Intermediate 3 min · March 24, 2026

Float Collinearity Causes Self-Intersecting Polygons

Naive line intersection using raw float equality failed on nearly collinear vertices, causing a self-intersecting polygon destroying three prototypes.

N
Naren · Founder
Plain-English first. Then code. Then the interview question.
About
 ● Production Incident 🔎 Debug Guide
⚡Quick Answer
  • Orientation test: cross product of vectors (q-p) x (r-p). Positive = CCW, Negative = CW, Zero = collinear. No division — exact for integer coordinates.
  • Segment intersection: segments AB and CD intersect iff {A,B} straddle CD AND {C,D} straddle AB. Collinear cases require an on-segment bounding-box check.
  • Intersection point: solve parametric line equations. Denominator near zero means parallel — check with epsilon.
  • Performance: O(1) per test. No allocations, no division in orientation. Batch tests dominate sweep line algorithms.
  • Production insight: floating-point precision is the #1 source of geometry bugs. Use integer coordinates or epsilon comparisons — never raw float equality.
  • Biggest mistake: forgetting collinear endpoint cases. Naive implementations return wrong results when an endpoint lies exactly on the other segment.
Plain-English First

Two line segments on a plane: do they cross? This sounds simple but requires careful handling of collinear points, endpoints, and floating-point precision. The cross product orientation test answers this in O(1) — and it is the building block of convex hull, polygon clipping, and sweep line algorithms.

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.

orientation.pyPYTHON
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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)
Output
1
0
-1
The Cross Product as a Signed Area
  • Cross product = 2 * signed area of triangle (p, q, r)
  • Positive area = points are counterclockwise
  • Zero area = points are collinear (triangle degenerates to a line)
  • No division means no rounding error for integer inputs
Production Insight
Cause: Using line equations (y = mx + b) for orientation requires computing slope (division), which introduces floating-point error for near-vertical lines and loses precision for large coordinates. Effect: Near-vertical lines produce infinite or near-infinite slopes, causing orientation tests to return wrong results. A single wrong orientation corrupts the entire convex hull or sweep line output. Action: Always use the cross product formula — no division. For integer coordinates, the result is exact. For floating-point coordinates, add epsilon comparison: treat |val| < EPS as collinear.
Key Takeaway
The orientation test is the atomic primitive of computational geometry. It uses only multiplication and subtraction — no division — making it exact for integers and robust for floats. Every segment intersection, convex hull, and sweep line algorithm reduces to repeated calls to this single function.
Choosing Arithmetic Precision
IfInput coordinates are integers (pixel coordinates, grid-based, CAD with integer units).
→
UseUse cross product with integer arithmetic. Result is exact — no epsilon needed.
IfInput coordinates are floats (GPS, physics simulation, real-world measurements).
→
UseUse cross product with epsilon comparison. Treat |val| < EPS as collinear. Choose EPS based on coordinate magnitude.
IfApplication requires guaranteed correctness (formal verification, financial geometry, safety-critical CAD).
→
UseUse exact rational arithmetic (Python fractions, Java BigDecimal, or CGAL's exact predicates). No epsilon, no approximation.

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.

segment_intersection.pyPYTHON
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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)
Output
False
True
The Four Collinear Checks Are Not Optional
  • o1 == 0: p2 is collinear with p1q1 — check if p2 lies on segment p1q1
  • o2 == 0: q2 is collinear with p1q1 — check if q2 lies on segment p1q1
  • o3 == 0: p1 is collinear with p2q2 — check if p1 lies on segment p2q2
  • o4 == 0: q1 is collinear with p2q2 — check if q1 lies on segment p2q2
Production Insight
Cause: Naive implementations only check the general straddling case (o1 != o2 and o3 != o4) and skip the four collinear endpoint checks. Effect: Segments that share an endpoint, or where one endpoint lies exactly on the other segment, are reported as non-intersecting. In polygon clipping, this creates gaps. In collision detection, it allows objects to pass through each other at contact points. Action: Always include all four collinear checks. Test with segments that share endpoints, are collinear but non-overlapping, and are collinear and overlapping.
Key Takeaway
Segment intersection requires two tests: general straddling (o1 != o2 and o3 != o4) AND four collinear endpoint checks. Missing the collinear cases is the most common bug in geometry code — it silently fails on T-junctions, shared endpoints, and overlapping collinear segments.
Intersection Test Edge Cases
IfSegments cross in an X pattern (general case).
→
UseGeneral straddling test catches this: o1 != o2 and o3 != o4.
IfSegments share exactly one endpoint (T-junction or corner touch).
→
UseCollinear check catches this: one orientation is zero, on_segment returns True.
IfSegments are collinear and overlap (partial or full overlap).
→
UseCollinear check catches this: both orientations on one side are zero, bounding-box overlap detected by on_segment.
IfSegments are collinear but do not overlap (gap between them).
→
UseCollinear check returns False: on_segment bounding-box test fails — the points are collinear but outside the segment range.
IfSegments are parallel but not collinear (distinct lines).
→
UseGeneral straddling test returns False: o1 == o2 (same side) and o3 == o4 (same side). No collinear case triggered.

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.

