The intersection of two line segments can be understood in several distinct ways, depending on how the segments are positioned relative to each other in the plane. Because of that, the possible outcomes range from no contact at all to a shared infinite set of points when the segments lie on the same line and overlap. In elementary geometry a line segment is defined by two endpoints, and when we ask what happens when we place two such objects together, the answer is not limited to a single point. Recognizing each case is essential for fields such as computer graphics, robotics, geographic information systems, and computational geometry, where algorithms must reliably detect and handle every scenario.
Types of Intersection Between Two Line Segments
When two line segments are considered, their intersection can fall into one of the following categories:
- Empty intersection – the segments do not touch at any point.
- Single‑point intersection – the segments meet at exactly one point. This point may be an interior point of both segments (a proper crossing) or an endpoint of one or both segments.
- Segment‑shaped intersection – the two segments are collinear and overlap over a non‑zero length, producing a line segment (which could be as short as a point if the overlap reduces to a single endpoint, but we treat that case under the single‑point category).
- Full coincidence – the segments are identical; their intersection is the entire segment itself.
Understanding why these are the only possibilities relies on the fact that each segment is a convex set. The intersection of two convex sets in ℝ² is also convex, and the only convex subsets of a line segment are the empty set, a point, or another line segment (possibly the whole segment). No other shape can arise.
Empty Intersection
Two segments fail to intersect when the convex hulls of their endpoint pairs are disjoint. A quick way to test this is to check whether the bounding boxes of the segments overlap; if they do not, the answer is definitively “no intersection.” Even when the bounding boxes overlap, the segments may still be separated, for example when they lie on parallel lines that never meet.
Easier said than done, but still worth knowing.
Single‑Point Intersection
A single‑point intersection occurs in two sub‑cases:
- Proper crossing – the segments intersect at a point that lies strictly inside each segment (not at an endpoint).
- Endpoint touch – at least one of the intersecting points is an endpoint of one or both segments.
In both situations the geometric condition is that the two lines supporting the segments are not parallel (or, if they are parallel, they coincide and the overlap reduces to a point). The algebraic test involves checking the orientation of triples of points (often called the ccw test) and verifying that the orientations differ appropriately.
Segment‑Shaped Intersection
When the supporting lines of the two segments are collinear, the intersection reduces to a problem of overlapping intervals on a line. The length of the overlap is the length of the intersecting interval; if this length is greater than zero, the intersection is a line segment. The intersection exists if the intervals [0,1] for the two segments overlap after applying the appropriate affine transformation that maps each segment onto the same line. On the flip side, represent each segment by the scalar parameter t that runs from 0 at one endpoint to 1 at the other. If the overlap is exactly a single point (the intervals touch at an endpoint), we fall back to the single‑point case.
Full Coincidence
Full coincidence is a special case of the segment‑shaped intersection where the two intervals are identical after transformation. Also, this happens when the four endpoints are pairwise equal (or when one segment is exactly the reverse of the other). In practice, detecting full coincidence is useful for deduplication routines in GIS data or for simplifying polygonal meshes.
Mathematical Foundations
To reason rigorously about the intersection of two line segments we rely on a few core concepts from analytic geometry and linear algebra.
Parametric Representation
A line segment S with endpoints P₀ = (x₀, y₀) and P₁ = (x₁, y₁) can be written as
[ \mathbf{S}(t) = \mathbf{P}_0 + t(\mathbf{P}_1 - \mathbf{P}_0), \qquad 0 \le t \le 1. ]
Similarly, a second segment T with endpoints Q₀, Q₁ is
[ \mathbf{T}(u) = \mathbf{Q}_0 + u(\mathbf{Q}_1 - \mathbf{Q}_0), \qquad 0 \le u \le 1. ]
The intersection problem becomes solving for (t, u) such that
[ \mathbf{P}_0 + t(\mathbf{P}_1 - \mathbf{P}_0) = \mathbf{Q}_0 + u(\mathbf{Q}_1 - \mathbf{Q}_0), ]
subject to the constraints 0 ≤ t ≤ 1 and 0 ≤ u ≤ 1.
Orientation Test
The orientation (or signed area) of three points A, B, C is given by
[ \text{orient}(\mathbf{A},\mathbf{B},\mathbf{C}) = (\mathbf{B}_x - \mathbf{A}_x)(\mathbf{C}_y - \mathbf{A}_y) - (\mathbf{B}_y - \mathbf{A}_y)(\mathbf{C}_x - \mathbf{A}_x). ]
- A positive value indicates a counter‑clockwise turn.
- A negative value indicates a clockwise turn.
- Zero means the points are collinear.
Two segments P₀P₁ and Q₀Q₁ properly intersect (interior point) iff
[ \text{orient}(P₀,P₁,Q₀) \times \text{orient}(P₀,P₁,Q₁) < 0 \quad\text{and}\quad \text{orient}(Q₀,Q₁,P₀) \times \text{orient}(Q₀,Q₁,P₁) < 0. ]
If any orientation equals zero, we must examine the collinear case separately, checking whether the projection of one segment onto the other overlaps.
Bounding‑Box Rejection
Before applying the orientation test, a cheap axis‑aligned bounding‑box check can eliminate many non‑intersecting pairs:
[ \max(P₀_x, P₁_x) < \min(Q₀_x, Q₁_x) ;\text{or}; \max(Q₀_x, Q₁_x) < \min(P₀_x, P₁_x) ;\text{or}; \max(P₀_y, P₁_y) < \min(Q₀_y, Q₁_y) ;\text{or}; \max(Q₀_y, Q₁_y) < \min(P₀_y, P₁_y). ]
If any of these inequalities holds
