Snap Rounding with Restore: An Algorithm for Producing Robust Geometric Datasets

This article presents a new algorithm called Snap Rounding with Restore (SRR), which aims to make geometric datasets robust and to increase the quality of geometric approximation and the preservation of topological structure. It is based on the well-known Snap Rounding algorithm but improves it by eliminating from the snap rounded arrangement the configurations in which the distance between a vertex and a nonincident edge is smaller than half the width of a pixel of the rounding grid. Therefore, the goal of SRR is exactly the same as the goal of another algorithm, Iterated Snap Rounding (ISR), and of its evolution, Iterated Snap Rounding with Bounded Drift (ISRBD). However, SRR produces an output with a quality of approximation that is on average better than ISRBD, under the viewpoint both of the distance from the original segments and of the conservation of their topological structure. The article also reports some cases where ISRBD, notwithstanding the bounded drift, produces strong topological modifications while SRR does not. A statistical analysis on a large collection of input datasets confirms these differences. It follows that the proposed Snap Rounding with Restore algorithm is suitable for applications that require robustness, a guaranteed geometric approximation, and a good topological approximation.