intersection_point.pyPYTHON
1
2
3
4
5
6
7
8
9
10
11
12
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)
Output
(0.5, 0.5)
Lines vs Segments: Know Which You Need
  • line_intersection: where do the infinite lines through these points cross?
  • segments_intersect: do the finite segments between these points overlap?
  • To get segment intersection point: call segments_intersect first, then line_intersection
  • Calling line_intersection alone gives false positives for non-overlapping segments
Production Insight
Cause: Using line_intersection without first checking segments_intersect. The function returns a point for any non-parallel lines, even if the segments themselves do not overlap. Effect: In collision detection, this reports intersections where none exist — objects that are far apart but whose extended lines cross are reported as colliding. In polygon clipping, this creates phantom intersection points outside both polygon edges. Action: Always guard line_intersection with a segments_intersect check. The intersection point is only valid if the segments actually cross.
Key Takeaway
line_intersection computes where infinite lines cross — it does NOT check if the segments overlap. Always guard with segments_intersect first. The denominator is the cross product of direction vectors: near-zero means parallel. Choose your epsilon based on coordinate scale.
When to Use Each Function
IfNeed to know IF two segments intersect (boolean question).
→
UseUse segments_intersect. O(1), no division, handles all edge cases.
IfNeed the exact intersection POINT of two segments.
→
UseFirst call segments_intersect to verify. Then call line_intersection to compute the point.
IfNeed where two infinite lines cross (ray casting, line-line intersection).
→
UseUse line_intersection directly. No segment check needed — you want the infinite line intersection.
IfNeed intersection of a ray with a segment (ray casting for visibility).
→
UseUse parametric ray equation combined with segments_intersect. Check that t >= 0 (intersection is in front of ray origin).
● Production incidentPOST-MORTEMseverity: high

Self-Intersecting Polygon in CAD Export Crashes CNC Machine

Symptom
CNC machine cut paths that intersected themselves, creating holes in the prototype where solid material should exist. QA flagged the issue after the third destroyed prototype. The CAD export showed valid polygons on screen but the simplified vertex output contained crossing edges.
Assumption
The team assumed the polygon simplification (Ramer-Douglas-Peucker algorithm) always produced valid simple polygons. They tested with hand-crafted inputs but never with real-world CAD data containing near-collinear vertices from curved surface tessellation.
Root cause
The Ramer-Douglas-Peucker implementation used a naive segment intersection check that did not handle collinear cases. When three consecutive vertices were nearly collinear (within floating-point epsilon), the middle vertex was removed, but the resulting simplified edge crossed another edge of the polygon. The orientation test returned zero (collinear) but the on-segment check used raw float comparison instead of epsilon, so it failed to detect the overlap. The simplified polygon had a self-intersection that the downstream CNC path generator faithfully followed.
Fix
1. Replaced raw float comparison in on_segment with epsilon-based check: if abs(val) < EPS, treat as collinear. 2. Added a post-simplification validation pass that runs O(n^2) intersection checks on all non-adjacent edges of the output polygon. 3. Switched to exact arithmetic (rational numbers) for the orientation test when coordinates are derived from CAD data. 4. Added adversarial test cases with near-collinear vertices (angle < 0.001 degrees) to the regression suite.
Key lesson
  • Floating-point equality in geometry is never safe. Always use epsilon comparisons or exact arithmetic.
  • Polygon simplification algorithms can produce self-intersecting output if the intersection predicate is imprecise.
  • Post-condition validation (checking that output polygons are simple) catches bugs that the algorithm itself misses.
  • Test with adversarial inputs: near-collinear vertices, near-parallel edges, degenerate triangles. Real CAD data is full of these.
