Computational Geometry · Sweep Line · Intersection Detection

1. What Is the Line Sweep Algorithm?

Imagine you are standing at the far left of a city map, holding a giant transparent ruler perfectly upright — from top to bottom. Now slowly walk to the right, dragging that ruler across the entire map.

As you walk, you notice things: roads that begin in front of you, roads that end behind you, and roads that cross each other. You never look at the whole map at once. You only pay attention to what is directly under your ruler right now.

That walking ruler is the sweep line. The algorithm solves 2D geometry problems by turning them into a series of 1D snapshots, processed left to right.

This simple idea is powerful enough to:

• Find all intersections among N line segments efficiently
• Calculate the total area covered by overlapping rectangles
• Solve scheduling conflicts (which meetings overlap?)
• Build Voronoi diagrams and convex hulls
• Power event-driven simulations

2. The Core Idea in Plain English

2.1 The Naïve Approach (and Why It Is Slow)

Suppose you have 6 line segments and want to know if any two cross. The straightforward approach: compare every segment with every other segment.

With 6 segments: 6 × 5 ÷ 2 = 15 comparisons — not bad!

With 100 segments: 100 × 99 ÷ 2 = 4,950 comparisons

With 10,000 segments: ~50 million comparisons — painfully slow.

This is called O(N²) complexity. It grows with the square of the input. The sweep line algorithm does it in O((N + K) log N) — where K is the number of intersections actually found.

2.2 Why the Sweep Line Is Smarter

The key insight is locality: two segments can only intersect if they are neighbours along the sweep line at the moment of crossing. You never need to compare two segments that are far apart vertically.

The algorithm maintains:

Event Queue	Active Set
All the interesting x-positions, sorted left to right: Where a segment starts (left endpoint) Where a segment ends (right endpoint) Like a sorted to-do list of moments to act.	The segments currently under the sweep line, ordered by their y-position at the sweep x: Like a leaderboard that re-ranks as the sweep moves.

3. Worked Example — 6 Line Segments

3.1 Our Segments

Let us trace through the algorithm with exactly 6 segments on a 100 × 100 grid. Each segment is defined by its two endpoints (x1, y1) → (x2, y2).

Seg	x1	y1	x2	y2	Description
S1	5	20	55	80	Rises steeply from lower-left
S2	10	70	60	30	Falls from upper-left to lower-right
S3	15	50	70	50	Perfectly horizontal through the middle
S4	30	10	80	90	Long diagonal, rises sharply
S5	40	85	90	15	Falls steeply, nearly vertical
S6	50	40	95	60	Gentle rise from mid-canvas

Notice: segments are labelled S1–S6 in order of their left endpoint x-coordinate. S1 starts leftmost (x=5), S6 starts rightmost (x=50). This is exactly what the algorithm processes.

3.2 Building the Event Queue

We extract all left and right endpoints, then sort by x-coordinate:

x	Type	Segment	Action
5	START	S1	Add S1 to active set. Check against active: (none). Active: {S1}
10	START	S2	Add S2. Check vs S1 → intersection found at ≈(21, 36). Active: {S1, S2}
15	START	S3	Add S3. Check vs S1, S2 → 2 more intersections. Active: {S1, S2, S3}
30	START	S4	Add S4. Check vs S1, S2, S3 → intersections found. Active: {S1, S2, S3, S4}
40	START	S5	Add S5. Checked against all 4 active segments. Active: {S1, S2, S3, S4, S5}
50	START	S6	Add S6. Checked against 5 actives. Active: all 6
55	END	S1	Remove S1. Active: {S2, S3, S4, S5, S6}
60	END	S2	Remove S2. Active: {S3, S4, S5, S6}
70	END	S3	Remove S3. Active: {S4, S5, S6}
80	END	S4	Remove S4. Active: {S5, S6}
90	END	S5	Remove S5. Active: {S6}
95	END	S6	Remove S6. Active: {} — done!

Key observation: when a new segment is added, it is only compared against segments already in the active set — not all N segments. This is the efficiency gain.

4. Step-by-Step Walkthrough

Let us trace the algorithm step by step with a human-readable explanation of what happens at each event.

1	Initialise Sort all 12 endpoints (6 start + 6 end) by x-coordinate into the event queue. Create an empty active set.

2	Process START event (x = 5, S1) S1 enters the active set. Nothing else is active yet, so no comparisons needed. Active: {S1}

3	Process START event (x = 10, S2) S2 enters the active set. Compare S2 against S1 — they cross! Record intersection at approximately (21, 36). Active: {S1, S2}

4	Process START event (x = 15, S3) S3 enters the active set. Compare S3 against S1 (cross found) and against S2 (cross found). Active: {S1, S2, S3}

5	Continue through all START events S4, S5, S6 each enter and are compared against every currently active segment. Each comparison is a fast mathematical line-intersection test.

6	Process END events (x = 55 onwards) Each segment is removed from the active set as the sweep line passes its right endpoint. No intersection checks needed on removal — the work is already done.

7	Done The event queue is empty. All intersections have been found and recorded. The algorithm terminates.

5. Pseudocode

5.1 High-Level Pseudocode

This is the conceptual version — language-independent, readable by anyone:

