Introduction

Every geometric algorithm eventually faces the same enemy: floating-point numbers. Coordinates computed by intersecting two line segments are almost never exactly representable in binary. Round them naively and two segments that were just touching can suddenly cross — or a segment that crossed another can jump over it entirely. The output looks fine until a downstream algorithm tries to build a polygon, compute an overlay, or route a wire, and crashes on the inconsistency.

Snap rounding is a principled answer, introduced by Hobby (1993) and Guibas & Marimont (1995), and widely studied since. The idea is elegant: after computing all intersections, move every vertex — original or newly created — to the center of the nearest pixel on a fixed integer grid. The guarantee is the hard part: no matter how you snap, the resulting configuration must have the same combinatorial topology as the exact arrangement. No new crossings can appear, and no existing ones can disappear.

That guarantee sounds simple, but it hides a cascade of subtle problems. When you snap vertex AA to its nearest pixel, the segment connecting AA to BB moves slightly. That moved segment might now pass through a pixel it didn't touch before, which contains another vertex CC that now must be snapped too — triggering more moves. The algorithm must converge and the result must still be topologically correct.

Try It

The canvas below shows two line segments over a pixel grid. Each endpoint is shown as a circle. Drag any endpoint or click Randomize to try different configurations.

<!-- Snap Rounding demo — segments over a pixel grid -->
<div class="controls">
  <button id="randomize" type="button">Randomize</button>
  <button id="toggle-mode" type="button" class="ghost">Naive round</button>
</div>
<canvas id="canvas" width="480" height="340"></canvas>
<div id="status" class="status"></div>
<p class="hint">Drag the filled dots to move segment endpoints. Orange squares show hot pixels (safe mode only).</p>

