Line Sweep & Segment Intersection

A line sweep imagines a vertical line gliding across the plane from left to right, pausing only at the interesting x-coordinates — here, the endpoints of some segments. Instead of testing every pair of segments (O(n²)), you keep a small active set of the segments the line currently crosses, ordered top to bottom, and only ever compare neighbors in that order. That is enough to decide whether any two segments intersect.

The classic problem: does any pair of n segments intersect? A brute-force check is O(n²); the sweep brings it down to O(n log n), the same idea behind the full Bentley–Ottmann algorithm.

Intuition

Picture a vertical ruler dragged across the page. At any instant it slices through some of the segments; reading those crossings top to bottom gives an ordered list — the active set. As the ruler moves, that order only changes at three kinds of moments: a segment begins (enters the list), a segment ends (leaves the list), or two segments swap places because they crossed.

That last case is the whole point. If two segments cross, then just before the crossing they sit next to each other in the active order, and just after they have flipped. So you never need to compare far-apart segments — a crossing always announces itself between neighbors. Each time you insert a new segment, checking the one directly above and the one directly below it is sufficient.

Walk through it

Step through the animation on the right. Four segments are drawn; the dashed sweep line moves left to right, and active (bottom-left) lists the segments it currently crosses, ordered by height.

First the sweep opens S0, then S1 — at that point the active order is S0 above S1, and testing S1 against its only neighbor S0 finds no crossing. Then the sweep reaches the left end of S2. Inserting S2 by its height drops it between S0 and S1, so its neighbors are S0 above and S1 below. Testing S2 against S0 is clear, but testing S2 against S1 shows their order flips further right — they cross. The pair lights up in red and we stop early: the answer is YES, without ever touching S3.

If no pair had crossed, the sweep would keep going — removing each segment at its END event (which makes its former neighbors adjacent, the next thing worth testing) until the events run out and the answer is NO.

The code, line by line

def any_intersection(segments):
    events = []
    for s in segments:
        events.append((min(s.x1, s.x2), "start", s))
        events.append((max(s.x1, s.x2), "end", s))
    events.sort()                       # by x, then end before start
    active = []                         # ordered by y at the sweep
    for x, kind, s in events:
        if kind == "start":
            i = insert_sorted(active, s, x)
            for nb in (above(active, i), below(active, i)):
                if nb and crosses(s, nb):
                    return True         # found a crossing pair
        else:
            active.remove(s)            # neighbors become adjacent
    return False

• Lines 2–5 turn each segment into two events — a START at its smaller x and an END at its larger x.
• Line 6 sorts events by x; ties resolve END before START so a closing segment leaves the active set before a new one opens at the same x.
• Line 7 keeps active ordered by each segment's y at the current sweep position (a balanced BST in a real implementation, so insert and neighbor lookups are O(log n)).
• Lines 9–10 handle a START: insert the segment in y-order, then look at the neighbor directly above and directly below it.
• Lines 11–12 are the only geometry test — crosses(s, nb) checks whether s and an adjacent segment intersect; the first hit returns True.
• Lines 13–14 handle an END by removing the segment, which makes its former neighbors adjacent so they get compared on a later event.

Complexity

Sorting the 2n events dominates at O(n log n). Each event does an O(log n) insert or remove in a balanced BST and a constant number of neighbor comparisons, so the sweep itself is also O(n log n). That beats the O(n²) brute force of comparing every pair. (Reporting all k intersections, not just the first, costs O((n + k) log n) with the full Bentley–Ottmann sweep.)

When to use / pitfalls

Practice