Introduction

Draw nn line segments on a page — road maps, circuit traces, the edges of overlapping polygons — and ask a simple question: where do they cross? The obvious way to answer is to compare every pair of segments, one against another, and check whether they intersect. With nn segments that's (n2)\binom{n}{2} pairs, so the work grows like O(n2)O(n^2).

For a handful of segments that's fine. For the millions of edges in a GIS map or a chip layout, quadratic time is a wall. And here's the strange part: most pairs of segments are nowhere near each other, so almost all of that checking is wasted effort on segments that could never possibly cross.

In 1979, Jon Bentley and Thomas Ottmann found a way to only ever compare segments that are genuinely close to each other at some moment — using a line that sweeps across the page and a queue that tells it exactly when to look.

Sweep the Line

Below is a handful of segments. A vertical sweep line moves left to right; at every moment it only tracks the segments it currently crosses, ordered top to bottom. Only neighbors in that order are ever compared for a crossing.

<p class="hint">Five segments, five colors. A red dashed <b>sweep line</b> moves left to right; the blue dots mark where the sweep currently crosses each segment, ordered top to bottom. The algorithm only ever compares <b>neighboring</b> dots for a crossing.</p>
<svg id="scene" class="scene" viewBox="0 0 340 220" xmlns="http://www.w3.org/2000/svg"></svg>
<div class="status" id="status">Ready — press Step or Run to start the sweep.</div>
<div class="btns">
  <button id="step" type="button">Step</button>
  <button id="run" type="button">Run</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>
<div class="log" id="log"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.scene { width: 100%; max-width: 480px; height: auto; background: #f6f8fa; border: 1px solid #d7dee5; border-radius: 8px; display: block; }
.seg { stroke-width: 2.4; }
.sweep { stroke: #e63946; stroke-width: 1.6; stroke-dasharray: 4 3; }
.dot { fill: #1d3557; }
.cross-dot { fill: #e63946; stroke: #fff; stroke-width: 1; }
.status { font-size: 1rem; font-weight: 600; margin: .6rem 0 .3rem; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.info { color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .5rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .5; cursor: default; }
.log { font: 13px ui-monospace, monospace; color: #333; background: #fff; border: 1px solid #e2e6ea;
       border-radius: 8px; padding: .5rem .7rem; max-height: 110px; overflow-y: auto; line-height: 1.5; }
.log .none { color: #888; font-style: italic; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));

// The 5 demo segments, each with its own color for the log and drawing.
const SEGS = [
  { id: 0, x1: 40,  y1: 40,  x2: 300, y2: 190, color: '#1d3557' },
  { id: 1, x1: 40,  y1: 190, x2: 300, y2: 40,  color: '#e07a3f' },
  { id: 2, x1: 90,  y1: 15,  x2: 130, y2: 210, color: '#2a9d8f' },
  { id: 3, x1: 20,  y1: 115, x2: 320, y2: 125, color: '#6a4c93' },
  { id: 4, x1: 210, y1: 20,  x2: 250, y2: 205, color: '#c9184a' },
];
const MINX = 20, MAXX = 320;

// Standard parametric line-segment intersection test (returns null if parallel or outside both segments).
function segIntersect(a, b) {
  const d1x = a.x2 - a.x1, d1y = a.y2 - a.y1;
  const d2x = b.x2 - b.x1, d2y = b.y2 - b.y1;
  const denom = d1x * d2y - d1y * d2x;
  if (Math.abs(denom) < 1e-9) return null;
  const t = ((b.x1 - a.x1) * d2y - (b.y1 - a.y1) * d2x) / denom;
  const u = ((b.x1 - a.x1) * d1y - (b.y1 - a.y1) * d1x) / denom;
  if (t < -1e-9 || t > 1 + 1e-9 || u < -1e-9 || u > 1 + 1e-9) return null;
  return { x: a.x1 + t * d1x, y: a.y1 + t * d1y };
}
function yAt(seg, x) {
  if (Math.abs(seg.x2 - seg.x1) < 1e-9) return seg.y1;
  const t = (x - seg.x1) / (seg.x2 - seg.x1);
  return seg.y1 + t * (seg.y2 - seg.y1);
}

// Base events: every segment start and end, sorted by x. Crossing events are added lazily as they are discovered.
// Build the base start/end events; crossing events are appended as the
// sweep discovers them by comparing only neighbors in the active order.
let events = [];
SEGS.forEach(s => {
  const xs = Math.min(s.x1, s.x2), xe = Math.max(s.x1, s.x2);
  events.push({ x: xs, type: 'start', seg: s.id });
  events.push({ x: xe, type: 'end', seg: s.id });
});
events.sort((a, b) => a.x - b.x);

let active = [];       // Segment ids currently crossed by the sweep line, kept sorted by their y-coordinate at the sweep's x.
let seenPairs = new Set();
let crossings = [];    // All crossings discovered so far, in the order the sweep found them.
let evIdx = 0;
let sweepX = MINX;
let running = false;
let timer = null;

function statusOrder(x) {
  active.sort((idA, idB) => yAt(SEGS[idA], x) - yAt(SEGS[idB], x));
}

// The key idea: only adjacent segments in the active order are ever tested for intersection, never a distant pair.
function checkNeighbors(x) {
  const newly = [];
  for (let i = 0; i < active.length - 1; i++) {
    const a = active[i], b = active[i + 1];
    const key = a < b ? a + ',' + b : b + ',' + a;
    if (seenPairs.has(key)) continue;
    const p = segIntersect(SEGS[a], SEGS[b]);
    if (p && p.x >= x - 1e-6 && p.x <= MAXX + 1e-6) {
      seenPairs.add(key);
      crossings.push({ a, b, x: p.x, y: p.y });
      newly.push({ a, b, x: p.x, y: p.y });
      events.push({ x: p.x, type: 'cross', pair: [a, b] });
      events.sort((e1, e2) => e1.x - e2.x);
    }
  }
  return newly;
}

function svgEl(name, attrs) {
  const el = document.createElementNS('http://www.w3.org/2000/svg', name);
  for (const k in attrs) el.setAttribute(k, attrs[k]);
  return el;
}

function draw() {
  const svg = document.getElementById('scene');
  svg.innerHTML = '';
  SEGS.forEach(s => {
    svg.appendChild(svgEl('line', { x1: s.x1, y1: s.y1, x2: s.x2, y2: s.y2, class: 'seg', stroke: s.color }));
  });
  crossings.forEach(c => {
    if (c.x <= sweepX + 1e-6) svg.appendChild(svgEl('circle', { cx: c.x, cy: c.y, r: 3.2, class: 'cross-dot' }));
  });
  svg.appendChild(svgEl('line', { x1: sweepX, y1: 5, x2: sweepX, y2: 215, class: 'sweep' }));
  active.forEach(id => {
    const y = yAt(SEGS[id], sweepX);
    svg.appendChild(svgEl('circle', { cx: sweepX, cy: y, r: 3.6, class: 'dot' }));
  });
}

function logLine(text) {
  const log = document.getElementById('log');
  const empty = log.querySelector('.none');
  if (empty) empty.remove();
  const div = document.createElement('div');
  div.textContent = text;
  log.appendChild(div);
  log.scrollTop = log.scrollHeight;
}

function setStatus(t, cls) {
  const s = document.getElementById('status');
  s.textContent = t;
  s.className = 'status ' + cls;
}

function reset() {
  events = [];
  SEGS.forEach(s => {
    const xs = Math.min(s.x1, s.x2), xe = Math.max(s.x1, s.x2);
    events.push({ x: xs, type: 'start', seg: s.id });
    events.push({ x: xe, type: 'end', seg: s.id });
  });
  events.sort((a, b) => a.x - b.x);
  active = [];
  seenPairs = new Set();
  crossings = [];
  evIdx = 0;
  sweepX = MINX;
  running = false;
  if (timer) { clearInterval(timer); timer = null; }
  document.getElementById('log').innerHTML = '<div class="none">Events will appear here as the sweep advances.</div>';
  document.getElementById('run').textContent = 'Run';
  document.getElementById('step').disabled = false;
  setStatus('Ready — press Step or Run to start the sweep.', 'info');
  draw();
}

// Process exactly one event (start, end, or crossing) and refresh the drawing and log.
function step() {
  if (evIdx >= events.length) {
    setStatus(i18nFmt('Sweep finished — found all %n% crossing(s).', { n: crossings.length }), 'ok');
    document.getElementById('step').disabled = true;
    if (running) { running = false; clearInterval(timer); document.getElementById('run').textContent = 'Run'; }
    draw();
    return;
  }
  const ev = events[evIdx];
  sweepX = ev.x;
  if (ev.type === 'start') {
    active.push(ev.seg);
    statusOrder(ev.x);
    const found = checkNeighbors(ev.x);
    logLine(i18nFmt('Segment %seg% starts — inserted into the active order.', { seg: ev.seg }));
    found.forEach(c => logLine(i18nFmt('Crossing found between segment %a% and segment %b% near x = %x%.', { a: c.a, b: c.b, x: c.x.toFixed(0) })));
  } else if (ev.type === 'end') {
    active = active.filter(s => s !== ev.seg);
    logLine(i18nFmt('Segment %seg% ends — removed from the active order.', { seg: ev.seg }));
  } else if (ev.type === 'cross') {
    statusOrder(ev.x + 1e-6);
    checkNeighbors(ev.x + 1e-6);
    logLine(i18nFmt('Neighbors %a% and %b% swap places — crossing detected and reported.', { a: ev.pair[0], b: ev.pair[1] }));
  }
  evIdx++;
  setStatus(i18nFmt('Sweep in progress: %active% active segment(s), %found% crossing(s) found so far.', { active: active.length, found: crossings.length }), 'info');
  draw();
}

document.getElementById('step').addEventListener('click', step);
document.getElementById('reset').addEventListener('click', reset);
document.getElementById('run').addEventListener('click', () => {
  if (running) {
    running = false;
    clearInterval(timer);
    document.getElementById('run').textContent = 'Run';
    return;
  }
  running = true;
  document.getElementById('run').textContent = 'Pause';
  timer = setInterval(() => {
    step();
    if (evIdx >= events.length) {
      running = false;
      clearInterval(timer);
      document.getElementById('run').textContent = 'Run';
    }
  }, 550);
});

reset();
Result
Console

Press Step to advance the sweep one event at a time, or Run to play it through. Watch how the active order changes only when segments start, end, or swap places at a crossing — that swap is exactly how the algorithm notices an intersection without ever comparing a distant pair.

The Real Complexity

The trick is to never ask "do these two segments cross?" for a pair that is far apart. Bentley-Ottmann keeps two structures moving together:

  • The event queue. A priority queue of xx-coordinates where something interesting can happen: a segment starts, a segment ends, or two segments cross. It begins with just the 2n2n endpoints and grows as new crossing events are discovered.
  • The status structure. A balanced order (conceptually a sorted list, in practice a balanced binary search tree) of the segments currently crossed by the sweep line, ordered by their yy-coordinate at the line's current position. Only segments that are adjacent in this order are ever tested for intersection.

At each event the sweep does a constant amount of structural work — insert a segment, delete a segment, or swap two neighbors — plus O(log⁡n)O(\log n) to keep the status structure balanced. Insertions and deletions happen at most 2n2n times (once per endpoint); crossings happen exactly KK times, the number of intersection points. So the total number of events is O(n+K)O(n + K), and each costs O(log⁡n)O(\log n):

T(n,K)=O((n+K)log⁡n)T(n, K) = O\big((n + K)\log n\big)

This is an output-sensitive bound: the running time scales with how many intersections actually exist, not just with nn. In the worst case KK can be O(n2)O(n^2) (every pair crosses), and the algorithm gracefully degrades to roughly the brute-force bound — but whenever KK is small, which is the common case for real maps and drawings, Bentley-Ottmann is dramatically faster than checking every pair. Space stays O(n)O(n) for the status and queue, ignoring the room needed to output the crossings themselves. This same insert-delete-swap idea is a workhorse of the broader computational geometry toolbox.

Where It Matters

Sweeping a line across geometric data and maintaining order along the way is one of the most reused ideas in applied geometry:

  • Geographic information systems (GIS): overlaying two maps — say, roads and rivers — to find every place they meet is exactly the segment-intersection problem, run on millions of edges.
  • VLSI design-rule checking: chip layouts are made of enormous numbers of rectangles and wires; checking that none illegally overlap uses sweep-line variants at massive scale.
  • Computer graphics: clipping polygons, resolving overlapping shapes, and rendering vector art all lean on sweeping and ordered status structures.
  • Robotics and motion planning: detecting where a robot's swept path could collide with obstacles reduces to the same crossing-detection idea.

Once you've seen the sweep line and its event queue here, you've met the pattern behind a whole family of geometric algorithms, including the sweeps used to build a convex hull or a Voronoi diagram.

Conclusion

Bentley-Ottmann answers a deceptively simple question — where do these lines cross? — without ever falling into the trap of comparing every possible pair. By sweeping a line across the plane and keeping only genuinely neighboring segments under comparison, it turns an O(n2)O(n^2) search into an O((n+K)log⁡n)O((n+K)\log n) one that scales with the number of crossings that truly exist.

It is a small, elegant proof that the shape of an algorithm's work can matter as much as the size of its input — and solved back in 1979, this same sweeping idea still quietly powers the maps, chips and graphics we use every day, sitting alongside classics like the convex hull.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/bentley-ottmann-algorithm/Content licensed under CC BY-NC 4.0.