Line Segment Intersection, this site's
other O(1) entry, decides whether one pair of segments crosses. Given n
segments and asked to find every crossing pair, the obvious move is to run that same
O(1) test on all n(n − 1) / 2 pairs — O(n²) total, and that
page's own Complexity section names this exact algorithm as the way to do better without changing
what "better" costs per pair. Bentley–Ottmann finds every intersection in
O((n + k) log n), where k is the number of intersections actually found —
faster than checking all pairs whenever k is small relative to n², which
is the common case for segments that mostly don't cross.
The idea is a sweep line: an imaginary vertical line moving left to right across the plane. At any fixed sweep position, the segments it currently crosses have a well-defined top-to-bottom order — call this the status structure. That order only ever changes at one of three moments: a segment starts (enters the sweep), a segment ends (leaves the sweep), or two active segments cross (swap places in the order). Between those moments nothing changes, so nothing needs re-checking — the algorithm only does work at these events, processed left to right from an event queue, instead of continuously scanning the whole plane.
Five segments, six real crossings among them — a deliberately dense example, picked to make the
mechanism visible (every kind of event fires at least once) rather than to show off
a pair-test count lower than brute force's fixed C(5,2) = 10. It doesn't come out
ahead here — watch the pair-test counter below climb past 10 before the sweep finishes — because
with 6 of the 10 possible pairs genuinely crossing, this is close to the algorithm's own worst case
(see Complexity). The real savings show up at larger n with proportionally fewer
crossings; the Pitfalls section below has a measured 80-segment case where the difference is stark.
Step through and watch the status structure strip below the canvas: it always lists
exactly the segments the dashed sweep line currently crosses, top to bottom. Every event — start,
end, or intersection — is computed live from the five segments' real coordinates by the same
sweep() function described below, not scripted per step. Watch B×D at
x=150 closely: D is a short horizontal segment sitting between B and A when the sweep
starts, and it's only once D ends and drops out of the status structure that B and A — now
newly adjacent — get checked against each other at all.
The event queue starts with just 2n events — every segment's left endpoint (a
"start") and right endpoint (an "end") — sorted by x. Intersection events aren't known
up front; they get discovered and scheduled during the sweep, which is the mechanism that
makes this efficient rather than exhaustive. Whenever two segments become adjacent in the status
structure — freshly inserted next to each other, or left newly next to each other after something
between them is removed — the algorithm checks that one pair, and only that pair, for a future
crossing. If they do cross further right than the current sweep position, that crossing is pushed
onto the event queue as a future event, to be handled exactly when the sweep line reaches it.
This is sound because of a standard exchange argument: two segments cannot cross without, at the
moment they cross, being adjacent in the status structure. If they weren't adjacent, some third
active segment would sit between them — and a continuous curve can't swap sides of another
continuous curve without crossing it first, so that in-between segment would have to cross one of
the two first, which is itself a crossing the algorithm would have already scheduled and processed
as an event before this one. So working strictly through the event queue in x order,
testing only pairs that are freshly adjacent right now, never misses a crossing — it just defers
discovering it until the two segments in question are actually next to each other.
Each event type needs exactly one adjacency re-check, no more: a start checks
the new segment against its one new neighbor above and one below; an end checks
whatever two segments the removed one used to separate, now possibly neighbors themselves; an
intersection swaps the two crossing segments' order and checks each one against its
new outer neighbor. Every one of these is a fixed, small number of pair-tests per event — the whole
reason the total stays proportional to n + k instead of n².
Simplified for non-vertical segments in general position (see Pitfalls for what that leaves out). The status structure below is a plain sorted array for clarity — see Complexity for what that costs against the algorithm's real bound:
function sweep(segments) {
let events = [];
segments.forEach(s => {
events.push({ x: s.p1.x, type: 'start', seg: s.label });
events.push({ x: s.p2.x, type: 'end', seg: s.label });
});
events.sort((a, b) => a.x - b.x);
let T = []; // status structure: labels, top-to-bottom, at the current sweep x
const scheduled = new Set();
const found = [];
function testPair(a, b, sweepX) {
if (!a || !b) return;
const key = [a, b].sort().join('|');
if (scheduled.has(key)) return;
const pt = segIntersection(byLabel[a], byLabel[b]);
if (pt && pt.x > sweepX) {
events.push({ x: pt.x, type: 'intersection', seg: [a, b] });
events.sort((e1, e2) => e1.x - e2.x);
scheduled.add(key);
}
}
while (events.length) {
const ev = events.shift();
if (ev.type === 'start') {
const idx = insertionIndex(T, ev.seg, ev.x); // by y at ev.x
T.splice(idx, 0, ev.seg);
testPair(T[idx - 1], T[idx], ev.x);
testPair(T[idx], T[idx + 1], ev.x);
} else if (ev.type === 'end') {
const idx = T.indexOf(ev.seg);
const above = T[idx - 1], below = T[idx + 1];
T.splice(idx, 1);
testPair(above, below, ev.x); // newly adjacent, if both exist
} else {
const [a, b] = ev.seg;
const lo = Math.min(T.indexOf(a), T.indexOf(b));
const hi = lo + 1;
[T[lo], T[hi]] = [T[hi], T[lo]]; // crossing flips their order
found.push({ pair: [a, b], x: ev.x });
testPair(T[lo - 1], T[lo], ev.x);
testPair(T[hi], T[hi + 1], ev.x);
}
}
return found;
}Skipping the end-event re-check silently drops real intersections. A version that
only re-checks adjacency on start and intersection events — reasoning "removal only
shrinks the structure, what's there to check" — misses crossings that only become discoverable once
something between them is gone. Verified directly with three segments: A from
(40,280) to (260,200), B from (240,180) to
(380,240), C from (200,220) to (460,180). The
correct sweep finds both real crossings, A×C at x≈208.7 and
B×C at x≈298.1 — matching an independent brute-force check of all three
pairs. Drop the end-event check and B×C disappears: at x=240 when
B starts, the status structure is [B, A, C] — B and
C aren't adjacent, A sits between them. Only at x=260, when
A ends and the structure becomes [B, C], do they become adjacent for the
first time — and a version that never re-checks on removal never schedules the test that would have
found the crossing sitting at x≈298.1, well past where the two segments were ever
directly compared.
Checking a new or removed segment against every currently active segment stays correct
but throws away the entire efficiency argument. It's tempting to over-check "to be safe" —
but every active segment is exactly what neighbors-only checking is built to avoid touching.
Measured directly on n long, near-parallel segments (mostly co-active across the whole
sweep, so only a handful genuinely cross): at n = 80 with k = 20 real
intersections, the neighbors-only version ran 136 pair-tests total, while a
check-against-everything-active variant ran 6,338 — worse than the
3,160 a flat one-time brute-force pass over all C(80,2) pairs would
cost, because the over-checking variant re-tests long-lived segments against the whole structure
repeatedly, once per event, not once per pair. Same output, same correctness — but only one of these
is the algorithm this page is actually about.
Time: O((n + k) log n) when the status structure is backed by a
balanced tree (or skip list) supporting O(log n) insert, delete, and neighbor lookup:
2n start/end events plus k intersection events, each event doing a constant
number of these operations, plus O(log n) to push/pop the event queue itself (a
priority queue, ordered by x). This page's own JavaScript uses a plain sorted
array for the status structure instead — same demo convention as
Dijkstra's Algorithm's array-backed priority queue — so
insertion and removal are O(n) via splice/indexOf rather than
O(log n); the event *count* and *which pairs get tested* are exactly what a
tree-backed version would do, only the per-event cost differs. Space:
O(n + k) for the event queue, O(n) for the status structure. One honest
caveat about the output-sensitive bound itself: if k is close to its
O(n²) ceiling — nearly every pair genuinely crosses — then
O((n + k) log n) becomes O(n² log n), asymptotically worse than
the brute-force O(n²) it's meant to improve on. The algorithm only wins when
k is small relative to n², which is the case it's built for, not every
case.
This site's guide, Choosing a Geometry
Algorithm, places this entry as the answer once the question moves from one pair to which
pairs among n segments cross, built on top of
Line Segment Intersection's own
O(1) test as its core primitive.