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.

How Line Intersection Algorithms Actually Work

Line intersection algorithms determine whether two line segments cross in 2D space and compute the exact intersection point. The core mechanic is solving the parametric equations of each segment: P = A + t(B - A) and Q = C + u(D - C). The intersection exists when 0 ≤ t ≤ 1 and 0 ≤ u ≤ 1, meaning both points lie within their respective segments. This is fundamentally an orientation test using cross products, not slope-intercept math.

In practice, the algorithm relies on orientation predicates: given three points, do they form a clockwise, counterclockwise, or collinear turn? Two segments intersect only if their orientations are opposite (or one is collinear and the other straddles). The cross product sign is the key — but floating-point precision makes exact collinearity detection unreliable. A tolerance (epsilon) of 1e-9 or 1e-12 is standard, but too large an epsilon introduces false positives.

Use this algorithm whenever you need to detect polygon self-intersection, compute boolean operations on shapes, or validate geometry in GIS or CAD systems. It's O(1) per segment pair, but naive O(n²) checks on all pairs in a polygon with n vertices can be slow. Spatial indexing (e.g., sweep-line, R-tree) reduces this to O(n log n). The real-world cost of a missed or false intersection is a corrupted polygon that breaks downstream rendering or physics engines.

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)

The Naive Approach — Pairwise Hell

You could check every segment against every other segment. That's O(n²). For small datasets—say, under 50 segments—it works fine. For anything larger, it's a death sentence.

The logic itself is simple: for each pair, run the orientation test on both endpoints. If the orientations are opposite (or collinear with overlapping ranges), they intersect. That check is O(1). So the whole thing is O(n²) time, O(1) space. No mystery.

Here's the truth: the naive approach isn't stupid, it's honest. It tells you exactly when you're in over your head. If your geometry engine handles 100K segments and you use this, you'll be watching a monitor go orange at 2 AM. Sweep line exists for a reason.

// io.thecodeforge — dsa tutorial

public class PairwiseIntersection {
    static boolean onSegment(int[] p, int[] q, int[] r) {
        return q[0] <= Math.max(p[0], r[0]) && q[0] >= Math.min(p[0], r[0]) &&
               q[1] <= Math.max(p[1], r[1]) && q[1] >= Math.min(p[1], r[1]);
    }

    static int orientation(int[] p, int[] q, int[] r) {
        int val = (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1]);
        if (val == 0) return 0;
        return (val > 0) ? 1 : 2;
    }

    static boolean intersect(int[] a1, int[] a2, int[] b1, int[] b2) {
        int o1 = orientation(a1, a2, b1);
        int o2 = orientation(a1, a2, b2);
        int o3 = orientation(b1, b2, a1);
        int o4 = orientation(b1, b2, a2);

        if (o1 != o2 && o3 != o4) return true;
        if (o1 == 0 && onSegment(a1, b1, a2)) return true;
        if (o2 == 0 && onSegment(a1, b2, a2)) return true;
        if (o3 == 0 && onSegment(b1, a1, b2)) return true;
        if (o4 == 0 && onSegment(b1, a2, b2)) return true;
        return false;
    }

    public static void main(String[] args) {
        int[][] seg1 = {{1, 5}, {4, 5}};
        int[][] seg2 = {{2, 5}, {10, 1}};
        System.out.println(intersect(seg1[0], seg1[1], seg2[0], seg2[1]));
    }
}

Sweep Line — The Only Algorithm You Need

The sweep line algorithm changes the game from O(n²) to O(n log n). Here's how it works: imagine a vertical line sliding from left to right across your plane. As it moves, it maintains a list of 'active' segments—those currently crossing the sweep line, sorted by their Y-coordinate at the current X.

The key insight: intersections only happen between segments that are neighbors in this sorted order. So instead of checking every pair, you only check pairs that become adjacent as the sweep line passes. When a new segment enters, you test it against its immediate neighbors. When one leaves, you test the neighbors against each other.

You need a balanced BST or a similar structure for the active set. In Java, that's TreeMap with a custom comparator—but careful, floating point comparisons will bite you. Use integer arithmetic or epsilon-tolerant comparisons.

For line segments (not infinite lines), you also need to handle endpoint events: when the sweep line hits a left endpoint, insert the segment; when it hits a right endpoint, remove it. Insertion and neighbor queries are O(log n) each.

// io.thecodeforge — dsa tutorial

import java.util.*;

public class SweepLineEngine {
    static class Event implements Comparable<Event> {
        int x, y, segIdx, type; // 0 = left, 1 = right
        Event(int x, int y, int idx, int t) {
            this.x = x; this.y = y; this.segIdx = idx; this.type = t;
        }
        public int compareTo(Event o) {
            if (this.x != o.x) return this.x - o.x;
            return this.y - o.y;
        }
    }

    public static void main(String[] args) {
        // dummy: shows skeleton. Real impl needs comparator with sweep X context
        System.out.println("Sweep line skeleton ready");
    }
}

Orientation of Three Points — The 2D Gut Check

Orientation is the foundation of everything here. Given three points A, B, C, orientation tells you if C is to the left, right, or collinear with the directed line AB. It's a cross product sign test, no trigonometry needed.

The formula: (B.y - A.y) (C.x - B.x) - (B.x - A.x) (C.y - B.y). If positive -> counterclockwise (left turn). Negative -> clockwise (right turn). Zero -> collinear.

