Line Intersection and Orientation in Computational Geometry
- Orientation test: cross product sign of (q-p)×(r-p). Positive=CCW, Negative=CW, Zero=collinear. No division — exact for integer coordinates.
- Segment intersection: segments AB, CD intersect iff {A,B} straddle CD AND {C,D} straddle AB. Handle collinear endpoint cases separately.
- No division in orientation test makes it exact for integer coordinates — crucial for robust geometry code.
Line intersection is the foundation of computational geometry. Every collision detection system, every polygon clipping algorithm, every sweep line algorithm, and every convex hull construction relies on one primitive: do two line segments intersect? The cross product orientation test answers this in O(1) with no division, making it numerically robust and fast.
Getting this right in practice requires handling edge cases that break naive implementations: collinear overlapping segments, endpoint-on-segment cases, and floating-point precision at near-parallel intersections. Production geometry code uses exact arithmetic (integer coordinates) or epsilon-based floating point checks depending on the application.
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.
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)
0
-1
Segment Intersection
Two segments AB and CD intersect if their orientations 'straddle' each other. Edge case: collinear overlapping segments require an additional on-segment test.
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)
True
Line Intersection Point
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)
🎯 Key Takeaways
- Orientation test: cross product sign of (q-p)×(r-p). Positive=CCW, Negative=CW, Zero=collinear. No division — exact for integer coordinates.
- Segment intersection: segments AB, CD intersect iff {A,B} straddle CD AND {C,D} straddle AB. Handle collinear endpoint cases separately.
- No division in orientation test makes it exact for integer coordinates — crucial for robust geometry code.
- Foundation for: convex hull (Graham scan, Jarvis march), polygon intersection, sweep line algorithms, collision detection.
Interview Questions on This Topic
- QWhat does the cross product tell you about three points' orientation?
- QHow do you handle the collinear case in segment intersection?
- QWhy is the cross product preferred over direct line equations for intersection testing?
Frequently Asked Questions
How do you handle floating-point precision in geometry algorithms?
Two approaches: (1) Use integer coordinates and exact arithmetic — cross product is exact for integers. (2) Use epsilon comparisons — treat |val| < eps as collinear. For production computational geometry (CAD, GIS), exact arithmetic libraries like CGAL or Shapely handle this robustly.
Developer and founder of TheCodeForge. I built this site because I was tired of tutorials that explain what to type without explaining why it works. Every article here is written to make concepts actually click.