Float Collinearity Causes Self-Intersecting Polygons

Line intersection is the foundational primitive of computational geometry. Collision detection, polygon clipping, sweep line algorithms, and convex hull construction all reduce to one question: do two segments intersect? The cross product orientation test answers this in O(1) with no division, making it numerically robust and fast.

Production geometry code fails not on the common case but on edge cases: collinear overlapping segments, endpoints lying exactly on segments, and floating-point precision at near-parallel intersections. A single missed collinear check can corrupt a convex hull, create self-intersecting polygons, or cause collision detection to miss contacts.

A common misconception is that line equations are equivalent to the cross product approach. They are not. Line equations require division, which introduces floating-point error. The cross product uses only multiplication and subtraction — exact for integer coordinates and significantly more robust for floats.

Orientation Test — The Core Primitive

The orientation of three points p, q, r is determined by the cross product of vectors (q-p) and (r-p): - Positive: counterclockwise (left turn) - Negative: clockwise (right turn) - Zero: collinear

This is the single operation that underlies all segment intersection tests. The cross product formula is:

val = (q.y - p.y) (r.x - q.x) - (q.x - p.x) (r.y - q.y)

No division is involved — only multiplication and subtraction. This makes the test exact for integer coordinates and significantly more robust than line-equation approaches that require dividing by a potentially-zero denominator.

def orientation(p, q, r):
    """
    Returns:
     1 — counterclockwise (left turn)
    -1 — clockwise (right turn)
     0 — collinear
    """
    val = (q[1]-p[1])*(r[0]-q[0]) - (q[0]-p[0])*(r[1]-q[1])
    if val > 0: return 1
    if val < 0: return -1
    return 0

print(orientation((0,0),(1,0),(0,1)))  # 1 (CCW)
print(orientation((0,0),(1,0),(2,0)))  # 0 (collinear)
print(orientation((0,0),(0,1),(1,0)))  # -1 (CW)

Segment Intersection

Two segments AB and CD intersect if their orientations 'straddle' each other. Specifically, A and B must be on opposite sides of line CD, AND C and D must be on opposite sides of line AB. This is checked by verifying that orientation(A,B,C) != orientation(A,B,D) and orientation(C,D,A) != orientation(C,D,B).

Edge case: when one or more orientations are zero (collinear), the segments may still intersect if an endpoint lies on the other segment. The on_segment test checks this by verifying the collinear point falls within the bounding box of the segment.

def on_segment(p, q, r):
    """Does point q lie on segment pr (given collinearity)?"""
    return (min(p[0],r[0]) <= q[0] <= max(p[0],r[0]) and
            min(p[1],r[1]) <= q[1] <= max(p[1],r[1]))

def segments_intersect(p1, q1, p2, q2) -> bool:
    """Do segments p1q1 and p2q2 intersect?"""
    o1 = orientation(p1, q1, p2)
    o2 = orientation(p1, q1, q2)
    o3 = orientation(p2, q2, p1)
    o4 = orientation(p2, q2, q1)
    if o1 != o2 and o3 != o4: return True
    # Collinear cases
    if o1 == 0 and on_segment(p1, p2, q1): return True
    if o2 == 0 and on_segment(p1, q2, q1): return True
    if o3 == 0 and on_segment(p2, p1, q2): return True
    if o4 == 0 and on_segment(p2, q1, q2): return True
    return False

print(segments_intersect((1,1),(10,1),(1,2),(10,2)))  # False (parallel)
print(segments_intersect((10,0),(0,10),(0,0),(10,10))) # True (X pattern)

Line Intersection Point

Given that two lines intersect, the intersection point is computed by solving the parametric equations of both lines simultaneously. For lines through p1-p2 and p3-p4, the denominator is the cross product of the direction vectors. If the denominator is zero, the lines are parallel. The parameter t gives the position along the first line, and the intersection point is p1 + t*(p2-p1).

This function operates on infinite lines, not segments. To find the intersection of segments, first verify they intersect using segments_intersect, then compute the point. For near-parallel lines, the denominator approaches zero and the intersection point becomes numerically unstable — handle this with an epsilon check.

def line_intersection(p1, p2, p3, p4):
    """Find intersection point of lines through p1-p2 and p3-p4."""
    x1,y1,x2,y2 = *p1, *p2
    x3,y3,x4,y4 = *p3, *p4
    denom = (x1-x2)*(y3-y4) - (y1-y2)*(x3-x4)
    if abs(denom) < 1e-10: return None  # parallel
    t = ((x1-x3)*(y3-y4) - (y1-y3)*(x3-x4)) / denom
    x = x1 + t*(x2-x1)
    y = y1 + t*(y2-y1)
    return (x, y)

print(line_intersection((0,0),(1,1),(0,1),(1,0)))  # (0.5, 0.5)

Frequently Asked Questions