17.3 Line and Segment Intersection

Given two lines or two line segments, determine whether they intersect and, if they do, compute the intersection point.

algorithmsgeometry

17.3 Line and Segment Intersection

Problem

Given two lines or two line segments, determine whether they intersect and, if they do, compute the intersection point.

This problem appears throughout computational geometry. Computer graphics uses intersection tests during rendering. Geographic information systems use them when processing roads, rivers, and administrative boundaries. Robotics uses them for collision detection and motion planning. Polygon clipping, sweep-line algorithms, and triangulation all rely heavily on robust intersection predicates.

The challenge is handling every possible configuration correctly, including parallel lines, overlapping segments, endpoint touching, and collinear cases.

Solution

Use orientation tests to determine the relative positions of endpoints.

Given two segments:

AB
CD

The general intersection condition is:

orientation(A,B,C) and orientation(A,B,D)
have opposite signs

AND

orientation(C,D,A) and orientation(C,D,B)
have opposite signs

This means each segment crosses the line containing the other segment.

Let:

o1 = orientation(A, B, C)
o2 = orientation(A, B, D)

o3 = orientation(C, D, A)
o4 = orientation(C, D, B)

The general case intersection test becomes:

if o1 * o2 < 0 and o3 * o4 < 0:
    return True

This handles all proper crossings.

Understanding the Geometry

Consider:

A------B
    /
   /
  /
 C------D

Point C and point D lie on opposite sides of line AB.

Similarly, A and B lie on opposite sides of line CD.

Both conditions hold simultaneously.

The segments intersect.

Orientation provides exactly the information needed to detect this situation.

Implementing the General Test

First define orientation:

def orientation(a, b, c):
    return (
        (b.x - a.x) * (c.y - a.y)
        - (b.y - a.y) * (c.x - a.x)
    )

Then:

def intersects_proper(a, b, c, d):
    o1 = orientation(a, b, c)
    o2 = orientation(a, b, d)

    o3 = orientation(c, d, a)
    o4 = orientation(c, d, b)

    return o1 * o2 < 0 and o3 * o4 < 0

This detects interior crossings but does not handle collinear cases.

Endpoint Touching

Consider:

A------B------C

Segment:

AB

touches segment:

BC

at endpoint B.

Some applications consider this an intersection.

Others consider it a special case.

To support endpoint touching, comparisons must include zero:

o1 * o2 <= 0
o3 * o4 <= 0

However, this alone is insufficient because collinear segments require additional handling.

Detecting Collinear Points on a Segment

Suppose:

A---------B
      C

and:

orientation(A,B,C) = 0

Point C lies somewhere on the line AB.

To determine whether C lies within the segment bounds:

def on_segment(a, b, p):
    return (
        min(a.x, b.x) <= p.x <= max(a.x, b.x)
        and
        min(a.y, b.y) <= p.y <= max(a.y, b.y)
    )

This test assumes collinearity has already been established.

Complete Segment Intersection Algorithm

def segments_intersect(a, b, c, d):
    o1 = orientation(a, b, c)
    o2 = orientation(a, b, d)

    o3 = orientation(c, d, a)
    o4 = orientation(c, d, b)

    if o1 * o2 < 0 and o3 * o4 < 0:
        return True

    if o1 == 0 and on_segment(a, b, c):
        return True

    if o2 == 0 and on_segment(a, b, d):
        return True

    if o3 == 0 and on_segment(c, d, a):
        return True

    if o4 == 0 and on_segment(c, d, b):
        return True

    return False

This handles:

  • Proper crossings
  • Endpoint touching
  • Collinear overlap
  • Degenerate cases

Computing Line Intersections

Sometimes the question is not merely whether two lines intersect but where.

Consider:

Line 1:
A + t(B - A)

Line 2:
C + u(D - C)

The intersection occurs when:

A + t(B - A)
=
C + u(D - C)

This produces a system of two equations with two unknowns.

Let:

r = B - A
s = D - C

Then:

A + tr
=
C + us

Solving yields:

t =
cross(C - A, s)
/
cross(r, s)

provided:

cross(r, s) ≠ 0

The intersection point is:

A + tr

Example

Line 1:

A = (0,0)
B = (4,4)

Line 2:

C = (0,4)
D = (4,0)

Vectors:

r = (4,4)
s = (4,-4)

Compute:

cross(r,s)
=
4(-4)-4(4)
=
-32

Nonzero result means lines are not parallel.

Next:

cross(C-A,s)
=
cross((0,4),(4,-4))
=
-16

Therefore:

t = (-16)/(-32)
   = 1/2

Substitute:

(0,0) + 1/2(4,4)
=
(2,2)

The lines intersect at:

(2,2)

Parallel Lines

Two lines are parallel when:

cross(r,s)
=
0

The direction vectors have identical slopes.

Example:

(1,2)
(2,4)

Cross product:

1×4 - 2×2
=
0

No unique intersection exists.

Coincident Lines

Consider:

Line 1: y = x
Line 2: y = x

Every point on one line lies on the other.

In this situation:

cross(r,s)=0

and

cross(C-A,r)=0

The lines coincide.

Instead of one intersection point, infinitely many exist.

Segment algorithms must handle this case separately.

Numerical Robustness

Floating-point geometry introduces significant complications.

Instead of:

cross(r, s) == 0

use:

EPS = 1e-9

abs(cross(r, s)) < EPS

Near-parallel lines frequently produce tiny nonzero values caused by rounding.

Robust geometry libraries often use exact predicates for critical operations.

Applications

Polygon Clipping

Every clipping operation repeatedly computes:

edge-edge intersections

between subject polygons and clipping boundaries.

Sweep-Line Algorithms

Event processing often depends on detecting intersections between neighboring segments.

Computer Graphics

Ray tracing computes millions of intersections per frame.

Geographic Information Systems

Road networks and boundaries are assembled from intersection computations.

Robotics

Collision detection relies on segment and polygon intersection tests.

Complexity Analysis

Orientation:

O(1)

On-segment check:

O(1)

Complete segment intersection:

O(1)

Line intersection computation:

O(1)

No loops or recursion are required.

Common Pitfalls

Ignoring Collinear Overlap

Many implementations correctly detect crossings but fail when segments overlap on the same line.

Forgetting Endpoint Intersections

Touching endpoints are often valid intersections.

Requirements should be defined explicitly.

Comparing Floats Directly

Avoid:

cross == 0

Use epsilon comparisons.

Assuming Unique Intersections

Parallel and coincident lines require separate logic.

The general formula only works when a unique solution exists.

Overflow

Large integer coordinates may overflow intermediate cross-product calculations.

Use sufficiently large numeric types.

Discussion

Segment intersection is one of the foundational predicates of computational geometry. Orientation testing provides the underlying mechanism, while bounding-box checks and collinearity handling complete the solution. Many seemingly unrelated geometric algorithms eventually reduce to repeated intersection queries. Once robust intersection testing becomes available, higher-level structures such as polygon clipping, sweep-line algorithms, visibility graphs, motion planning systems, and map-processing pipelines become much easier to construct.