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).
More details on Interated Snap Rounding can be found in the paper Snap Rounding Revisited by Dan Halperin and Eli Packer (see below).
- Eli Packer and Dan Halperin
Iterated Snap Rounding
Computational Geometry: Theory and Applications, 23(2): 209-225, 2002 [link][bibtex]
A preliminary version appeared in Abstracts 17th European Workshop on Computational Geometry (EWCG), pages 82-85, Berlin, 2001 [bibtex]
- Eli Packer
Finite-precision approximation techniques for planar arrangements of line segments
M.Sc. Thesis [pdf] [bibtex].
- D. H. Greene and F. F. Yao, Finite-resolution computational geometry, 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