Search

# Iterated Snap Rounding

Snap rounding is a well known method for converting arbitrary-precision arrangements of segments into a fixed-precision representation.

Given an arrangement of segments whose vertices (end-points and intersections) are represented with arbitrary-precision coordinates, snap rounding proceeds as follows. We tile the plane with a grid of unit squares, pixels, each centered at a point with integer coordinates. A pixel is hot if it contains a vertex of the arrangement. Each vertex of the arrangement is replaced by the center of the hot pixel containing it and each edge e is replaced by the polygonal chain through the centers of the hot pixels met by $$e$$, in the same order as they are met by $$e$$.

In a snap-rounded arrangement, the distance between a vertex and a non-incident edge can be extremely small compared with the width of a pixel in the grid used for rounding. Iterated Snap Rounding is a technique which rounds the arrangement in a similar way as Snap Rounding, but makes sure each vertex is at least half-the-width-of-a-pixel away from any non-incident edge. Iterated Snap Rounding preserves the topology of the original arrangement in the same sense that the original scheme does. However, the guaranteed quality of the approximation degrades. Thus each scheme may be suitable in different situations.

We implemented both schemes. We have examples that demonstrate the difference in rounding between the schemes (see below).

### Examples

Example 1—Congestion

 Input After Snap Rounding After Iterated Snap Rounding The small square inside each image represents a unit pixel

Example 1 Zoomed In

 Input After Snap Rounding After Iterated Snap Rounding The small square inside each image represents a unit pixel

Example 2—Triangulation

Iterated Snap Rounding—Example 2 : Triangulation

 Input After Snap Rounding After Iterated Snap Rounding The small square inside each image represents a unit pixel

Example 2 Zoomed In

 Input After Snap Rounding After Iterated Snap Rounding The small square inside each image represents a unit pixel

Example 3—Pixel Size
Iterated Snap Rounding – Example 3: Pixel Size

Choose Pixel Size

0.5 / 1 / 2

Pixel size = 0.5

pixel size = 1

pixel size = 2

• Eli Packer and Dan Halperin
Iterated Snap Rounding
Computational Geometry: Theory and Applications, 23(2): 209-225,  2002 [link][bibtex]
In Proceedings of the 17th European Workshop on Computational Geometry (EuroCG), pages 82-85, Berlin, 2001 [bibtex]
• Eli Packer
Finite-precision approximation techniques for planar arrangements of line segments
M.Sc. Thesis [pdf] [bibtex].

### Related Work

• D. H. Greene and F. F. Yao,
Finite-resolution computational geometry
In Proceedings of the 27th Annual IEEE Symposium on the Foundation Computer Science, pages 143-15, 1986
• J. Hobby
Practical segment intersection with finite precision output
Computational Geometry: Theory and Applications, 13, pages 199-21, 1999
• M. Goodrich and L. J. Guibas and J. Hershberger and P. Tanenbaum,
Snap Rounding Line Segments Efficiently in Two and Three Dimensions
In Proceedings of the 13th Annual ACM Symposium on Computational Geometry, pages 284-293, 1997
• Leonidas Guibas and David Marimont
Rounding Arrangements Dynamically
International Journal Computational Geometry and Applications, pages 157-176, 1998

Eli Packer