# Snap rounding

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Snap_rounding
> Markdown URL: https://mediated.wiki/source/Snap_rounding.md
> Source: https://en.wikipedia.org/wiki/Snap_rounding
> Source revision: 1290228898
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

**Snap rounding** is a method of approximating [line segment](/source/Line_segment) locations by creating a grid and placing each point in the centre of a cell (pixel) of the grid. The method preserves certain topological properties of the arrangement of line segments.

Drawbacks include the potential interpolation of additional vertices in line segments (lines become [polylines](/source/Polyline)), the arbitrary closeness of a point to a non-incident edge, and arbitrary numbers of intersections between input line-segments. The 3 dimensional case is worse, with a polyhedral subdivision of complexity n becoming complexity *[O](/source/Big-O_notation)*(n4).

There are more refined algorithms to cope with some of these issues, for example *iterated snap rounding* guarantees a "large" separation between points and non-incident edges.[1]

## Algorithm

... (please edit). See,[2] [3] and [https://www.cgal.org/](https://www.cgal.org/) ([4][5])

## Properties

- Canonicity:
- Efficiency; A number of efficient implementations exist.

Conversely there are undesirable properties:

- Non-[idempotence](/source/Idempotence): Repeated applications can cause arbitrary drift of points. - Exception on "Stable snap rounding" algorithms, see [https://doi.org/10.1016/j.comgeo.2012.02.011](https://doi.org/10.1016/j.comgeo.2012.02.011)

## See also

- [Snap (computer graphics)](/source/Snap_(computer_graphics))

## References

1. Csaba D. Toth; Joseph O'Rourke; Jacob E. Goodman (13 April 2004). *Handbook of Discrete and Computational Geometry, Second Edition*. CRC Press. pp. 552–. ISBN 978-1-4200-3531-5.

1. L. J. Guibas & D. H. Marimont (1998). "Rounding arrangements dynamically". *Int. J. Comput. Geom. Appl.*. **8** (2): 157–176. [doi:10.1142/S0218195998000096](https://doi.org/10.1142/S0218195998000096)

1. [Efficient Snap-Rounding with Integer Arithmetic](http://cccg.ca/proceedings/2007/07a1full.pdf), Binay K. Bhattacharya and Jeff Sember

1. CGAL Guide [https://doc.cgal.org/latest/Snap_rounding_2/index.html](https://doc.cgal.org/latest/Snap_rounding_2/index.html)

1. CGAL Implementation [https://doc.cgal.org/latest/Snap_rounding_2/group__PkgSnapRounding2Ref.html](https://doc.cgal.org/latest/Snap_rounding_2/group__PkgSnapRounding2Ref.html)

---
Adapted from the Wikipedia article [Snap rounding](https://en.wikipedia.org/wiki/Snap_rounding) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Snap_rounding?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.