This paper presents a new algorithm called Snap Rounding with Restore (SRR), which aims to make ge- ometric 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 eliminat- ing from the snap rounded arrangement the configurations in which the distance between a vertex and a non-incident 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, both under the viewpoint of the distance from the original segments and of the conservation of their topological structure. The paper 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 both robustness, a guaranteed geometric approximation and a good topological approximation.
Snap Rounding with Restore: an Algorithm for Producing Robust Geometric Datasets
BELUSSI, Alberto;MIGLIORINI, Sara;
2016-01-01
Abstract
This paper presents a new algorithm called Snap Rounding with Restore (SRR), which aims to make ge- ometric 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 eliminat- ing from the snap rounded arrangement the configurations in which the distance between a vertex and a non-incident 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, both under the viewpoint of the distance from the original segments and of the conservation of their topological structure. The paper 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 both robustness, a guaranteed geometric approximation and a good topological approximation.File | Dimensione | Formato | |
---|---|---|---|
00_snap_rounding_finale.pdf
accesso aperto
Tipologia:
Documento in Post-print
Licenza:
Creative commons
Dimensione
12.3 MB
Formato
Adobe PDF
|
12.3 MB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.