Why this works: the cross product of vectors AB and BC gives twice the signed area of triangle ABC. If the area is positive, C is left of AB. That's it. No floating point errors if you use integers.

Collinear cases are the ugly part. When orientation is zero, you need an extra containment check: does point C lie within the bounding box of AB? That's onSegment(). Without it, you'll miss intersections where segments share an endpoint or overlap partially.

// io.thecodeforge — dsa tutorial

public class OrientationTest {
    static int orientation(int[] a, int[] b, int[] c) {
        int cross = (b[1] - a[1]) * (c[0] - b[0]) - (b[0] - a[0]) * (c[1] - b[1]);
        if (cross > 0) return 1;  // counterclockwise
        if (cross < 0) return 2;  // clockwise
        return 0;                 // collinear
    }

    static boolean onSegment(int[] a, int[] b, int[] c) {
        return b[0] <= Math.max(a[0], c[0]) && b[0] >= Math.min(a[0], c[0]) &&
               b[1] <= Math.max(a[1], c[1]) && b[1] >= Math.min(a[1], c[1]);
    }

    public static void main(String[] args) {
        int[] a = {0, 0}, b = {10, 10}, c = {5, 5};
        int orient = orientation(a, b, c);
        System.out.println("Orientation: " + orient + " (0=collinear)");
        System.out.println("On segment: " + onSegment(a, b, c));
    }
}

Graham Scan — Convex Hull in O(n log n)

Why care? Line intersection algorithms often assume you already know which segments are relevant. The Graham Scan eliminates irrelevant points by computing the convex hull — the smallest convex polygon containing all points. This is foundational: any line that doesn't intersect the hull never intersects the points inside it. Graham Scan works by first finding the lowest-y point (pivot), then sorting all other points by polar angle relative to that pivot. It scans the sorted list, maintaining a stack. For each new point, it checks orientation of the last two stack points and the new point — if the turn is clockwise (right turn), the middle point is inside the hull and gets popped. Only counter-clockwise turns stay. The result is a tight boundary you can feed directly into sweep-line algorithms. The critical nuance: collinear points on hull edges require special handling — either keep them for precision or discard them depending on whether you need minimal hull. This single pass after sorting gives O(n log n) total, beating naive pairwise methods.

// io.thecodeforge — dsa tutorial

import java.util.*;

class Point { int x, y; Point(int x, int y) { this.x = x; this.y = y; } }

public class GrahamScan {
    static int orientation(Point p, Point q, Point r) {
        int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
        if (val == 0) return 0; // collinear
        return (val > 0) ? 1 : 2; // cw or ccw
    }

    static List<Point> convexHull(Point[] pts) {
        int n = pts.length;
        if (n < 3) return new ArrayList<>();
        Arrays.sort(pts, (a, b) -> a.y != b.y ? a.y - b.y : a.x - b.x);
        Arrays.sort(pts, 1, n, (a, b) -> {
            int o = orientation(pts[0], a, b);
            if (o == 0)
                return (dist(pts[0], a) - dist(pts[0], b)) > 0 ? 1 : -1;
            return (o == 2) ? -1 : 1;
        });
        Stack<Point> stack = new Stack<>();
        stack.push(pts[0]); stack.push(pts[1]);
        for (int i = 2; i < n; i++) {
            while (stack.size() > 1 && orientation(stack.get(stack.size()-2), stack.peek(), pts[i]) != 2)
                stack.pop();
            stack.push(pts[i]);
        }
        return new ArrayList<>(stack);
    }
}

Chand–Kapur Algorithm — Avoiding Degenerate Sorting Perils

Why this matters? The Graham Scan's polar sort fails when points share the same angle (collinear with pivot) or when the convex hull has multiple collinear boundary points. Chand–Kapur (also called the Tentative Hull algorithm) fixes this by skipping the angle sort entirely. Instead, it builds the hull incrementally by traversing the sorted-by-x points and maintaining an upper and lower chain separately. For each chain, you push points and check orientation — if a right turn occurs, you pop the middle point. This avoids the collinear-angle ambiguity because you process points in monotonic x-order. The critical insight: process left-to-right for the upper hull, right-to-left for the lower hull. No angle computation, no floating-point. This makes Chand–Kapur more robust for integer coordinates and avoids edge-case crashes common in competitive programming. Complexity remains O(n log n) from sorting by x, but the constant is lower because you skip the angle comparison. Use this when your input contains many collinear points or when you need exact integer output without rounding errors.

// io.thecodeforge — dsa tutorial

import java.util.*;

class Point { int x, y; Point(int x, int y) { this.x = x; this.y = y; } }

public class ChandKapur {
    static int cross(Point o, Point a, Point b) {
        return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
    }

    static List<Point> hull(Point[] pts) {
        Arrays.sort(pts, (a, b) -> a.x != b.x ? a.x - b.x : a.y - b.y);
        List<Point> lower = new ArrayList<>();
        for (Point p : pts) {
            while (lower.size() >= 2 && cross(lower.get(lower.size()-2), lower.get(lower.size()-1), p) <= 0)
                lower.remove(lower.size()-1);
            lower.add(p);
        }
        List<Point> upper = new ArrayList<>();
        for (int i = pts.length-1; i >= 0; i--) {
            while (upper.size() >= 2 && cross(upper.get(upper.size()-2), upper.get(upper.size()-1), pts[i]) <= 0)
                upper.remove(upper.size()-1);
            upper.add(pts[i]);
        }
        lower.addAll(upper.subList(1, upper.size()-1));
        return lower;
    }
}