The Sweep Line
In short: to find a crossing among many segments, you don't have to
check every pair. Sweep a vertical line left to right. At any moment, the
line is only crossing some subset of the segments — the active set —
and that set has a real order: top to bottom, by where each segment
currently sits. Keep the active set sorted (section 14's balanced
structures do this with an O(log n) insert; a sorted list with bisect
is fine here) and test a newly-inserted segment against only its two
neighbours in that order. Anything farther away has a neighbour sitting
between them that would have to cross first. The tested-pair count stays
far below n², because every insertion costs at most two tests, however many
segments are already active.
Three avenues, three cross streets
Meridian has three horizontal avenues and three north-south cross streets. Does any cross street actually meet an avenue?
The three avenues all start at x = 0 and go into the active set together,
ordered by their y-values: [0, 2, 4]. The first cross street starts at
x = 1 and inserts itself between the avenue at y=4 and... nothing above
it, so it's tested only against its immediate neighbour, not all three
avenues. That single test already finds a crossing, and the sweep returns
True immediately — it never even reaches the other two cross streets.
Counting how few pairs get tested
The same six routes, brute force, would check 6 * 5 / 2 = 15 pairs. The
sweep tests far fewer, because it only ever compares adjacent
segments at the moment one is inserted:
5 tests instead of 15 — and the gap only widens as more routes get added, because brute force grows with the square of the route count while the sweep's tests per route stay capped at 2.
Why the active set needs to be ordered
If order were just an unsorted list, "the neighbours" would mean nothing —
you'd be back to testing a new segment against everyone active, which is
brute force again, just delayed. The active set's order has to track the
sweep line's current crossing position, which changes continuously as
segments rise and fall relative to each other. A sorted container — a
balanced tree, a skip list, or (for teaching) a plain list kept sorted with
bisect — is what makes "neighbour" a meaningful, cheap-to-find idea.
Quick practice
import bisect
ys = [0, 2, 4]
pos = bisect.bisect_left(ys, 5)
print(pos)order = [10, 20, 30, 40]
pos = 2
neighbours = []
if pos > 0:
neighbours.append(order[pos - 1])
if pos < len(order) - 1:
neighbours.append(order[pos + 1])
print(neighbours)🎯 Your turn
Build any_intersection(segments): sweep left to right, keep the active set
ordered by current y, and test only neighbours.
- Three avenues plus a crossing street →
True - Three parallel avenues alone →
False []→False
Hint: build (x, 0/1, index) events for every start/end, sort them,
then on a start event use bisect.bisect_left on the active segments'
current y-values to find where to insert, and test only order[pos-1] and
order[pos+1].
Press ▶ Run, try the Live App chips, then ✓ Check.