Voronoi diagrams: Robust and efficient implementation.

摘要

The Voronoi diagram has been a long studied geometric construct that embodies the set of points equidistant from one or more geometric primitives. These primitives may consist of points, lines, curves, polygons, or other more complex geometric primitives. Voronoi diagrams are utilized to solve a large and diverse set of engineering problems where detailed interpretation or analysis of a geometric space is required. Although this construct is easily understood and quite simple in principle, because it is dependent upon mathematically exact distance computation, its algorithmic formulation becomes more difficult when using microprocessors that only provide facilities for approximate IEEE floating point representations. One solution to this problem has been to utilize a model of exact computation implemented as an additional layer on top of the microprocessor's native floating point facilities. However, such solutions introduce significant amounts of computational overhead where time-efficient implementation becomes impractical for many applications. Another solution, focused on here, has been to carefully account for degeneracies resultant from inexact IEEE floating point representation to permit both a fast and robust computation of the Voronoi diagram. More specifically, previous results shown by Held and others [15, 18, 17] are incorporated and built upon to describe a reliable and performance oriented algorithm for construction of Voronoi diagrams. The fundamental elements of this approach are based upon consideration of general topological properties in addition to the less reliable IEEE-floating-point-based distance computation. After a comprehensive presentation of the algorithm developed here, a summary of its application within the areas of embroidery design automation and structural indexing is presented. This material is based upon work supported by the National Science Foundation under Grant No. 0239356