Given two line segments, do they cross? Every other entry in this site's Geometry and
Convex Hull categories processes a whole point set —
O(n log n) or worse. This question is answerable for a single pair of segments in a
fixed number of steps, no sorting or recursion involved: O(1), the first entry on this
site with that as its actual top-line complexity rather than a per-step cost inside a larger loop.
The primitive is the same cross product
Graham Scan and the rest of Convex Hull are built on —
cross(o, a, b), whose sign says which way the path o → a → b turns. Convex
Hull uses that turn direction to decide which points survive onto a boundary. This page uses the
exact same sign test for a different purpose: two segments cross if and only if each one's
endpoints are turned opposite ways by the other segment's line — straddling it, not sitting
on one side.
Six fixed cases, picked to cover the general rule and every special case it doesn't handle on its
own. Segment A–B and segment C–D are drawn on the canvas; the
orientation values o1–o4 and the verdict are computed live from their
actual coordinates, not hand-authored per case. bbox overlap ≠ intersect is the one
to watch first — both segments' bounding boxes clearly overlap, but the segments themselves pass
each other without crossing.
Four orientation tests decide the general case: o1 = orientation(A, B, C),
o2 = orientation(A, B, D), o3 = orientation(C, D, A),
o4 = orientation(C, D, B). If segment A–B has C on one side and D on the other
(o1 ≠ o2), and segment C–D has A on one side and B on the other
(o3 ≠ o4), the two segments must cross — each one's line genuinely separates the
other's endpoints, and two finite segments doing that to each other can only happen at a single
shared point. If either pair of orientations matches, one segment's endpoints sit entirely on one
side of the other's line (or on it), and there is no crossing to find in the general case.
That leaves the case any orientation call returns exactly zero: three collinear
points. Zero doesn't mean intersecting — it means the fourth point sits somewhere
on the infinite line through the other two, which could be anywhere along it, including far past
either endpoint. Confirming an actual overlap needs a second check, onSegment: given
three collinear points, is the middle one inside the bounding box of the other two? Bounding-box
containment is a sound test for collinear points specifically (they can only vary in one direction),
even though it's unsound in general — see the first Pitfall below for exactly how unsound. A shared
endpoint alone doesn't force this path: two segments meeting at a corner, pointed in different
directions, are almost always resolved by the general rule above without onSegment ever
running — the shared point contributes a zero that's simply unequal to whatever nonzero value the
far endpoint gets. The special case only becomes load-bearing when all four points sit on
one infinite line — this page's "collinear, touching at a point" case is the minimal example: every
one of o1 through o4 comes back zero, so the general rule can't tell it
apart from "collinear, disjoint" at all, and onSegment is the only thing left that can.
Coordinate-system note, same caveat Graham
Scan already had to make explicit: this page's canvas has y increasing downward, like
every pixel-based coordinate system, so the raw sign of o1–o4 below reads
as visually flipped from the textbook "positive = counterclockwise" convention. It doesn't matter
here — the algorithm only ever asks whether two orientations match, never which specific
way something turns — but it's the same detail worth stating rather than leaving implicit.
function cross(o, a, b) {
return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}
function orientation(p, q, r) {
const val = cross(p, q, r);
if (val === 0) return 0; // collinear
return val > 0 ? 1 : 2; // 1 or 2 — which way doesn't matter, only whether it matches
}
function onSegment(p, q, r) {
// p, q, r already known collinear — is q within the bounding box of p and r?
return q.x <= Math.max(p.x, r.x) && q.x >= Math.min(p.x, r.x) &&
q.y <= Math.max(p.y, r.y) && q.y >= Math.min(p.y, r.y);
}
function segmentsIntersect(a, b, c, d) {
const o1 = orientation(a, b, c);
const o2 = orientation(a, b, d);
const o3 = orientation(c, d, a);
const o4 = orientation(c, d, b);
if (o1 !== o2 && o3 !== o4) return true; // general case
// collinear special cases — each endpoint checked against the opposite segment
if (o1 === 0 && onSegment(a, c, b)) return true;
if (o2 === 0 && onSegment(a, d, b)) return true;
if (o3 === 0 && onSegment(c, a, d)) return true;
if (o4 === 0 && onSegment(c, b, d)) return true;
return false;
}Bounding-box overlap is not intersection. This page's own "bbox overlap ≠
intersect" case is a direct counter-example: segment A–B and segment C–D have clearly overlapping
bounding rectangles — a naive check that stops at "do the boxes overlap" would call it a match — but
the actual segments pass on either side of each other and never touch, confirmed by o1 = o2 =
2 (both C and D fall on the same side of line A–B). Bounding-box overlap is a cheap
necessary pre-filter worth keeping before the real test on a large set of segments — two
segments that don't cross always have non-overlapping boxes — but it is never sufficient on its own.
Skipping the collinear special cases loses real intersections, silently. The
general rule alone (o1 ≠ o2 && o3 ≠ o4) returns false for both this page's
"collinear, touching at a point" and "collinear, overlapping" cases — all four orientations come
back exactly zero, so neither inequality ever holds, and a version that only implements the general
case reports no intersection for two segments that plainly do touch. Worse, checking only the first
segment's two special cases (o1/o2) and dropping the second segment's
(o3/o4) still passes both of those visible cases but silently fails a
degenerate one: a single point (a segment with equal endpoints) sitting exactly on the
interior of another segment. Confirmed directly — a point at the midpoint of a horizontal
segment, checked against a version of segmentsIntersect missing its o3/
o4 checks, returns false; the correct answer, and what all four checks
together return, is true. The asymmetry is real: onSegment(a, c, b) tests
against segment A–B's own bounding box, which collapses to a single point when A equals B, so it
can only ever confirm a match when the query point lands on that exact point — it's segment C–D's
own check, run from the other direction, that actually catches it.
Time: O(1) — four fixed cross-product evaluations, each
O(1), plus at most four O(1) bounding-box checks. No sorting, no
recursion, no dependence on any other point in the scene, unlike every other entry in this site's
Geometry or Convex Hull categories. Space: O(1), a handful of scalar
comparisons. The harder, genuinely different problem — given n segments, find every
intersecting pair, not just decide one pair — needs more than n²/2 repeated calls to
this test to do better than the brute-force O(n²) that implies; a sweep-line algorithm,
Bentley–Ottmann, solves it in
O((n + k) log n) where k is the number of intersections found, by only
ever testing pairs of segments once they become adjacent along the sweep — a different algorithm
built on top of this one's O(1) test as its core primitive.
This site's guide, Choosing a Geometry Algorithm, places this entry as the answer to whether one specific pair of segments crosses — reach for Bentley–Ottmann instead the moment the question is which pairs among many segments cross.