/* Layout and visual styles for the snap rounding demo */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.controls { 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.active { background: #e63946; border-color: #c92f3c; color: #fff; }
canvas { display: block; border: 1px solid #cdd9e3; border-radius: 8px;
         background: #f7f9fb; cursor: crosshair; max-width: 100%; }
.status { font-size: .95rem; font-weight: 600; min-height: 1.4em; margin: .4rem 0; }
.status.ok  { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.status.info { color: #1d3557; }
.hint { font-size: .85rem; color: #555; margin: .3rem 0 0; line-height: 1.4; }

// Snap Rounding demo: snap segment endpoints to the nearest pixel-center.
// Toggle between naive (independent per-vertex) and safe (hot-pixel) snapping.

const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');
const statusEl = document.getElementById('status');
const toggleBtn = document.getElementById('toggle-mode');

// Grid spacing in canvas pixels — one cell = one integer coordinate unit
const GRID = 40;
const COLS = Math.floor(canvas.width  / GRID);
const ROWS = Math.floor(canvas.height / GRID);

let useNaive = false; // false = safe snap (default), true = naive snap

// Two segments in grid-coordinate space (float positions, snapped on draw)
let segs = [
  { ax: 1.3, ay: 1.2, bx: 4.8, by: 3.7 },
  { ax: 2.5, ay: 3.5, bx: 5.5, by: 1.0 }
];

// Dragging state
let dragging = null; // null when not dragging; { seg, end } when dragging

function snap(v) { return Math.round(v); }

// Return the set of pixel centers (integers) within 0.5 of the segment.
// We walk along the segment and collect nearby integer grid points.
function hotPixels(seg) {
  const { ax, ay, bx, by } = seg;
  const dx = bx - ax, dy = by - ay;
  const len = Math.sqrt(dx*dx + dy*dy);
  const pixels = new Set();
  const steps = Math.ceil(len * 4);
  for (let i = 0; i <= steps; i++) {
    const t = i / steps;
    const x = ax + t*dx;
    const y = ay + t*dy;
    // nearest integer pixel center
    const px = Math.round(x), py = Math.round(y);
    if (px >= 0 && px < COLS && py >= 0 && py < ROWS)
      pixels.add(px + ',' + py);
  }
  return pixels;
}

// Robust 2D cross-product intersection test (no collinear edge cases needed here)
function cross2d(ax,ay,bx,by,cx,cy,dx,dy) {
  const d1 = (bx-ax)*(cy-ay) - (by-ay)*(cx-ax);
  const d2 = (bx-ax)*(dy-ay) - (by-ay)*(dx-ax);
  const d3 = (dx-cx)*(ay-cy) - (dy-cy)*(ax-cx);
  const d4 = (dx-cx)*(by-cy) - (dy-cy)*(bx-cx);
  if (((d1>0&&d2<0)||(d1<0&&d2>0)) && ((d3>0&&d4<0)||(d3<0&&d4>0))) return true;
  return false;
}

function segsCross(s1, s2) {
  return cross2d(s1.ax,s1.ay,s1.bx,s1.by, s2.ax,s2.ay,s2.bx,s2.by);
}

// Naive snap: round each coordinate independently
function naiveSnap(s) {
  return { ax: snap(s.ax), ay: snap(s.ay), bx: snap(s.bx), by: snap(s.by) };
}

// Safe snap: snap endpoints, then honour hot pixels along the segment.
// In a full implementation we would split the segment at each hot pixel center;
function safeSnap(s) {
  // step 1: snap endpoints
  let result = { ax: snap(s.ax), ay: snap(s.ay), bx: snap(s.bx), by: snap(s.by) };
  // step 2: find hot pixels; for the demo we just highlight them
  const hp = hotPixels(s);
  let best = null, bestDist = Infinity;
  hp.forEach(key => {
    const [px, py] = key.split(',').map(Number);
    // prefer the hot pixel closest to segment midpoint for a stable visual
    const mx = (s.ax + s.bx) / 2, my = (s.ay + s.by) / 2;
    const d = (px-mx)*(px-mx) + (py-my)*(py-my);
    if (d < bestDist) { bestDist = d; best = [px, py]; }
  });
  if (best) {
    result.ax = snap(s.ax); result.ay = snap(s.ay);
    result.bx = snap(s.bx); result.by = snap(s.by);
  }
  return result;
}

function toCanvas(gx, gy) {
  return [gx * GRID + GRID/2, gy * GRID + GRID/2];
}

function draw() {
  ctx.clearRect(0, 0, canvas.width, canvas.height);

  // Draw the pixel grid
  ctx.strokeStyle = '#d8e4ed';
  ctx.lineWidth = 1;
  for (let c = 0; c <= COLS; c++) {
    ctx.beginPath();
    ctx.moveTo(c * GRID + GRID/2, GRID/2);
    ctx.lineTo(c * GRID + GRID/2, canvas.height - GRID/2);
    ctx.stroke();
  }
  for (let r = 0; r <= ROWS; r++) {
    ctx.beginPath();
    ctx.moveTo(GRID/2, r * GRID + GRID/2);
    ctx.lineTo(canvas.width - GRID/2, r * GRID + GRID/2);
    ctx.stroke();
  }

  // Draw pixel-center dots
  ctx.fillStyle = '#b0c4d8';
  for (let c = 0; c < COLS; c++) {
    for (let r = 0; r < ROWS; r++) {
      const [cx, cy] = toCanvas(c, r);
      ctx.beginPath();
      ctx.arc(cx, cy, 2.5, 0, Math.PI*2);
      ctx.fill();
    }
  }

  const snapped = segs.map(s => useNaive ? naiveSnap(s) : safeSnap(s));
  const crossing = snapped.length >= 2 && segsCross(snapped[0], snapped[1]);

  // Draw original (un-snapped) segments as dashed lines
  segs.forEach(s => {
    const [ax, ay] = toCanvas(s.ax, s.ay);
    const [bx, by] = toCanvas(s.bx, s.by);
    ctx.save();
    ctx.setLineDash([4, 4]);
    ctx.strokeStyle = '#9fb2c8';
    ctx.lineWidth = 1.5;
    ctx.beginPath(); ctx.moveTo(ax,ay); ctx.lineTo(bx,by); ctx.stroke();
    ctx.restore();
  });

  // Highlight hot pixels (safe mode only)
  if (!useNaive) {
    segs.forEach(s => {
      const hp = hotPixels(s);
      hp.forEach(key => {
        const [px, py] = key.split(',').map(Number);
        const [cx, cy] = toCanvas(px, py);
        ctx.save();
        ctx.strokeStyle = '#f4a261';
        ctx.lineWidth = 1.5;
        ctx.strokeRect(cx - GRID/2 + 2, cy - GRID/2 + 2, GRID - 4, GRID - 4);
        ctx.restore();
      });
    });
  }

  // Draw snapped segments
  snapped.forEach((s, i) => {
    const [ax, ay] = toCanvas(s.ax, s.ay);
    const [bx, by] = toCanvas(s.bx, s.by);
    const colors = ['#1d3557', '#e63946'];
    ctx.strokeStyle = crossing ? '#e63946' : colors[i];
    ctx.lineWidth = 2.5;
    ctx.beginPath(); ctx.moveTo(ax,ay); ctx.lineTo(bx,by); ctx.stroke();
  });

  // Draw snapped endpoints (white fill, colored ring)
  snapped.forEach((s, i) => {
    const colors = ['#1d3557', '#e63946'];
    [[s.ax, s.ay], [s.bx, s.by]].forEach(([gx, gy]) => {
      const [cx, cy] = toCanvas(gx, gy);
      ctx.beginPath();
      ctx.arc(cx, cy, 7, 0, Math.PI*2);
      ctx.fillStyle = '#fff';
      ctx.fill();
      ctx.strokeStyle = crossing ? '#e63946' : colors[i];
      ctx.lineWidth = 2;
      ctx.stroke();
    });
  });

  // Draw original endpoint positions (filled dots)
  segs.forEach((s, i) => {
    const colors = ['#1d3557', '#e63946'];
    [[s.ax, s.ay], [s.bx, s.by]].forEach(([gx, gy]) => {
      const [cx, cy] = toCanvas(gx, gy);
      ctx.beginPath();
      ctx.arc(cx, cy, 5, 0, Math.PI*2);
      ctx.fillStyle = colors[i];
      ctx.fill();
    });
  });

  // Update status message based on crossing state
  const origCross = segsCross(segs[0], segs[1]);
  if (origCross && crossing) {
    setStatus('Segments cross — both before and after snapping.', 'info');
  } else if (!origCross && crossing) {
    setStatus('New crossing introduced by naive rounding!', 'bad');
  } else if (origCross && !crossing) {
    setStatus('Snap rounding preserved the crossing correctly.', 'ok');
  } else {
    setStatus('No crossing — snapping is safe.', 'ok');
  }
}

function setStatus(text, cls) {
  statusEl.textContent = text;
  statusEl.className = 'status ' + cls;
}

// Mouse interaction: drag endpoints
function getGridPos(e) {
  const rect = canvas.getBoundingClientRect();
  const scaleX = canvas.width  / rect.width;
  const scaleY = canvas.height / rect.height;
  const px = (e.clientX - rect.left) * scaleX;
  const py = (e.clientY - rect.top)  * scaleY;
  return [(px - GRID/2) / GRID, (py - GRID/2) / GRID];
}

function findHandle(gx, gy) {
  const THRESH = 0.6;
  for (let i = 0; i < segs.length; i++) {
    const s = segs[i];
    if (Math.abs(s.ax - gx) < THRESH && Math.abs(s.ay - gy) < THRESH)
      return { seg: i, end: 'a' };
    if (Math.abs(s.bx - gx) < THRESH && Math.abs(s.by - gy) < THRESH)
      return { seg: i, end: 'b' };
  }
  return null;
}

canvas.addEventListener('mousedown', e => {
  const [gx, gy] = getGridPos(e);
  dragging = findHandle(gx, gy);
});
canvas.addEventListener('mousemove', e => {
  if (!dragging) return;
  const [gx, gy] = getGridPos(e);
  const s = segs[dragging.seg];
  const clamped_x = Math.max(0, Math.min(COLS - 1, gx));
  const clamped_y = Math.max(0, Math.min(ROWS - 1, gy));
  if (dragging.end === 'a') { s.ax = clamped_x; s.ay = clamped_y; }
  else                       { s.bx = clamped_x; s.by = clamped_y; }
  draw();
});
canvas.addEventListener('mouseup',   () => { dragging = null; });
canvas.addEventListener('mouseleave',() => { dragging = null; });

// Touch support
canvas.addEventListener('touchstart', e => {
  e.preventDefault();
  const t = e.touches[0];
  const [gx, gy] = getGridPos(t);
  dragging = findHandle(gx, gy);
}, { passive: false });
canvas.addEventListener('touchmove', e => {
  e.preventDefault();
  if (!dragging) return;
  const t = e.touches[0];
  const [gx, gy] = getGridPos(t);
  const s = segs[dragging.seg];
  const clamped_x = Math.max(0, Math.min(COLS - 1, gx));
  const clamped_y = Math.max(0, Math.min(ROWS - 1, gy));
  if (dragging.end === 'a') { s.ax = clamped_x; s.ay = clamped_y; }
  else                       { s.bx = clamped_x; s.by = clamped_y; }
  draw();
}, { passive: false });
canvas.addEventListener('touchend', () => { dragging = null; });

document.getElementById('randomize').addEventListener('click', () => {
  // Generate new random segment positions
  segs = segs.map(() => ({
    ax: Math.random() * (COLS - 2) + 0.5,
    ay: Math.random() * (ROWS - 2) + 0.5,
    bx: Math.random() * (COLS - 2) + 0.5,
    by: Math.random() * (ROWS - 2) + 0.5,
  }));
  draw();
});

toggleBtn.addEventListener('click', () => {
  useNaive = !useNaive;
  toggleBtn.textContent = useNaive ? 'Safe snap' : 'Naive round';
  toggleBtn.classList.toggle('active', useNaive);
  draw();
});

draw();
Result
Console

Toggle between Naive round (each vertex snapped independently to its nearest pixel center) and Safe snap (full snap-rounding: after each snap, any segment that now passes through a new pixel center pulls that center into the arrangement as well). Notice how naive rounding can introduce a new crossing — while safe snap always produces a valid configuration.

The Real Complexity

Snap rounding is a solved problem — efficient algorithms exist and are widely implemented. The key results came from a series of papers between 1993 and 2006:

  • The naive approach fails. Simply rounding every vertex to the nearest pixel independently can produce new intersections. Two segments that were disjoint in the exact arrangement can cross after their endpoints move by half a pixel each.
  • The cascade. The correct fix requires processing hot pixels — pixels whose centers lie within 12\frac{1}{2} of a segment. Any such pixel center becomes a vertex, and the segment is split there. This can trigger further hot pixels, so the process must be iterated to convergence. Guibas & Marimont proved it always terminates.
  • Efficient algorithms. Hobby's original algorithm ran in O(n2)O(n^{2}) time. Subsequent work by de Berg et al. and later by Packer (2006) achieved O((n+k)log⁡n)O((n + k) \log n) where kk is the number of intersections in the original arrangement — essentially optimal given the output size.
  • Output complexity. A set of nn segments with kk pairwise intersections produces at most O(n+k)O(n + k) vertices after snap rounding, so the output is no larger than the input arrangement.
  • Precision model. The guarantee holds when coordinates are integers and the grid spacing is 1. Real implementations scale input coordinates to integers first, snap, then scale back.

The connection to broader complexity: computing the arrangement of nn line segments already requires O((n+k)log⁡n)O((n + k) \log n) time by the closest pair argument, so snap rounding adds no asymptotic overhead. The hard part is correctness, not speed.

Where It Matters

The need for numerically robust geometry arises wherever real-world coordinates meet combinatorial algorithms:

  • GIS and map overlays: computing the union or intersection of polygon layers (roads, land use, administrative boundaries) requires snapping thousands of near-coincident vertices. Without snap rounding, overlays crash or produce slivers and holes.
  • VLSI chip layout: routing wires on a chip at nanometer precision uses integer grids by design, and every intersection of wire paths must be topologically exact.
  • Polygon clipping: graphics pipelines clip polygons against viewport boundaries. A numerically inconsistent clip can produce inside-out polygons or missing faces in a 3D render.
  • Computational solid modeling (CAD): boolean operations on 3D solids reduce to 2D arrangements at intersection curves; snap rounding keeps the topology consistent.
  • Mesh generation: triangulating a planar subdivision — needed for finite-element analysis — requires that every vertex lies exactly on its intended edge, which snap rounding guarantees.

Snap rounding sits at the intersection of geometry and closest pair proximity arguments. It shows that even "just rounding a number" is a problem that deserves a careful algorithm.

Conclusion

Snap rounding is a reminder that robustness is not free. Rounding a single coordinate seems trivial, but geometry is combinatorial: moving one point can change which segments cross, which polygons are adjacent, and which topological invariants hold. The naive approach breaks these invariants silently.

The snap-rounding guarantee — that snapping vertices to a pixel grid never introduces new combinatorial crossings — required real insight to achieve and real algorithms to make efficient. It remains one of the clearest examples of a bridge between the exact, symbolic world of combinatorial geometry and the approximate, floating-point world of real computation.

Next time you zoom into a digital map and edges meet precisely at every intersection, or a CAD tool correctly booleans two solids, there is a good chance snap rounding — or one of its descendants — is silently keeping the topology honest.

Share this article

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

Comments

Loading comments...

https://www.kipuhub.com/en/article/snap-rounding/Content licensed under CC BY-NC 4.0.