If this is the case we call the site hidden (these are the black circles in Figure 53.1 ).
This can also happen in the case of the power diagram, whose dual is the regular triangulation (see Section Regular Triangulations ). Unlike the case of points, however, it is possible that a site \( P_i\) might have an empty cell. It can easily be seen that it is a generalization of the Voronoi diagram for points, which can actually be obtained if all the weights \( w_i\) are equal. Where \( \|\cdot\|\) denotes the Euclidean norm. The distance \( \delta(x, P_i)\) of a point \( x\) in the plane to a site \( P_i\) is defined as: The cell of a site \( P_i\) is the locus of points on the plane that are closer to \( P_i\) than any other site \( P_j\), \( j\neq i\). It is a subdivision of the plane into connected regions, called cells, associated with the sites (see Figure 53.1 (left)). The Apollonius diagram is defined over a set of sites \( P_i=(c_i,w_i)\), \( i=1,\ldots,n\), where \( c_i\) is the point and \( w_i\) the weight of \( P_i\). The interested reader may want to refer to the paper by Karavelas and Yvinec for the general idea as well as the details of the algorithm implemented.īefore describing the details of the implementation we make a brief introduction to the theory of Apollonius diagrams. The corresponding CGAL class is called Apollonius_graph_2 and will be discussed in more detail in the sequel. The algorithm that has been implemented is dynamic, which means that we can perform insertions and deletions on line. The 2D Apollonius graph class of CGAL is designed to compute the dual of the Apollonius diagram or, as it is also known, the Additively weighted Voronoi diagram. Figure 53.1 The Apollonius diagram (left) and its dual the Apollonius graph (right).
0 kommentar(er)
