Sweep-Line Algorithms and Segment Intersection

Sweep-Line Algorithms and Segment Intersection

A brute-force intersection search compares every pair of segments, taking $O(n^2)$ tests even when the drawing is almost empty. A sweep line replaces those global comparisons with a moving local view. Imagine a vertical line traveling from left to right. At coordinate $x$, it remembers only the segments that cross the line and orders them from bottom to top. Most pairs never become neighbors in this order, so they never need to be compared.

This is the sweep-line pattern in one sentence: process discrete events in geometric order while maintaining exactly the state needed between events. The same pattern later powers polygon overlay, arrangements, and point-location structures.

Two Coordinated Data Structures

The event queue stores the future $x$-coordinates at which the combinatorial state may change. For a segment-intersection sweep, events include left endpoints, right endpoints, and—when all intersections must be reported—newly discovered crossings. A priority queue normally orders events lexicographically by $(x,y)$, followed by an explicit event-type tie-breaker.

The sweep status stores active segments: those whose $x$-range contains the current sweep position. Its order is the vertical order in which the sweep line meets them. A balanced search tree supports insertion, deletion, predecessor, successor, and swaps in $O(\log n)$ time.

The status comparator is unusual: it depends on the current $x$. Conceptually, segment $s$ precedes $t$ when $y_s(x) < y_t(x)$. Do not mutate a comparator behind the back of an ordinary library tree and assume its invariants survive. Production implementations use carefully controlled event transitions, symbolic comparisons just to one side of an event, or a specialized status structure.

Why Neighbors Are Enough

Consider the leftmost proper intersection not yet processed. Immediately before that crossing, its two segments must be adjacent in the sweep status. If another segment lay vertically between them, it would have to leave the gap by crossing one of the pair earlier—contradicting the choice of the leftmost intersection. This neighbor lemma converts a quadratic search into local checks.

At a left endpoint, insert the segment and test it against its predecessor and successor. At a right endpoint, remove it and test the two segments that become neighbors. At a crossing event, report the intersection, exchange the two segments' order, and test the newly adjacent pairs on the outside.

Existence Versus Reporting

The decision problem asks whether any pair intersects. The Shamos–Hoey variant can stop at the first positive neighbor test and needs only endpoint events. Under a stated general-position model—no vertical segments, no shared endpoints, no three-way crossings—this gives $O(n\log n)$ time and $O(n)$ space.

The reporting problem must enumerate every intersection. Bentley–Ottmann adds discovered crossing points to the queue. If $k$ intersections are reported, it processes $O(n+k)$ events, each with logarithmic queue and status work, for $O((n+k)\log n)$ time and $O(n+k)$ event storage in the straightforward bound. This is output-sensitive: producing $k$ distinct answers already costs $\Omega(k)$ time. Event deduplication matters because the same future crossing may be discovered from more than one neighbor transition.

The bound assumes isolated point intersections. Collinear overlaps can describe intervals and can induce quadratically many pairwise reports without isolated crossing events; decide whether to merge them, report maximal overlap pieces, or report every contributing pair before quoting a complexity bound.

A Learning Scaffold for the Decision Problem

The following Python widget demonstrates endpoint events, active status, and neighbor checks. It deliberately rebuilds the status list at each event, so it is easy to inspect but can take $O(n^2\log n)$. It also assumes general position: nonvertical segments, distinct endpoint $x$-coordinates, no endpoint touching, and no collinear overlap. It is a teaching scaffold, not a production Bentley–Ottmann implementation.

def orient(a, b, c):
    return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])


def proper_cross(s, t):
    """Strict interior crossing; degeneracies are excluded by the contract."""
    a, b = s
    c, d = t
    return ((orient(a, b, c) > 0) != (orient(a, b, d) > 0) and
            (orient(c, d, a) > 0) != (orient(c, d, b) > 0))


def y_at(segment, x):
    (x1, y1), (x2, y2) = segment
    return y1 + (y2 - y1) * (x - x1) / (x2 - x1)


def any_proper_intersection(segments):
    """Readable sweep scaffold; intentionally not asymptotically optimal."""
    normalized = []
    events = []
    for sid, (a, b) in enumerate(segments):
        if a[0] == b[0]:
            raise ValueError("vertical segment: outside this demo's contract")
        left, right = (a, b) if a[0] < b[0] else (b, a)
        normalized.append((left, right))
        events += [(left[0], 0, sid), (right[0], 1, sid)]  # start before end

    active = set()
    for x, kind, sid in sorted(events):
        if kind == 0:
            active.add(sid)
        else:
            active.remove(sid)

        # Rebuilding makes the invariant visible; a real sweep uses a tree.
        order = sorted(active, key=lambda i: y_at(normalized[i], x))
        for lower, upper in zip(order, order[1:]):
            if proper_cross(normalized[lower], normalized[upper]):
                return True, (lower, upper)
    return False, None


segments = [((0, 0), (7, 6)), ((0, 5), (7, 1)), ((1, 7), (6, 8))]
print(any_proper_intersection(segments))

Because this scaffold scans every adjacent pair after every endpoint, its code mirrors the proof more closely than the target data structure. Replacing the set and repeated sort with a balanced status tree is what recovers logarithmic updates; adding crossing events and swaps turns the decision sweep into the reporting sweep.

Degeneracies Are Part of the Specification

Real data rarely honors general position. A reliable implementation begins by choosing conventions rather than sprinkling epsilon comparisons through the code.

• Equal event coordinates: gather all events at one point and process them as a batch. A useful conceptual order is removals, crossings, then insertions, but the exact mechanics must match the chosen boundary policy. Lexicographic keys alone do not resolve several segments meeting at the same point.
• Vertical segments: they do not have a single status height at their event $x$; they span a $y$-interval. Handle each as a range query against the status, or rotate/shear coordinates symbolically so no segment is vertical. Merely dividing by $x_2-x_1$ is not a policy.
• Shared endpoints: decide whether touching counts as an intersection and whether a point incident to several segments is emitted once or once per pair. Batched events avoid missing or duplicating such contacts.
• Collinear overlaps: an overlap is a segment, not a point. Split segments at overlap boundaries or route them through a separate one-dimensional interval procedure, with a return type that distinguishes POINT from OVERLAP.
• Multiple segments at one crossing: swapping one arbitrary pair is insufficient. Remove and reinsert the entire crossing bundle in the order immediately to the right of the event.

Robust Comparisons, Not Decorative Epsilons

The sweep depends on discrete decisions: endpoint order, orientation signs, whether an intersection lies to the right, and which segment is above another just after an event. One wrong sign can corrupt the status tree, after which later neighbor reasoning no longer applies.

Use exact integer orientation when coordinate ranges permit it, widening intermediate products to prevent overflow. For floating-point inputs, use filtered predicates: evaluate quickly, bound the roundoff error, and fall back to adaptive or exact arithmetic when the sign is uncertain. Compute an intersection coordinate only when output requires it; many scheduling and ordering decisions can be expressed with orientation predicates. If constructed intersection points become future event keys, represent and compare them consistently—exact rationals or certified algebraic comparisons are safer than independently rounded doubles.

Sweep-line output is more than a list of coordinates. To support overlay, each segment must be split at its ordered intersection points, and the resulting edge pieces need incidence and adjacency. Bentley–Ottmann spotlight develops the event/status invariants and reporting machinery in full. Part 7 then gives those split edges a durable home: the doubly connected edge list (DCEL), where vertices, half-edges, and faces turn local crossings into a planar subdivision.