The idea: sweep a line and test only neighbours
You have n line segments and want every pair that crosses. The obvious way tests all pairs: n(n − 1)/2 tests, even for segments at opposite ends of the picture. The sweep line algorithm of Bentley and Ottmann (1979) moves a vertical line from left to right. At each moment it keeps the segments the line cuts, in order from bottom to top. Two segments can only cross after they sit next to each other in that order, so it only ever tests neighbours.
The page uses segments with whole-number ends on a 20 × 16 grid, chosen so that no two events share an x and no three segments meet in one point. Every number on the canvas can be checked by hand.
Do two segments cross?
This uses the orientation test from the convex hull page: the sign of
cross(a, b, c) = (bx − ax)·(cy − ay) − (by − ay)·(cx − ax)says whether c is left of the line a→b (positive), right of it (negative) or on it (0). Segments s and t cross exactly when both of these hold:
- t's two ends are on opposite sides of the line through s (the two cross values have opposite signs), and
- s's two ends are on opposite sides of the line through t.
Four multiplications-and-subtractions, no division, no square roots. Only when both tests pass is the crossing point worked out, with u = d₃ / (d₃ − d₄) along s (Demo: do two segments cross?). On the page, A and B pass both tests. E's ends are on opposite sides of line F, but F's ends are both on one side of line E, so E and F do not cross, even though they come very close.
Events and the status
The line does not move smoothly; it jumps between events, the only x values where the order can change. They wait in an event queue sorted by x (a priority queue or a balanced tree). The ordered list of cut segments is the status (a balanced search tree keyed by y at the current x).
| Event | What changes | Which pairs are tested |
|---|---|---|
| Left end of s | Insert s into the status, by its y | s with the segment just above, s with the one just below |
| Right end of s | Remove s | The segments that were above and below s: they are neighbours now |
| Crossing of s and t | Report it, swap s and t | Each of the two with its new outer neighbour |
A test that finds a crossing right of the sweep line adds a crossing event to the queue. A crossing left of the line was already handled, and one already in the queue is not added twice (Demo: sweep 6 segments).
A crossing swaps two neighbours
Just left of a crossing, A is below B; just right of it, A is above B. So at the crossing event the two trade places in the status. That gives each of them a new neighbour on its outer side, and those two new pairs are tested.
Why testing neighbours is enough
Take two segments that cross at point P, and suppose no other event lies between them near P. Just left of P, nothing lies between them on the sweep line, so they are neighbours in the status. They became neighbours at some earlier event (an insert, a removal or a swap), and at that event they were tested. So every crossing is put in the queue before the line reaches it.
Cost: brute force vs the sweep
| Segments | n | Crossings k | Brute force tests | Sweep tests |
|---|---|---|---|---|
| 6 crossing segments | 6 | 3 | 15 | 11 |
| 8 segments, 1 crossing | 8 | 1 | 28 | 13 |
There are 2n + k events, each with at most two tests and a few O(log n) tree operations, so the sweep costs O((n + k) log n). Brute force is always O(n²). The sweep wins when crossings are few (Demo: 8 segments, 1 crossing). When almost every pair crosses, k is about n² and brute force is simpler and just as fast.
Where it is used
Map overlay in GIS (where do roads cross rivers?), checking that a polygon does not cross itself, design-rule checks on chip layouts, and Boolean operations on shapes in CAD and vector drawing programs. The same idea, a line sweeping across the plane with a sorted status, also builds the convex hull with Andrew's monotone chain and fills polygons scan line by scan line, as in rasterization. The cross product itself is explained in vectors, the dot product and the cross product.
The same crossing test answers whether a point is inside a polygon: see Point in Polygon.
What the page leaves out
The page leaves out the special cases: vertical segments, endpoints that lie on another segment, overlapping collinear segments and three or more segments through one point. Real code handles them with extra rules and with exact arithmetic, since floating-point crossings can fall in the wrong order. It also skips the balanced trees themselves (the status is drawn as a list) and faster algorithms such as Chazelle–Edelsbrunner, which reach O(n log n + k).
See where this page fits on the Geometric Algorithms mind map.