xv. Sweep Line and Segment Intersections

Sweep Line

Move an imaginary line across the plane and maintain a data structure describing what it currently touches. The continuous problem becomes a discrete sequence of events.

The skeleton

// 1. build events, sorted by the sweep coordinate
vector<Event> ev;
sort(ev.begin(), ev.end());
 
// 2. a status structure of currently-active objects
set<Segment, SweepCmp> status;
 
// 3. process
for (auto& e : ev) {
    if (e.isStart)  status.insert(e.obj);
    else            status.erase(e.obj);
    // answer whatever the event asks
}

Three design decisions: what is an event, what does the status structure hold, and what invariant does it maintain.

The classic applications

Problem	Events	Status	Time
Any two segments intersect?	endpoints	segments by $y$	$O(n\log n)$ (Shamos-Hoey)
Report all intersections	endpoints + intersections	segments by $y$	$O((n+k)\log n)$ (Bentley-Ottmann)
Area of a union of rectangles	vertical edges	segment tree with counts	$O(n\log n)$
Perimeter of a union of rectangles	same	same, tracking transitions	$O(n\log n)$
Count rectangle overlaps	same	segment tree with min-count	$O(n\log n)$
Closest pair	points by $x$	set of points by $y$	$O(n\log n)$ — 16-closest-pair
Maximum points in a window	window edges	count in a BIT	$O(n\log n)$
Skyline / building silhouette	building edges	multiset of heights	$O(n\log n)$
Point in polygon, many queries	polygon edges + queries	active edges	$O((n+q)\log n)$
Voronoi	sites + circle events	the beach line	$O(n\log n)$ (Fortune) — 20-delaunay-and-voronoi
Rectangle stabbing queries	edges + queries	BIT over $y$	$O((n+q)\log n)$

Area of a union of rectangles

The template everyone should know: sweep $x$, keep a segment tree over compressed $y$ that tracks how much of the $y$-axis is currently covered.

struct CoverTree {
    vector<ll> ys;
    vector<int> cnt;
    vector<ll> len;
    explicit CoverTree(vector<ll> coords) : ys(coords), cnt(4 * coords.size(), 0), len(4 * coords.size(), 0) {}
    void update(int v, int l, int r, int ql, int qr, int delta) {   // node covers [ys[l], ys[r]]
        if (qr <= l || r <= ql) return;
        if (ql <= l && r <= qr) {
            cnt[v] += delta;
        } else {
            int m = (l + r) / 2;
            update(2 * v, l, m, ql, qr, delta);
            update(2 * v + 1, m, r, ql, qr, delta);
        }
        if (cnt[v]) len[v] = ys[r] - ys[l];
        else len[v] = r - l == 1 ? 0 : len[2 * v] + len[2 * v + 1];
    }
    void add(ll y1, ll y2, int delta) {
        int l = lower_bound(ys.begin(), ys.end(), y1) - ys.begin(), r = lower_bound(ys.begin(), ys.end(), y2) - ys.begin();
        update(1, 0, ys.size() - 1, l, r, delta);
    }
    ll covered() const { return len[1]; }
};
 
ll rectangleUnionArea(const vector<array<ll, 4>>& rects) {   // {x1, y1, x2, y2}, x1 < x2, y1 < y2
    if (rects.empty()) return 0;
    vector<ll> ys;
    vector<tuple<ll, int, ll, ll>> events;   // x, +1 / -1, y1, y2
    for (auto [x1, y1, x2, y2] : rects) {
        ys.push_back(y1); ys.push_back(y2);
        events.push_back({x1, 1, y1, y2}); events.push_back({x2, -1, y1, y2});
    }
    sort(ys.begin(), ys.end());
    ys.erase(unique(ys.begin(), ys.end()), ys.end());
    sort(events.begin(), events.end());
    CoverTree tree(ys);
    ll area = 0, lastX = get<0>(events[0]);
    for (auto [x, type, y1, y2] : events) {
        area += tree.covered() * (x - lastX);
        lastX = x;
        tree.add(y1, y2, type);
    }
    return area;
}
 
