Snap rounding polygons with a triangulation

Abstract

Geometric algorithms are usually designed based on the assumption of using arbitraryprecision representations. However, in modern computer systems floating-point arithmetic and finite-precision approximation are often used as implementing exact computations would require large computational resources and would be rather slow in the applications. Snap rounding (SR) is a widely used technique to transform representations of infinite precision into fixed-precision formats. It slightly modifies the original geometry of the input in order
to obtain a better organized geometric object arrangement and avoid the issues caused by applying floating-point arithmetic in geometric algorithms. The existing implementations of SR primarily focus on processing sets of line segments, while in practice polygons are of great significance as well yet has not received adequate attention so far. In this thesis, a new method is proposed to perform SR on 2-dimensional polygons. Firstly the input polygons are embedded into a triangulation. Subsequently, the triangulation is tagged with the ID information of polygons and the polygon boundaries are extracted and
stored in a container. The boundaries and the triangulation are then dynamically processed according to the identification of close polygonal vertices and close vertex and boundaries (under a predefined tolerance). After having snapped all the close elements the rounded polygons will be reconstructed from the processed boundaries. The testing results show the proposed method is capable of eliminating small gaps between elements (i.e. vertices and
boundaries) and is adaptable to various inputs. The topological and geometrical properties of polygons are preserved as much as possible. Finally, an overview of the limitations is provided, along with potential directions for future research.