Snap Rounding

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 $A$ to its nearest pixel, the segment connecting $A$ to $B$ moves slightly. That moved segment might now pass through a pixel it didn't touch before, which contains another vertex $C$ that now must be snapped too — triggering more moves. The algorithm must converge and the result must still be topologically correct.

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.

<!-- {{c_html_comment}} -->
<div class="controls">
  <button id="randomize" type="button">{{btn_randomize}}</button>
  <button id="toggle-mode" type="button" class="ghost">{{btn_naive}}</button>
</div>
<canvas id="canvas" width="480" height="340"></canvas>
<div id="status" class="status"></div>
<p class="hint">{{hint_drag}}</p>

/* {{c_css_comment}} */
* { 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; }

// Code not found

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.

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 $\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(n^{2})$ time. Subsequent work by de Berg et al. and later by Packer (2006) achieved $O((n + k) \log n)$ where $k$ is the number of intersections in the original arrangement — essentially optimal given the output size.
• Output complexity. A set of $n$ segments with $k$ pairwise intersections produces at most $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 $n$ line segments already requires $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.

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.

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.