ll rectangleUnionPerimeter(const vector<array<ll, 4>>& rects) {
    auto sweep = [&](bool swapAxes) {
        vector<ll> ys;
        vector<tuple<ll, int, ll, ll>> events;
        for (auto r4 : rects) {
            ll x1 = r4[0], y1 = r4[1], x2 = r4[2], y2 = r4[3];
            if (swapAxes) { swap(x1, y1); swap(x2, y2); }
            ys.push_back(y1); ys.push_back(y2);
            events.push_back({x1, -1, y1, y2}); events.push_back({x2, 1, y1, y2});   // adds (-1) sort first
        }
        sort(ys.begin(), ys.end());
        ys.erase(unique(ys.begin(), ys.end()), ys.end());
        sort(events.begin(), events.end());
        CoverTree tree(ys);
        ll total = 0;
        for (auto [x, type, y1, y2] : events) {
            ll before = tree.covered();
            tree.add(y1, y2, -type);
            total += llabs(tree.covered() - before);
        }
        return total;
    };
    if (rects.empty()) return 0;
    return sweep(false) + sweep(true);
}

Complexity: $O(n\log n)$. The segment tree stores, per node, a count of covering intervals and the covered length; crucially it never needs lazy propagation, because updates always come in matching $+1/-1$ pairs, so a node’s count never goes negative and the covered length is recomputable from the count and children. Coordinate-compress the $y$ values first.

Proof: CoverTree, area, and perimeter

update/covered. By induction on the segment tree structure: len[v] is the total length of [ys[l],ys[r]) currently covered by at least one active interval. If cnt[v]>0, the whole node range is covered by some interval that spans it entirely (an interval only increments cnt[v] when it fully contains the node’s range, by the standard segment-tree range-update convention), so len[v] is the full range length regardless of the children — correct, and this is exactly why no lazy propagation is needed: a node fully covered by one of its own ancestors’ ranges doesn’t need its children updated at all, and cnt[v]>0 alone (without recursing into children) suffices to know it’s fully covered. If cnt[v]=0, nothing covers the whole range as a single interval, so the covered length is exactly the sum of the children’s covered lengths (recursively correct by induction) — matching the pull logic.
Area. Between consecutive $x$-events, the covered $y$-length is constant (no rectangle starts or ends), so the area swept is covered() * (x - lastX); summing over all event gaps gives the total area, and processing a $+1/-1$ pair at each rectangle’s left/right edges keeps cnt consistent with “is this $y$ currently inside some rectangle’s $x$-range” at every point in the sweep.
Perimeter. The vertical contribution to the perimeter at a given sweep $x$ is exactly how much the covered-length changes when an edge is processed (a rectangle’s vertical edge contributes to the perimeter exactly where it is not flush against another rectangle, which is precisely the net change in covered length, not the edge’s own length) — summing $|\Delta \text{covered}|$ over all x-events gives the total vertical-edge perimeter contribution; by symmetry, swapping axes and repeating gives the horizontal contribution. Processing additions (sign $-1$ here, an arbitrary labelling used only to keep adds before removes at equal $x$) before removals at equal $x$ ensures two rectangles touching edge-to-edge contribute $0$ to the perimeter at that shared edge, not double-counted.

Tested: rectangleUnionArea against the circle/polygon-union Monte-Carlo pattern used elsewhere (random sample points, fraction inside any rectangle, scaled by bounding box); rectangleUnionPerimeter against a direct trace of the union region’s boundary length on small test cases built from known configurations (disjoint, touching, nested, overlapping rectangles) where the true perimeter can be computed by hand.

Choosing the status structure

Need	Structure
Ordered active objects with neighbours	std::set
Count/sum over a coordinate range	BIT or segment tree
Covered length under $\pm 1$ updates	segment tree with counts (above)
Minimum/maximum active value	multiset or a heap with lazy deletion
$k$-th active value	PBDS or a BIT

Radial and angular sweeps

The sweep need not be a line. Rotating a ray around a point (sorting by angle) solves: visibility polygons, “how many points lie in some half-plane through this point”, maximum points inside an angular sector, counting triangles containing the origin.

Sort by angle with the exact cross-product comparator, not atan2.

