Sweep Line for Geometry

Quick Revisit
USE WHEN: detecting segment intersections, rectangle union area, or spatial event processing in 2D
INVARIANT: only adjacent segments in the y-ordered active set can intersect
TIME: O(n log n) detect-any; O((n+k) log n) find-all k intersections | SPACE: O(n)
CLASSIC BUG: not checking new neighbors on removal — former neighbors may now intersect each other
PRACTICE: 08-ladder-mixed

Geometric sweep line algorithms -- detecting segment intersections, computing rectangle union areas, and processing spatial events. This is the geometry-specific sibling of the general sweep technique in Chapter 9.

Difficulty: [Advanced]Prerequisites: Geometry Basics, SortingCF Rating Range: 1800 -- 2300

The Geometric Sweep Mindset

The general sweep line idea (process events left-to-right) gets a special flavor in geometry. Instead of intervals on a number line, you're sweeping a vertical line across the plane. The "active set" contains geometric objects currently intersecting the sweep line, ordered by their y-coordinate at the current sweep position.

The key insight: only adjacent objects in the active set can interact. A segment can only intersect its neighbors in the y-ordered active set -- not segments far above or below. This collapses $O (n^{2})$ checks into $O (n \log n)$ neighbor checks.

Segment Intersection Detection

Given $n$ line segments, detect if any two intersect -- or find all $k$ intersections.

Simplified Bentley-Ottmann

The full Bentley-Ottmann finds all $k$ intersections in $O ((n + k) \log n)$ . For contests, a simplified version often suffices: just detect whether any intersection exists, in $O (n \log n)$ .

  Sweep line moves left -> right

  Events:                       Active set (ordered by y):
  --------                      --------------------------
  x=1: segment A starts         { A }
  x=2: segment B starts         { A, B }  <- check A∩B
  x=3: segment A ends           { B }     <- check new neighbors
  x=4: segment C starts         { B, C }  <- check B∩C

  Only check pairs that become adjacent!

Events:

Left endpoint of segment: insert into active set, check against new neighbors (above and below).
Right endpoint of segment: before removing, check if its former neighbors now become adjacent (they might newly intersect).
Intersection point (full algorithm only): swap the two segments in the active set, check new neighbors.

C++ Implementation -- Any Intersection? (conceptual sketch)

This snippet is intentionally incomplete. It shows the general-position case — where the proper-intersection check resolves with strict inequalities — to keep the structure visible. Collinear segments, endpoint touching (d_i == 0), vertical segments, and EPS-driven comparator transitivity failures are not handled below. Treat this as a teaching diagram, not a contest template; for a paste-ready segment-intersection routine see 01-geometry-basics.md § segment intersection and the Geometry Recipes sheet.

cpp

#include <bits/stdc++.h>
using namespace std;

using ld = long double;
struct P { ld x, y; };

struct Seg {
    P a, b; // a.x <= b.x
    int id;
    ld y_at(ld x) const {
        if (abs(a.x - b.x) < 1e-9) return a.y;
        return a.y + (b.y - a.y) * (x - a.x) / (b.x - a.x);
    }
};

ld sweep_x; // global sweep position for comparator

bool seg_intersect(Seg& s1, Seg& s2) {
    auto cross = [](P a, P b, P c) -> ld {
        return (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x);
    };
    ld d1 = cross(s2.a, s2.b, s1.a), d2 = cross(s2.a, s2.b, s1.b);
    ld d3 = cross(s1.a, s1.b, s2.a), d4 = cross(s1.a, s1.b, s2.b);
    if (((d1>0&&d2<0)||(d1<0&&d2>0)) && ((d3>0&&d4<0)||(d3<0&&d4>0)))
        return true;
    // collinear/endpoint cases omitted for brevity -- add on_segment checks
    return false;
}

For a full contest implementation, pair this with a std::set keyed by y_at(sweep_x) and process events via a priority queue, and add the on-segment / collinear handling that this sketch omits.

Area of Union of Rectangles

A powerful application: given $n$ axis-aligned rectangles, find the total area of their union.

Approach: coordinate-compress x- and y-values (01-essential-techniques/09-coordinate-compression), sweep left-to-right, maintain a segment tree on the compressed y-axis that tracks coverage counts. The specific segment tree pattern is the "lazy add + total covered length" variant — see 02-data-structures/15-segment-tree and 02-data-structures/16-segment-tree-lazy for the underlying propagation logic.

  Rectangles overlapping on a plane:

  +-------+
  |   +---|---+       Sweep line at each x-event
  |   |   |   |       updates coverage on y-axis.
  +---|---+   |       Segment tree stores how much
      +-------+       of the y-range is covered >= 1 time.

  Area = Σ (covered_y_length x Δx) for each strip between events.

