Detecting Segment Intersections with Orientation Tests

Testing whether two line segments cross is the primitive beneath polygon self-intersection checks, collision detection, map overlay, and the sweep-line algorithms that report all crossings in a set. It is also a case study in how a simple geometric question turns into a bookkeeping problem the moment segments share endpoints, lie on the same line, or touch without crossing.

Two closed segments in the plane intersect when they have at least one point in common, including endpoints. Two open segments, or a mix of open and closed, give different answers on shared endpoints, and libraries differ on which convention they implement. That ambiguity is worth resolving before writing any code, because the orientation-based test naturally answers the closed version and needs extra work for the others.

Four signs decide the general case

The orientation predicate takes an ordered triple of points and returns the sign of the signed area of the triangle they form. Written as a determinant,

orient(o, a, b) = sign( (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x) )

with positive meaning a counterclockwise turn from o to a to b, negative clockwise, and zero collinear. For segments p1p2 and p3p4, compute four values: d1 = orient(p3, p4, p1), d2 = orient(p3, p4, p2), d3 = orient(p1, p2, p3), and d4 = orient(p1, p2, p4). Each answers a question of the form “which side of this line is that endpoint on”.

The segments cross properly when d1 and d2 have opposite signs and d3 and d4 have opposite signs. The first pair says p3p4 separates p1 from p2; the second says p1p2 separates p3 from p4. Both conditions are necessary and together sufficient for a crossing in the interior of both segments.

The predicate is a determinant of a 3×3 matrix whose last column is all ones, and it is the same quantity that appears in convex hulls by monotone chain. Written as the difference of two products, it is exact when the coordinates are integers small enough that the products do not overflow the accumulator, which is the main reason to keep coordinates integral and to choose the integer width deliberately rather than inheriting whatever the platform gives.

The collinear and touching cases

The four-sign test above answers “no” whenever any d is zero, and that is wrong. A zero means an endpoint lies on the other segment’s supporting line, and the segments may still intersect at that endpoint or overlap along a stretch of line. The complete test adds a bounding-box check for each zero:

• If d1 == 0, p1 lies on the line of p3p4; the segments intersect if p1 is within the bounding box of p3p4.
• If d2 == 0, test p2 against the bounding box of p3p4.
• If d3 == 0 or d4 == 0, test p3 or p4 against the bounding box of p1p2.
• Otherwise, the answer is the proper-crossing test.

Collinear overlap is caught by this rule because at least one endpoint of the shorter segment must lie inside the other’s bounding box, unless the segments are disjoint along the line, in which case no endpoint lies inside and the answer is correctly “no”. A shared endpoint is caught because the shared point is inside both bounding boxes.

/* Closed-segment intersection. Coordinates are int64_t, bounded so the products
   fit in a signed 128-bit accumulator; __int128 is a GCC and Clang extension. */
int orient(int64_t ox, int64_t oy, int64_t ax, int64_t ay, int64_t bx, int64_t by) {
    /* Widen before subtracting: the difference of two int64_t need not fit in int64_t. */
    __int128 v = ((__int128)ax - ox) * ((__int128)by - oy)
               - ((__int128)ay - oy) * ((__int128)bx - ox);
    return (v > 0) - (v < 0);
}

The 128-bit intermediate is not optional, and neither is widening before the subtraction: the difference of two 64-bit coordinates needs 65 bits, so it overflows in int64_t before the cast can help. With 32-bit coordinates the differences reach 2^32 and each product reaches 2^64, which already overflows a signed 64-bit word. With 64-bit coordinates the differences reach 2^64 and the products need close to 128 bits, so the range of coordinates that a signed 128-bit accumulator carries exactly is bounded, and the subtraction of the two products is what consumes the remaining headroom. Silently wrapping the subtraction produces a sign that is not merely imprecise but unrelated to the geometry, and the resulting failures appear as impossible configurations rather than as small errors.

What the all-pairs test costs

Checking every pair is O(n²) predicates. For n = 10^4 segments that is roughly 5×10^7 tests, each a handful of multiplies; the arithmetic is not the problem, the quadratic growth is. Doubling the input quadruples the work, so at n = 10^5 the pair count is already 5×10^9 and it is the quadratic term, not the predicate, that rules the method out for map data or particle simulations.

Two different questions hide under “do these segments intersect”. The decision problem asks whether any pair crosses and can stop at the first hit. The reporting problem asks for all crossing pairs, and its output can itself be quadratic: n/2 horizontal segments crossing n/2 vertical segments produce n²/4 intersections. Any algorithm for the reporting problem must emit the k pairs it reports, and the best lower bound known for the problem is Ω(n log n + k); on this input the output alone is n²/4, so no asymptotic improvement over brute force is possible there.

Between the two lies the useful case where the input is large but the number of crossings is small. There, a sweep line that only examines segments whose x-ranges overlap at the sweep position avoids most of the quadratic work. The Bentley–Ottmann sweep achieves O((n + k) log n) for this case, which is the reason the naive test is a fallback rather than the standard method.

Prefiltering before the predicate

Most pairs in real data are far apart, and the orientation test is more expensive than a comparison. Sorting segments by their minimum x-coordinate and maintaining an active set keyed on maximum x lets the loop skip every segment that ends before the current one begins. That is a one-dimensional sweep and it reduces the constant factor substantially on clustered input without changing the worst case.

A bounding-box test is the other standard filter: two segments whose axis-aligned boxes are disjoint cannot intersect, and the test is four comparisons. Applied first, it rejects the overwhelming majority of pairs on typical spatial data, and it is exact, so it never changes the answer. The ordering of filters matters: cheapest and most selective first, with the exact predicate last.

Consistency between primitives

The most damaging failure is not a wrong answer on one test but an inconsistency between two tests that should agree. A program that uses a floating-point orientation in the intersection test and an exact orientation in the hull construction can produce a polygon whose hull contains a vertex the intersection test claims is outside it. Each primitive is individually plausible and the combination is incoherent.

The remedy is to route every orientation question through a single implementation with a documented semantics, and to make the collinearity threshold explicit rather than emergent. If the implementation is exact for the coordinate type in use, zero means exactly zero and the case analysis above is sound. If it is floating point, “zero” means “within whatever the cancellation left”, and the bounding-box branches will fire on pairs that are not actually collinear, producing false positives. The adaptive exact predicates described in exact geometric predicates exist to make the sign trustworthy at a cost close to that of the floating-point evaluation, and they are the correct foundation for this test whenever the input is not provably small integers.

Degenerate inputs that are not exotic

Zero-length segments occur in real data whenever a polyline repeats a vertex, and they break the four-sign test because all orientations involving the degenerate segment are zero. Treating a zero-length segment as a point and testing point-on-segment against the other one is the consistent fix; letting it fall through the collinear branch usually works by accident but not always, because the bounding box of a zero-length segment is a single point and the containment test then depends on the exact comparison of coordinates.

Overlapping collinear segments are common in data assembled from multiple sources, where shared borders are digitised twice with slightly different vertices. The closed-segment test reports them as intersecting, which is correct, but a caller that wants proper crossings only will see a flood of degenerate hits along every shared boundary. Deciding which of the two questions is being asked, and naming the function accordingly, prevents a class of bugs that are otherwise diagnosed only after the output is plotted.