Practical notes

Event ordering at equal coordinates

When several events share a sweep coordinate, their relative order matters. For rectangle unions, process all additions before all removals at the same $x$ (or you will miss zero-width overlaps). Encode the tiebreak explicitly in the comparator rather than relying on the sort being stable.

• Coordinate-compress early; it makes the status structure a small array.
• Use exact integer comparators; the whole point of a sweep is that the decisions are combinatorial.
• Think about whether the sweep should be over $x$, over angle, or over time (see offline dynamic connectivity, a sweep over the query timeline).

Shamos-Hoey

Decide whether any two of $n$ line segments intersect, in $O(n\log n)$ — without finding all the intersections. The original sweep-line algorithm (1976).

Bentley-Ottmann reports all $k$ intersections in $O((n+k)\log n)$, which is $O(n^2\log n)$ when everything crosses everything. But a yes/no answer only needs the first crossing, which always involves two segments adjacent in the sweep-line status at some moment.

Algorithm

1. Create $2n$ events: the left and right endpoint of each segment. Sort by $x$ (ties: left endpoints first, then by $y$).
2. Maintain a status structure — a balanced BST of the segments currently crossing the sweep line, ordered by their $y$ at the sweep position.
3. Process events left to right:
   • Left endpoint of $s$: insert $s$. Test $s$ against its immediate predecessor and successor. If either intersects, report yes and stop.
   • Right endpoint of $s$: before erasing $s$, test its predecessor against its successor (they become adjacent). If they intersect, report yes and stop.
4. If the sweep finishes, report no.

bool anyIntersection(vector<BOSeg> segs) {       // BOSeg, StatusCmp, sweepX_: see Bentley-Ottmann below
    vector<pair<double, int>> ev;                 // x, segment index (sign encodes left/right in practice)
    for (int i = 0; i < (int)segs.size(); i++) { ev.push_back({segs[i].a.x, i}); ev.push_back({segs[i].b.x, ~i}); }
    sort(ev.begin(), ev.end());
    set<BOSeg, StatusCmp> status;
    map<int, set<BOSeg, StatusCmp>::iterator> where;
    for (auto [x, code] : ev) {
        sweepX_ = x;
        if (code >= 0) {
            auto it = status.insert(segs[code]).first;
            where[code] = it;
            auto nx = next(it), pv = (it == status.begin() ? status.end() : prev(it));
            PD tmp;
            if (nx != status.end() && segIntersect(*it, *nx, tmp)) return true;
            if (pv != status.end() && segIntersect(*pv, *it, tmp)) return true;
        } else {
            int id = ~code;
            auto it = where[id];
            auto nx = next(it), pv = (it == status.begin() ? status.end() : prev(it));
            PD tmp;
            if (nx != status.end() && pv != status.end() && segIntersect(*pv, *nx, tmp)) return true;
            status.erase(it);
        }
    }
    return false;
}

Complexity: $O(n\log n)$ — $2n$ events, each $O(\log n)$ BST work and $O(1)$ intersection tests.

Proof: adjacency suffices

Claim: if two segments $s,t$ intersect, then at some sweep position before their leftmost intersection they are adjacent in the status order.
Consider the sweep just to the left of their first crossing point. There, $s$ and $t$ have a definite order, say $s$ below $t$; just after the crossing the order flips. The order can only change at events (insertions, removals, or a crossing itself), so immediately before the crossing they must be neighbours: any segment strictly between them at that moment would itself have to cross one of $s,t$ at some point no later than $s,t$‘s own crossing (to end up out of the way), contradicting that $s,t$‘s crossing is the first one encountered by the sweep. Hence testing only adjacent pairs at every event is guaranteed to test $s,t$ at the moment they become adjacent, which happens no later than (and typically exactly at) the event just before their crossing. $■$

Shamos-Hoey vs Bentley-Ottmann

	Shamos-Hoey	Bentley-Ottmann
Answers	does any intersection exist	all intersections
Time	$O(n\log n)$	$O((n+k)\log n)$
Events	endpoints only	endpoints and intersection points
Status changes	insert/erase	insert/erase and swap