Steps:

Create events: each rectangle contributes a "start" event at $x_{1}$ and "end" event at $x_{2}$ .
Coordinate-compress y-values.
Sweep x left-to-right. At each event, update the segment tree (increment/decrement coverage counts on the y-range $[y_{1}, y_{2}]$ ).
Between consecutive x-events, add covered_length x (x_next - x_curr) to the answer.

The segment tree needs to support: given range updates (+1 or -1), query the total length of y-intervals with count $\geq 1$ . This is a classical segment tree application.

Complexity: $O (n \log n)$ time, $O (n)$ space.

Closest Pair via Sweep (Alternative to D&C)

Instead of divide-and-conquer, sweep left-to-right maintaining a balanced BST of points within a sliding window of width $d$ (current best distance). For each new point, query neighbors in the BST within $[y - d, y + d]$ . When the best distance shrinks, retroactively shrink the window.

This is the approach shown in Closest Pair -- it's essentially a geometric sweep line.

Event Processing Pattern

Most geometric sweep problems follow the same skeleton:

cpp

// Skeleton for event-based geometric sweep
sort(events.begin(), events.end()); // by x, then by type
set<ActiveObject, Comparator> active;

for (auto& event : events) {
    sweep_x = event.x; // update global state
    if (event.type == START) {
        auto it = active.insert(event.obj).first;
        // check neighbors: prev(it), next(it)
    } else { // END
        auto it = active.find(event.obj);
        // check if prev(it) and next(it) newly interact
        active.erase(it);
    }
}

Gotchas

Trap	What happens	Fix
Comparator inconsistency when segments cross	`std::set` invariant breaks, UB	Re-insert after swapping, or use simpler detection
Vertical segments	Division by zero in `y_at`	Handle as special events or use cross products
Coordinate-compress forgetting to deduplicate	Wrong segment tree indices	Sort + unique the coordinate array
Using `double` comparator in `std::set`	Transitivity fails near intersections	Add EPS tolerance carefully or use exact arithmetic

Self-Test

Q1. Why can only adjacent objects in the active set intersect, not arbitrary pairs?
Answer
At any sweep position $x$, segments in the active set are ordered by their $y$-coordinate at $x$. Two non-adjacent segments have at least one segment between them in $y$-order. For those segments to intersect, they'd first have to cross the intermediate segment, which would be detected first (as an adjacency-based intersection event). So non-adjacent pairs can't intersect without a prior adjacency event.

Q2. In the rectangle union area problem, why do we use a segment tree instead of a simpler data structure?
Answer
We need to support range updates (+1/-1 on a y-interval when a rectangle starts/ends) and query the total length of y-intervals with coverage >= 1. A segment tree handles both in $O(\log n)$, while a naive array would require $O(n)$ per query. Since there are $O(n)$ events, the total is $O(n \log n)$ vs. $O(n^2)$.

Q3. What event processing order should you use when two events have the same x-coordinate?
Answer
Process "start" events before "end" events at the same $x$. This ensures segments that share an endpoint are both in the active set simultaneously, so their intersection is detected. Reversing the order would miss touching/overlapping segments.

Q4. A global variable sweep_x controls the comparator in the active set. Why is this dangerous and what's the alternative?
Answer
Modifying `sweep_x` invalidates the BST ordering -- segments that were correctly ordered at the old $x$ may be misordered at the new $x$. The `std::set` doesn't re-sort. This is safe only if you update `sweep_x` at the right moments and never query stale orderings. Alternatives: use a segment tree on discretized y-values, or re-insert affected segments after each event.

Practice Problems

Problem	What it tests
CSES -- Line Segment Intersection	Segment intersection test
CF 610D -- Vanya and Triangles	Rectangle union area
POJ 1389 -- Area of Simple Polygons	Rectangle union via sweep + segment tree
CF 612D -- The Union of Segments	Sweep merge of overlapping segments
CF 1117F -- Crisp String	Sweep-based geometry processing

Sweep Line for Geometry ​

The Geometric Sweep Mindset ​

Segment Intersection Detection ​

Simplified Bentley-Ottmann ​

C++ Implementation -- Any Intersection? (conceptual sketch) ​

Area of Union of Rectangles ​

Closest Pair via Sweep (Alternative to D&C) ​

Event Processing Pattern ​

Gotchas ​

Self-Test ​

Practice Problems ​

Further Reading ​