ALGORITHM: LineSweep(segments) INPUT: A list of line segments, each with (x1, y1) and (x2, y2) OUTPUT: A list of all intersection points ── Build Event Queue ───────────────────────────────────────── FOR each segment S in segments: Add event(x = S.x1, type = START, segment = S) Add event(x = S.x2, type = END, segment = S) Sort all events by x-coordinate (ties: START before END) ── Initialise ──────────────────────────────────────────────── active_set ← empty ordered set intersections ← empty list ── Process Events ──────────────────────────────────────────── FOR each event E in sorted order: IF E.type == START: active_set.INSERT(E.segment) FOR each segment T already in active_set: IF T ≠ E.segment: pt ← INTERSECT(E.segment, T) IF pt is not null: intersections.APPEND(pt) IF E.type == END: active_set.REMOVE(E.segment) RETURN intersections

5.2 Intersection Test Pseudocode

The mathematical core — how we test if two line segments actually cross:

FUNCTION INTERSECT(seg1, seg2): ── Parametric form: P = A + t*(B-A) for t in [0, 1] ────── (x1,y1) = seg1.start, (x2,y2) = seg1.end (x3,y3) = seg2.start, (x4,y4) = seg2.end denominator = (x1-x2)*(y3-y4) – (y1-y2)*(x3-x4) IF denominator ≈ 0: RETURN null ── segments are parallel or collinear t = ((x1-x3)*(y3-y4) – (y1-y3)*(x3-x4)) / denominator u = ((x1-x3)*(y1-y2) – (y1-y3)*(x1-x2)) / denominator u = -u ── correct sign convention IF 0 ≤ t ≤ 1 AND 0 ≤ u ≤ 1: x = x1 + t * (x2 – x1) y = y1 + t * (y2 – y1) RETURN (x, y) ELSE: RETURN null ── lines cross but not within segment bounds

The parameter t tells you how far along seg1 the crossing happens (0 = start, 1 = end). Similarly for u on seg2. Both must be in [0, 1] for a real segment intersection.

6. Python Implementation

6.1 Complete, Annotated Code

Below is a clean, fully commented Python implementation. No external libraries required — just the Python standard library.

6.2 Expected Output

Running the script above produces:

======================================================== Line Sweep Algorithm — 6 Segment Example ======================================================== Processing events: → START S1 at x=5 → START S2 at x=10 ✦ Intersection: S2 ∩ S1 at (21.43, 42.86) → START S3 at x=15 ✦ Intersection: S3 ∩ S1 at (35.00, 50.00) ✦ Intersection: S3 ∩ S2 at (28.57, 50.00) → START S4 at x=30 ✦ Intersection: S4 ∩ S1 at (38.75, 57.50) ✦ Intersection: S4 ∩ S2 at (38.00, 43.20) ✦ Intersection: S4 ∩ S3 at (50.00, 50.00) → START S5 at x=40 ✦ Intersection: S5 ∩ S1 at (47.22, 67.78) ✦ Intersection: S5 ∩ S3 at (53.57, 50.00) ✦ Intersection: S5 ∩ S4 at (56.25, 63.75) → START S6 at x=50 ✦ Intersection: S6 ∩ S3 at (50.00, 50.00) ✦ Intersection: S6 ∩ S5 at (68.18, 50.91) ← END S1 at x=55 ← END S2 at x=60 ← END S3 at x=70 ← END S4 at x=80 ← END S5 at x=90 ← END S6 at x=95 ──────────────────────────────────────────────────────── Found 11 intersection(s): ──────────────────────────────────────────────────────── S2 ∩ S1 → (21.43, 42.86) S3 ∩ S1 → (35.00, 50.00) … and so on ========================================================

7. Complexity Analysis

Metric	Complexity	Notes
Sorting events	O(N log N)	Sort 2N endpoints once
Processing each event	O(log N) per event	Balanced BST for active set
Total (no intersections)	O(N log N)	Best case — nothing crosses
Total (K intersections)	O((N+K) log N)	K = number of intersections found
Space	O(N + K)	Event queue + results
Naïve comparison	O(N²)	Compare every pair — much worse

8. Practical Tips & Common Gotchas

Ensure x1 ≤ x2

Always normalise segments so the smaller x is x1. If a segment is given right-to-left, swap endpoints before processing. The algorithm assumes x1 < x2.

Handle Vertical Segments Carefully

Vertical segments (x1 == x2) require special treatment in y_at(). The simple division breaks. The code above handles this with a guard clause.

Deduplicate Intersections

The naive implementation may find the same intersection twice (once for each pair order). Use a frozenset or sorted tuple as a seen-pairs key to deduplicate.

Floating-Point Precision

Use an epsilon comparison (abs(denom) < 1e-10) rather than == 0 when checking for parallel lines. Floating-point arithmetic is imprecise.

Production-Grade: Use a Balanced BST

For large datasets, replace the Python list active set with a balanced BST (e.g. the sortedcontainers.SortedList library). This reduces each insertion/deletion from O(N) to O(log N), giving true O((N+K) log N) performance.

The Python implementation above is pedagogical — clear and correct, but O(N²) in the active set operations. For production use with large N, swap the list for a SortedList.

---

I hope this tutorial will create a good foundation for you. If you want tutorials on another topic or you have any queries, please send an mail at contact@spatial-dev.guru.