Variants / Use Cases

• Simple polygon testing — is a polygon self-intersecting? Feed its edges (excluding shared endpoints) to Shamos-Hoey.
• Planarity of a drawing — does a given straight-line drawing have crossings?
• Validating geometric input — GIS and CAD systems run this constantly.

Bentley-Ottmann

Find all pairwise intersection points among $n$ line segments in $O((n+k)\log n)$, $k$ the number of intersections.

Algorithm

1. Sweep a vertical line left to right. Maintain an event queue (ordered by $x$, then $y$) of segment endpoints and detected intersection points.
2. Maintain a status structure ordered by each segment’s current $y$ at the sweep position.
3. Left endpoint: insert; check the new neighbours for intersections, scheduling any found as future events.
4. Right endpoint: remove; check the now-adjacent former neighbours against each other.
5. Intersection event: report the point; the two segments swap $y$-order here, so remove and reinsert both (their relative order has flipped), then check each against its new far-side neighbour.

struct BOSeg { PD a, b; int id; };   // caller guarantees a.x < b.x; no vertical segments (see the scope note below)
 
double sweepX_;                       // current sweep position, read by the status comparator
double yAtSweep(const BOSeg& s, double x) {
    double t = (x - s.a.x) / (s.b.x - s.a.x);
    return s.a.y + t * (s.b.y - s.a.y);
}
struct StatusCmp {
    bool operator()(const BOSeg& s1, const BOSeg& s2) const {
        double y1 = yAtSweep(s1, sweepX_), y2 = yAtSweep(s2, sweepX_);
        if (fabs(y1 - y2) > 1e-9) return y1 < y2;
        double sl1 = (s1.b.y - s1.a.y) / (s1.b.x - s1.a.x), sl2 = (s2.b.y - s2.a.y) / (s2.b.x - s2.a.x);
        if (fabs(sl1 - sl2) > 1e-9) return sl1 < sl2;
        return s1.id < s2.id;
    }
};
struct BOEvent {
    double x, y; int type; int id1, id2;       // type: 0 left, 1 right, 2 intersection
    bool operator<(const BOEvent& o) const { return x > o.x || (x == o.x && y > o.y); }  // reversed: min-heap
};
 
bool segIntersect(const BOSeg& s1, const BOSeg& s2, PD& out) {
    PD d1 = s1.b - s1.a, d2 = s2.b - s2.a;
    double den = cross(d1, d2);
    if (fabs(den) < 1e-12) return false;                 // parallel (collinear overlap: out of scope, see below)
    double t = cross(s2.a - s1.a, d2) / den, u = cross(s2.a - s1.a, d1) / den;
    if (t < -1e-9 || t > 1 + 1e-9 || u < -1e-9 || u > 1 + 1e-9) return false;
    out = s1.a + d1 * t;
    return true;
}
 
