Line intersection is a fundamental concept in computational geometry with applications spanning diverse fields: from game development (collision detection), computer graphics (rendering, picking), and CAD/GIS systems to pathfinding and robotics. While seemingly simple, accurately determining if and where two lines or line segments intersect, especially in edge cases, can be surprisingly tricky.
This post will demystify the process. We’ll cover:
- Representing lines in 2D space.
- The mathematics behind intersecting infinite lines.
- The more complex scenario of intersecting finite line segments, including parallel and collinear cases.
- Robust, runnable Python code examples for each concept.
Let’s dive in!
Representing Lines and Points
Before we can intersect lines, we need a consistent way to represent them. In 2D, the most intuitive way to define a line or segment is by two distinct points. A point itself is simply an (x, y) coordinate pair.
For our Python implementation, we’ll create a simple Point class. This class will not only hold coordinates but also provide helper methods for vector operations like subtraction (to get a direction vector), addition (for translating points), scalar multiplication (for scaling vectors), and crucial geometric operations like the dot product and cross product.
import math
from enum import Enum
# Define a small epsilon for floating-point comparisons
# This helps with precision issues when comparing calculated float values to 0 or 1.
EPSILON = 1e-9
class Point:
def __init__(self, x, y):
self.x = float(x) # Ensure coordinates are floats for calculations
self.y = float(y)
def __repr__(self):
# A clear representation for debugging
return f"Point({self.x:.4f}, {self.y:.4f})" # Format to 4 decimal places
def __eq__(self, other):
# Custom equality for robust float comparisons
if not isinstance(other, Point):
return NotImplemented
return abs(self.x - other.x) < EPSILON and abs(self.y - other.y) < EPSILON
def __sub__(self, other):
# Vector subtraction (self - other)
return Point(self.x - other.x, self.y - other.y)
def __add__(self, other):
# Vector addition (self + other)
return Point(self.x + other.x, self.y + other.y)
def __mul__(self, scalar):
# Scalar multiplication (vector * scalar)
return Point(self.x * scalar, self.y * scalar)
def __truediv__(self, scalar):
# Scalar division (vector / scalar)
if abs(scalar) < EPSILON:
raise ValueError("Division by zero scalar is not allowed.")
return Point(self.x / scalar, self.y / scalar)
def dot_product(self, other):
# Dot product of two vectors
return self.x * other.x + self.y * other.y
def cross_product(self, other):
# 2D cross product (scalar value: z-component of 3D cross product)
# For vectors (x1, y1) and (x2, y2), it's x1*y2 - y1*x2.
# Its sign indicates orientation:
# > 0: 'other' is counter-clockwise from 'self'
# < 0: 'other' is clockwise from 'self'
# = 0: 'self' and 'other' are collinear (parallel)
return self.x * other.y - self.y * other.x
def magnitude_sq(self):
# Squared magnitude (length) of the vector
return self.x**2 + self.y**2
def magnitude(self):
# Magnitude (length) of the vector
return math.sqrt(self.magnitude_sq())
# Enum to describe the type of intersection found
class IntersectionType(Enum):
NONE = 0
POINT = 1
SEGMENT = 2 # For collinear and overlapping segmentsIntersection of Two Infinite Lines
The simplest case is finding the intersection of two infinite lines. We’ll use the parametric form of a line, which is highly versatile:
Line 1: $P_1(t) = P_1 + t \cdot (P_2 - P_1)$ Line 2: $P_2(u) = P_3 + u \cdot (P_4 - P_3)$
Here, $P_1$, $P_2$, $P_3$, $P_4$ are points defining the lines. $(P_2 - P_1)$ and $(P_4 - P_3)$ are direction vectors (let’s call them $V_1$ and $V_2$). $t$ and $u$ are scalar parameters. If the lines intersect, there must be values of $t$ and $u$ such that:
$P_1 + t \cdot V_1 = P_3 + u \cdot V_2$
Rearranging this equation gives:
$t \cdot V_1 - u \cdot V_2 = P_3 - P_1$
This is a system of two linear equations (one for x-coordinates, one for y-coordinates) with two unknowns ($t$ and $u$):
$t \cdot V_{1x} - u \cdot V_{2x} = P_{3x} - P_{1x}$ $t \cdot V_{1y} - u \cdot V_{2y} = P_{3y} - P_{1y}$
We can solve this system using Cramer’s Rule or direct substitution. A common and robust way involves cross products:
The denominator for $t$ and $u$ is $V_1 \times V_2$ (the 2D cross product, V1.cross_product(V2)).
If this denominator is zero, the lines are parallel. Otherwise, they intersect at a unique point.
The numerators are: $t_{num} = (P_3 - P_1) \times V_2$ $u_{num} = (P_3 - P_1) \times V_1$
So, $t = t_{num} / (V_1 \times V_2)$ and $u = u_{num} / (V_1 \times V_2)$. Once we have $t$ (or $u$), we can plug it back into its respective parametric equation to find the intersection point.
Special Cases for Infinite Lines:
- Parallel Lines: If $V_1 \times V_2 = 0$ and $(P_3 - P_1) \times V_2 \neq 0$, the lines are parallel and distinct. They never intersect.
- Collinear Lines: If $V_1 \times V_2 = 0$ and $(P_3 - P_1) \times V_2 = 0$, the lines are collinear. This means they are parallel and share at least one point, hence they overlap infinitely.
Let’s implement a function for infinite line intersection.
def intersect_infinite_lines(p1, p2, p3, p4):
"""
Calculates the intersection of two infinite lines defined by (p1,p2) and (p3,p4).
Returns (IntersectionType, intersection_data):
- (IntersectionType.POINT, Point) if they intersect at a single point.
- (IntersectionType.INFINITE_COLLINEAR, None) if they are collinear.
- (IntersectionType.NONE, None) if they are parallel and distinct.
"""
v1 = p2 - p1 # Direction vector for line 1
v2 = p4 - p3 # Direction vector for line 2
denominator = v1.cross_product(v2)
# If denominator is close to zero, lines are parallel
if abs(denominator) < EPSILON:
# Check if they are collinear (P3-P1 is also parallel to V2)
# Note: If v1.cross_product(v2) is 0, and (p3-p1).cross_product(v2) is also 0,
# then p3-p1 is parallel to v2. Since v1 is also parallel to v2,
# it implies p3-p1 is parallel to v1, meaning p1, p3, p4 are collinear.
# If p1, p3, p4 are collinear, and p1, p2 are collinear, then all 4 points are collinear.
if abs((p3 - p1).cross_product(v2)) < EPSILON:
return IntersectionType.INFINITE_COLLINEAR, None
else:
return IntersectionType.NONE, None
# Calculate parameters t and u
t = (p3 - p1).cross_product(v2) / denominator
# u = (p3 - p1).cross_product(v1) / denominator # Not strictly needed for the point itself
intersection_point = p1 + v1 * t
return IntersectionType.POINT, intersection_pointInfinite Line Intersection Examples
Let’s see some common scenarios.
# --- Example 1: Standard intersection ---
p1, p2 = Point(0, 0), Point(10, 10) # Line 1: y = x
p3, p4 = Point(0, 10), Point(10, 0) # Line 2: y = -x + 10
type, result = intersect_infinite_lines(p1, p2, p3, p4)
print(f"Example 1 (Standard): {type}, {result}")
# --- Example 2: Parallel lines ---
p1, p2 = Point(0, 0), Point(10, 0) # Line 1: y = 0
p3, p4 = Point(0, 1), Point(10, 1) # Line 2: y = 1
type, result = intersect_infinite_lines(p1, p2, p3, p4)
print(f"Example 2 (Parallel): {type}, {result}")
# --- Example 3: Collinear lines ---
p1, p2 = Point(0, 0), Point(10, 0) # Line 1: y = 0
p3, p4 = Point(5, 0), Point(15, 0) # Line 2: y = 0
type, result = intersect_infinite_lines(p1, p2, p3, p4)
print(f"Example 3 (Collinear): {type}, {result}")
# --- Example 4: Vertical lines intersection ---
p1, p2 = Point(5, 0), Point(5, 10) # Line 1: x = 5
p3, p4 = Point(0, 5), Point(10, 5) # Line 2: y = 5
type, result = intersect_infinite_lines(p1, p2, p3, p4)
print(f"Example 4 (Vertical): {type}, {result}")Example 1 (Standard): IntersectionType.POINT, Point(5.0000, 5.0000)
Example 2 (Parallel): IntersectionType.NONE, None
Example 3 (Collinear): IntersectionType.INFINITE_COLLINEAR, None
Example 4 (Vertical): IntersectionType.POINT, Point(5.0000, 5.0000)Intersection of Two Line Segments
This is where it gets more involved. The math for finding the intersection point is identical to infinite lines. The crucial difference is that once we find t and u, we must check if they fall within the range [0, 1].
- If
0 <= t <= 1, the intersection point lies on the first segment. - If
0 <= u <= 1, the intersection point lies on the second segment.
If both conditions are met, the segments intersect at a single point. If either is outside this range, the infinite lines intersect, but the segments do not.
Special Cases for Line Segments:
-
Parallel and Non-Collinear: If the denominator ($V_1 \times V_2$) is zero and they are not collinear, there is no intersection. Return
NONE. -
Collinear Segments: This is the most complex case. If the segments are collinear, we need to check if they overlap.
- No Overlap: Segments are collinear but separate (e.g., [0,5] and [6,10]). Return
NONE. - Touching at an Endpoint: Segments touch at a single point (e.g., [0,5] and [5,10]). This counts as a
POINTintersection. - Overlapping: Segments share a common interval (e.g., [0,10] and [5,15]). The intersection is itself a
SEGMENT.
- No Overlap: Segments are collinear but separate (e.g., [0,5] and [6,10]). Return
To handle collinear overlap, we can project all four segment endpoints onto the line they share and check for overlap of the resulting 1D intervals. A simpler approach for two segments is to check if any of the endpoints of one segment lies on the other segment, or if the segments are “interspersed”.
Our is_on_segment_bbox helper will check if a point lies within the bounding box of a segment (which, combined with the collinearity check, effectively means it’s on the segment). By checking all four segment endpoints against the other segment, we can determine if there’s any overlap.
Let’s refine the intersect_segments function:
def intersect_segments(p1, p2, p3, p4):
"""
Calculates the intersection of two line segments defined by (p1,p2) and (p3,p4).
Returns (IntersectionType, intersection_data):
- (IntersectionType.POINT, Point) if they intersect at a single point.
- (IntersectionType.SEGMENT, (Point, Point)) if they are collinear and overlap.
- (IntersectionType.NONE, None) if no intersection.
"""
v1 = p2 - p1 # Direction vector for segment 1
v2 = p4 - p3 # Direction vector for segment 2
denominator = v1.cross_product(v2)
# Numerators for t and u (relative to p1)
t_numerator = (p3 - p1).cross_product(v2)
u_numerator = (p3 - p1).cross_product(v1)
# Case 1: Lines are parallel (denominator is close to zero)
if abs(denominator) < EPSILON:
# Check if they are collinear (numerator for t is also close to zero)
if abs(t_numerator) < EPSILON:
# Collinear segments: check for overlap
# Helper to check if a point 'q' is on the segment defined by 'a' and 'b'
# This assumes q, a, b are already collinear.
# We use a bounding box check with EPSILON for floating point robustness.
def is_on_segment_bbox(q, a, b):
# Ensure x and y coordinates are within the min/max of the segment's bounding box
return (min(a.x, b.x) - EPSILON <= q.x <= max(a.x, b.x) + EPSILON and
min(a.y, b.y) - EPSILON <= q.y <= max(a.y, b.y) + EPSILON)
# Collect points that are on the OTHER segment
overlapping_points = []
if is_on_segment_bbox(p1, p3, p4): overlapping_points.append(p1)
if is_on_segment_bbox(p2, p3, p4): overlapping_points.append(p2)
if is_on_segment_bbox(p3, p1, p2): overlapping_points.append(p3)
if is_on_segment_bbox(p4, p1, p2): overlapping_points.append(p4)
# Remove duplicates and sort them for consistent segment representation.
# The Point.__eq__ method handles float comparisons using EPSILON.
unique_points = []
for p in overlapping_points:
if p not in unique_points:
unique_points.append(p)
# Sort points, first by x, then by y to define the segment consistently
unique_points.sort(key=lambda p: (p.x, p.y))
if len(unique_points) >= 2:
# Overlap is a segment (at least two unique points)
return IntersectionType.SEGMENT, (unique_points[0], unique_points[-1])
elif len(unique_points) == 1:
# Overlap is a single point (segments touch at an endpoint)
return IntersectionType.POINT, unique_points[0]
else:
# Collinear but no overlap
return IntersectionType.NONE, None
else:
# Parallel but not collinear
return IntersectionType.NONE, None
# Case 2: Lines are not parallel
# Calculate parameters t and u
t = t_numerator / denominator
u = u_numerator / denominator
# Check if the intersection point lies within both segments (0 to 1 inclusive)
if (0 - EPSILON <= t <= 1 + EPSILON and
0 - EPSILON <= u <= 1 + EPSILON):
intersection_point = p1 + v1 * t
return IntersectionType.POINT, intersection_point
else:
# Intersection point is outside one or both segments
return IntersectionType.NONE, NoneLine Segment Intersection Examples
Let’s put the segment intersection logic to the test with various scenarios.
# --- Example 1: Standard intersection of two segments ---
# Seg1: (0,0) to (10,10)
# Seg2: (0,10) to (10,0)
# Expected: (5,5)
p1, p2 = Point(0, 0), Point(10, 10)
p3, p4 = Point(0, 10), Point(10, 0)
type, result = intersect_segments(p1, p2, p3, p4)
print(f"1. Standard Intersection: {type}, {result}")
# --- Example 2: Segments do not intersect, but their infinite lines do ---
# Seg1: (0,0) to (1,1)
# Seg2: (10,0) to (11,1)
# Infinite lines intersect at (-9, -9), but segments are far apart.
p1, p2 = Point(0, 0), Point(1, 1)
p3, p4 = Point(10, 0), Point(11, 1)
type, result = intersect_segments(p1, p2, p3, p4)
print(f"2. Non-intersecting segments (infinite lines intersect): {type}, {result}")
# --- Example 3: Parallel, non-collinear segments ---
# Seg1: (0,0) to (10,0)
# Seg2: (0,1) to (10,1)
# Expected: No intersection
p1, p2 = Point(0, 0), Point(10, 0)
p3, p4 = Point(0, 1), Point(10, 1)
type, result = intersect_segments(p1, p2, p3, p4)
print(f"3. Parallel, non-collinear: {type}, {result}")
# --- Example 4: Collinear, overlapping segments ---
# Seg1: (0,0) to (10,0)
# Seg2: (5,0) to (15,0)
# Expected: (5,0) to (10,0)
p1, p2 = Point(0, 0), Point(10, 0)
p3, p4 = Point(5, 0), Point(15, 0)
type, result = intersect_segments(p1, p2, p3, p4)
print(f"4. Collinear, overlapping: {type}, {result}")
# --- Example 5: Collinear, touching at an endpoint ---
# Seg1: (0,0) to (5,0)
# Seg2: (5,0) to (10,0)
# Expected: (5,0)
p1, p2 = Point(0, 0), Point(5, 0)
p3, p4 = Point(5, 0), Point(10, 0)
type, result = intersect_segments(p1, p2, p3, p4)
print(f"5. Collinear, touching endpoint: {type}, {result}")
# --- Example 6: Collinear, no overlap ---
# Seg1: (0,0) to (1,0)
# Seg2: (2,0) to (3,0)
# Expected: No intersection
p1, p2 = Point(0, 0), Point(1, 0)
p3, p4 = Point(2, 0), Point(3, 0)
type, result = intersect_segments(p1, p2, p3, p4)
print(f"6. Collinear, no overlap: {type}, {result}")
# --- Example 7: Vertical line intersection ---
# Seg1: (5,0) to (5,10)
# Seg2: (0,5) to (10,5)
# Expected: (5,5)
p1, p2 = Point(5, 0), Point(5, 10)
p3, p4 = Point(0, 5), Point(10, 5)
type, result = intersect_segments(p1, p2, p3, p4)
print(f"7. Vertical line intersection: {type}, {result}")
# --- Example 8: One segment is a point, intersects another segment ---
# Seg1: (5,5) to (5,5) (a point)
# Seg2: (0,0) to (10,10)
# Expected: (5,5)
p1, p2 = Point(5, 5), Point(5, 5)
p3, p4 = Point(0, 0), Point(10, 10)
type, result = intersect_segments(p1, p2, p3, p4)
print(f"8. Point segment intersection: {type}, {result}")
# --- Example 9: One segment is a point, does not intersect ---
# Seg1: (5,5) to (5,5)
# Seg2: (0,0) to (1,1)
# Expected: No intersection
p1, p2 = Point(5, 5), Point(5, 5)
p3, p4 = Point(0, 0), Point(1, 1)
type, result = intersect_segments(p1, p2, p3, p4)
print(f"9. Point segment no intersection: {type}, {result}")
# --- Example 10: Both segments are points, intersecting ---
# Seg1: (5,5) to (5,5)
# Seg2: (5,5) to (5,5)
# Expected: (5,5)
p1, p2 = Point(5, 5), Point(5, 5)
p3, p4 = Point(5, 5), Point(5, 5)
type, result = intersect_segments(p1, p2, p3, p4)
print(f"10. Both segments are points, intersecting: {type}, {result}")
# --- Example 11: Both segments are points, non-intersecting ---
# Seg1: (5,5) to (5,5)
# Seg2: (6,6) to (6,6)
# Expected: No intersection
p1, p2 = Point(5, 5), Point(5, 5)
p3, p4 = Point(6, 6), Point(6, 6)
type, result = intersect_segments(p1, p2, p3, p4)
print(f"11. Both segments are points, non-intersecting: {type}, {result}")1. Standard Intersection: IntersectionType.POINT, Point(5.0000, 5.0000)
2. Non-intersecting segments (infinite lines intersect): IntersectionType.NONE, None
3. Parallel, non-collinear: IntersectionType.NONE, None
4. Collinear, overlapping: IntersectionType.SEGMENT, (Point(5.0000, 0.0000), Point(10.0000, 0.0000))
5. Collinear, touching endpoint: IntersectionType.POINT, Point(5.0000, 0.0000)
6. Collinear, no overlap: IntersectionType.NONE, None
7. Vertical line intersection: IntersectionType.POINT, Point(5.0000, 5.0000)
8. Point segment intersection: IntersectionType.POINT, Point(5.0000, 5.0000)
9. Point segment no intersection: IntersectionType.NONE, None
10. Both segments are points, intersecting: IntersectionType.POINT, Point(5.0000, 5.0000)
11. Both segments are points, non-intersecting: IntersectionType.NONE, NoneConsiderations and Nuances
- Floating Point Precision: As seen with
EPSILON, comparing floating-point numbers directly for equality (==) is a common pitfall. Always use a small epsilon value to check if numbers are “close enough” to zero or to each other. - Edge Cases: The handling of parallel, collinear, and point segments is crucial for a robust intersection algorithm. Many simpler implementations overlook these, leading to unexpected behavior. Our
Pointclass’s__eq__andEPSILONusage, along with the detailed collinear check, address these. - Performance: For very high-performance scenarios (e.g., millions of collision checks per frame), optimizing the
Pointclass (e.g., usingnamedtupleornumpyarrays) and theintersect_segmentsfunction might be necessary. However, for most applications, this explicit, clear implementation is perfectly adequate. - Beyond 2D: Line intersection in 3D is significantly more complex, often involving finding the closest points between two lines (which may or may not intersect). Polygon intersection and clipping build upon these fundamental line intersection principles.
Conclusion
Understanding line intersection is a cornerstone of computational geometry. By representing points and lines effectively, leveraging the parametric form, and carefully handling edge cases like parallelism and collinearity (especially for segments), you can build robust and reliable geometric algorithms.
The Python code provided offers a practical, runnable example that covers the core logic and common pitfalls. Feel free to adapt and expand upon it for your own projects! Experiment with different point coordinates to fully grasp the various intersection scenarios.