Production debug guideWhen intersection tests return wrong results, miss edge cases, or produce degenerate polygons.5 entries
Symptom · 01
Intersection test returns True for parallel segments that clearly do not overlap.
→
Fix
Check the epsilon threshold in the collinear on_segment test. If epsilon is too large, near-parallel segments are treated as collinear and the bounding-box overlap check triggers incorrectly. Reduce epsilon or switch to exact arithmetic.
Symptom · 02
Intersection test misses an intersection at a shared endpoint.
→
Fix
Verify that the collinear on_segment cases are handled. The general straddling test (o1 != o2 and o3 != o4) does NOT catch endpoint-on-segment cases. All four collinear checks must be present: o1==0, o2==0, o3==0, o4==0.
Symptom · 03
Convex hull output has collinear points that should have been removed.
→
Fix
Check the orientation test in the hull construction. If the hull uses '<= 0' to remove collinear points, it keeps the last collinear point. If it uses '< 0', it keeps all collinear points. Decide based on your spec and be consistent.
Symptom · 04
Sweep line algorithm produces wrong results on inputs with many vertical segments.
→
Fix
Vertical segments have undefined slope, which breaks line-equation-based intersection. Use the cross product orientation test — it handles vertical and horizontal segments correctly with no special cases.
Symptom · 05
Intersection point calculation returns NaN or Infinity for nearly parallel lines.
→
Fix
The denominator (x1-x2)(y3-y4) - (y1-y2)(x3-x4) approaches zero for parallel lines. Add an epsilon check: if abs(denom) < EPS, return None (parallel). Choose EPS based on your coordinate range — 1e-10 for unit-scale, 1e-6 for pixel-scale.
★ Geometry Intersection Triage Cheat SheetFast diagnostics for intersection test failures in production geometry code.
Parallel segments reported as intersecting.−
Immediate action
Check epsilon threshold in collinear on_segment test.
Commands
Print orientation values for all four point triples to verify they are near-zero
Check if on_segment bounding-box test uses raw float or epsilon comparison
Fix now
Add epsilon to on_segment: if abs(orientation_val) > EPS, skip collinear branch. Tune EPS to coordinate scale.
Shared endpoint intersection missed.+
Immediate action
Verify all four collinear checks are present in segments_intersect.
Commands
Add debug print: print(f'o1={o1} o2={o2} o3={o3} o4={o4}') before return
Test with segments sharing exactly one endpoint: ((0,0),(1,1)) and ((1,1),(2,0))
Fix now
Ensure all four if oN==0 and on_segment(...) checks exist. Do not shortcut the collinear cases.
Intersection point is wildly wrong for nearly parallel lines.+
Immediate action
Check if denominator is near zero before dividing.
Commands
Print denom value: should be > EPS for valid intersection
If denom < EPS, treat as parallel — return None instead of dividing
Fix now
Add: if abs(denom) < 1e-10: return None. Choose EPS based on coordinate scale.
O(n^2) intersection checks are too slow for large polygon sets.+
Immediate action
Switch to sweep line algorithm for batch intersection detection.
Commands
Profile: count total segment pairs being tested
Implement Bentley-Ottmann sweep line to reduce to O((n+k) log n)
Fix now
Use sweep line for n > 1000 segments. O(n^2) is fine for small inputs.
Intersection Detection Approaches
ApproachArithmeticHandles CollinearHandles EndpointPerformanceBest For
Cross Product OrientationMultiplication + subtraction onlyYes (with on_segment)Yes (4 collinear checks)O(1) per test, no divisionGeneral segment intersection, convex hull, sweep line
Line Equation (y = mx + b)Division requiredNo (slope undefined for vertical)Requires special casesO(1) but division overheadSimple horizontal/vertical cases only
Parametric (p + t*d)Multiplication + divisionYes (denom = 0 check)Yes (t in [0,1] check)O(1) per testComputing intersection POINTS, ray casting
Exact Rational ArithmeticInteger operations on fractionsExact — no epsilonExact — no epsilonSlower (GCD per operation)Safety-critical CAD, formal verification, financial geometry
Sweep Line (Bentley-Ottmann)Cross product at coreYesYesO((n+k) log n) for n segmentsBatch intersection detection on large segment sets

Key takeaways

1
Orientation test
cross product sign of (q-p) x (r-p). Positive = CCW, Negative = CW, Zero = collinear. No division — exact for integer coordinates.
2
Segment intersection
segments AB, CD intersect iff {A,B} straddle CD AND {C,D} straddle AB. Handle collinear endpoint cases separately.
3
No division in orientation test makes it exact for integer coordinates
crucial for robust geometry code.
4
Foundation for
convex hull (Graham scan, Jarvis march), polygon intersection, sweep line algorithms, collision detection.
5
Floating-point precision is the #1 source of geometry bugs. Use epsilon comparisons or exact arithmetic
never raw float equality.
6
line_intersection computes where infinite lines cross. Always guard with segments_intersect to verify the segments actually overlap.
INTERVIEW PREP · PRACTICE MODE

Interview Questions on This Topic

FAQ · 5 QUESTIONS

Frequently Asked Questions

01
How do you handle floating-point precision in geometry algorithms?
02
What is the difference between line intersection and segment intersection?
03
Why does the orientation test use cross product instead of computing slopes?
04
How do you choose the epsilon value for collinearity checks?
05
What is the Bentley-Ottmann sweep line algorithm?
Related Next Steps
→Convex Hull Algorithms: Graham Scan and Jarvis MarchBuild on the orientation test to construct convex hulls. Graham scan uses sorted angular order with cross product comparisons. Jarvis march uses orientation to find the next hull vertex. Both reduce to repeated orientation calls.
🔥

That's Geometry. Mark it forged?

3 min read · try the examples if you haven't

←
Previous
Public Key Infrastructure (PKI) Explained
1 / 4 · Geometry
Next
Polygon Area — Shoelace Formula
→