vector<PD> bentleyOttmann(vector<BOSeg> segs) {
    priority_queue<BOEvent> pq;
    map<int, BOSeg> byId;
    for (auto& s : segs) {
        byId[s.id] = s;
        pq.push({s.a.x, s.a.y, 0, s.id, -1});
        pq.push({s.b.x, s.b.y, 1, s.id, -1});
    }
    set<BOSeg, StatusCmp> status;
    map<int, set<BOSeg, StatusCmp>::iterator> where;
    set<pair<int, int>> scheduled;
    vector<PD> result;
 
    auto schedule = [&](int id1, int id2) {
        if (id1 < 0 || id2 < 0) return;
        auto key = minmax(id1, id2);
        if (scheduled.count(key)) return;
        PD pt;
        if (segIntersect(byId[id1], byId[id2], pt) && pt.x >= sweepX_ - 1e-9) {
            pq.push({pt.x, pt.y, 2, id1, id2});
            scheduled.insert(key);
        }
    };
 
    while (!pq.empty()) {
        BOEvent e = pq.top(); pq.pop();
        sweepX_ = e.x;
        if (e.type == 0) {
            auto it = status.insert(byId[e.id1]).first;
            where[e.id1] = it;
            auto nx = next(it), pv = (it == status.begin() ? status.end() : prev(it));
            if (nx != status.end()) schedule(e.id1, nx->id);
            if (pv != status.end()) schedule(e.id1, pv->id);
        } else if (e.type == 1) {
            auto it = where[e.id1];
            auto nx = next(it), pv = (it == status.begin() ? status.end() : prev(it));
            if (nx != status.end() && pv != status.end()) schedule(pv->id, nx->id);
            status.erase(it);
            where.erase(e.id1);
        } else {
            result.push_back({e.x, e.y});                  // report the intersection
            status.erase(where[e.id1]); status.erase(where[e.id2]);
            sweepX_ = e.x + 1e-7;                            // just past the crossing: order has now flipped
            bool firstIsLower = StatusCmp()(byId[e.id1], byId[e.id2]);
            int loId = firstIsLower ? e.id1 : e.id2, hiId = firstIsLower ? e.id2 : e.id1;
            auto insLo = status.insert(byId[loId]).first;
            auto insHi = status.insert(byId[hiId]).first;
            where[loId] = insLo; where[hiId] = insHi;
            auto beforeLo = (insLo == status.begin() ? status.end() : prev(insLo));
            auto afterHi = next(insHi);
            if (beforeLo != status.end()) schedule(beforeLo->id, loId);
            if (afterHi != status.end()) schedule(hiId, afterHi->id);
        }
    }
    return result;
}

Complexity: $O((n+k)\log n)$: $2n$ endpoint events plus $k$ intersection events, each $O(\log n)$.

Scope of this implementation

This version handles the generic-position case cleanly: no vertical segments (yAtSweep divides by $\Delta x$), no two segments overlapping along a shared sub-segment (segIntersect returns “no intersection” for parallel lines, including collinear-overlapping ones), and no three or more segments crossing at exactly the same point (each crossing is scheduled and resolved as a pairwise event; a triple point works out to the same reported point from multiple pairs in practice, but the status-structure bookkeeping around it is not guaranteed order-independent). A production implementation handles all three with extra casework — rotate the input slightly to remove verticals, treat collinear overlaps as their own event type, and merge simultaneous intersection events before processing — but for contest inputs in general position, this is the real algorithm, not a sketch.

Proof: Bentley-Ottmann is correct

Invariant. At any sweep position, status lists exactly the segments currently crossing the sweep line, correctly ordered by true $y$ at that $x$ — maintained because segments are only reordered at a detected intersection event, which is exactly when two adjacent segments’ true order flips, and the code removes and reinserts both at that moment under the post-crossing order.
Completeness (every true intersection is found). By the same adjacency argument as Shamos-Hoey: immediately before any true intersection, its two segments are adjacent in the status order. The algorithm checks newly-adjacent pairs at every insertion, removal, and crossing event — so the pair becomes adjacent at some event no later than their own crossing (an earlier crossing involving one of them with a different segment is itself processed first, by induction on sweep order, correctly updating the status so that eventually this pair becomes neighbours before their own crossing point is reached), is scheduled via schedule, and is reported when the sweep reaches that $x$.
No duplicate work. scheduled records each unordered pair once; a pair already scheduled is not re-scheduled even if it becomes adjacent again through other segments’ removals, since its single true crossing (in the generic-position scope above) is already queued.
Termination. The event queue holds $2n$ endpoint events plus exactly $k$ intersection events (one per true crossing, by the no-duplicate-scheduling argument), so the loop runs $O(n+k)$ iterations, each $O(\log n)$. $■$

Tested against brute-force $O(n^2)$ all-pairs intersection on random segment sets (up to 25 segments, hundreds of trials), excluding by construction the three degeneracies noted above (verticals, collinear overlaps, triple points) to match the implementation’s documented scope; every brute-force intersection point is matched by a reported one and vice versa.

Variants / Use Cases

• Map overlay / GIS polygon intersection — core subroutine for combining vector map layers.
• CAD system geometry engines — detecting overlaps and crossings in drawings.
• Axis-aligned rectangle intersection — a simplified variant for orthogonal shapes.
• Arrangement construction — generalises to arrangements of curves, not just straight segments.