These representations are useful for the efficient traversal of a Voronoi diagram and the computation of parameters of Voronoi cells, such as area and perimeter. For example, an edge must be linked to previous and next edges in a boundary of a cell and additionally, the edge must store at least one link to the cell enclosed by the boundary. The complexity of these representations is associated not only with the data sets, but also with the need to support adjacency relationships between elements of different types of a representation. The widely used boundary-based representations of a Voronoi diagram, such as shown in Figure 2, store sets of sites, cells, edges and vertices. Two adjacent cells have common boundary elements drawn in red. These regions are also called Voronoi cells.įigure 2: Illustration of a boundary-based representation of a Voronoi diagram. Each region has a polygonal boundary that contains all points of the plane nearest to the region site. Boundary-Based Voronoi Diagramīy definition, the Voronoi diagram represents a sub-division of the two dimensional space into regions induced by an input set of points, which are called sites in traditional terminology. The suggested variant of a Voronoi diagram should be useful for the fast development of algorithms that require the facilities of a Voronoi diagram and for the development of advanced and more efficient representations of a Voronoi diagram. The benefits come at the expense of the performance, which is, nevertheless, much better than that of the brute force approach. The main advantages of this approach are the simplicity of the representation, the low cost of development and maintenance, and the adaptability to a wide range of user algorithms. Here, we discuss an affordable and effective Voronoi diagram using interchangeable STL containers. The high cost of development and maintenance of these data structures is a serious obstacle to take advantage of this powerful mathematical concept in practice. Unfortunately, the efficient programming representation of a Voronoi diagram requires quite complex data structures. Figure 1: A Voronoi diagram of a set of points in the plane.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |