37.6 Lưới tam giác đơn giản Regular Triangulations

37.6   Regular Triangulations

37.6.1   Description

Let PW = {(p_i, w_i) | i = 1, … , n } be a set of weighted points where each p_i is a point and each w_iis a scalar called the weight of point p_i. Alternatively, each weighted point (p_i, w_i) can be regarded as a sphere (or a circle, depending on the dimensionality of p_i) with center p_i and radius r_i=√w_i. The power diagram of the set PW is a space partition in which each cell corresponds to a sphere (p_i, w_i) of PWand is the locus of points p whose power with respect to (p_i, w_i)is less than its power with respect to any other sphere in PW. In the two-dimensional space, the dual of this diagram is a triangulation whose domain covers the convex hull of the set P= { p_i | i = 1, … , n } of center points and whose vertices form a subset of P. Such a triangulation is called a regular triangulation. Three points p_i, p_j and p_k of Pform a triangle in the regular triangulation of PWiff there is a point p of the plane with equal powers with respect to (p_i, w_i), (p_j, w_j)and (p_k, w_k) and such that this power is less than the power of pwith respect to any other sphere in PW.
Let us defined the power product of two weighted points (p_i, w_i) and (p_j, w_j) as:

Π(pi, wi, pj, wj) = pipj 2 - wi - wj .

Π(p_i, w_i, p_j, 0) is simply the power of point p_jwith respect to the sphere (p_i, w_i), and two weighted points are said to be orthogonal if their power product is null. The power circle of three weighted points (p_i, w_i), (p_j, w_j)and (p_k, w_k) is defined as the unique circle (π, ω) orthogonal to (p_i, w_i), (p_j, w_j)and (p_k, w_k). The regular triangulation of the sets PWsatisfies the following regular property (which just reduces to the Delaunay property when all the weights are null): a triangle p_ip_jp_k is a face of the regular triangulation of PW iff the power product of any weighted point (p_l, w_l) of PW with the power circle of (p_i, w_i), (p_j, w_j) and (p_k, w_k) is positive or null. We call power test of (p_i, w_i), (p_j, w_j), (p_k, w_k), and (p_l, w_l), the predicates which amount to compute the sign of the power product of (p_l, w_l) with respect to the power circle of (p_i, w_i), (p_j, w_j) and (p_k, w_k). This predicate amounts to computing the sign of the following determinant

|

1 xi yi xi 2 + yi 2 - wi 1 xj yj xj 2 + yj 2 - wj 1 xk yk xk 2 + yk 2 - wk 1 xl yl xl 2 + yl 2 - wl

|

A pair of neighboring faces p_ip_jp_kand p_ip_jp_l is said to be locally regular (with respect to the weights in PW) if the power test of (p_i, w_i), (p_j, w_j), (p_k, w_k), and (p_l, w_l) is positive. A classical result of computational geometry establishes that a triangulation of the convex hull of Psuch that any pair of neighboring faces is regular with respect to PW, is a regular triangulation of PW.
Alternatively, the regular triangulation of the weighted points set PWcan be obtained as the projection on the two dimensional plane of the convex hull of the set of three dimensional points P'= { (p_i,p_i ² - w_i ) | i = 1, … , n }.
The class Regular_triangulation_2<Traits, Tds> is designed to maintain the regular triangulation of a set of 2d weighted points. It derives from the class Triangulation_2<Traits, Tds>. The functions insert and remove are overwritten to handle weighted points and maintain the regular property. The function move is not overwritten and thus does not preserve the regular property. The vertices of the regular triangulation of a set of weighted points PW correspond only to a subset of PW. Some of the input weighted points have no cell in the dual power diagrams and therefore do not correspond to a vertex of the regular triangulation. Such a point is called a hidden point. Because hidden points can reappear later on as vertices when some other point is removed, they have to be stored somewhere. The regular triangulation store those points in special vertices, called hidden vertices. A hidden point can reappear as vertex of the triangulation only when the two dimensional face that hides it is removed from the triangulation. To deal with this feature, each face of a regular triangulation stores a list of hidden vertices. The points in those vertices are reinserted in the triangulation when the face is removed.
Regular triangulation have member functions to construct the vertices and edges of the dual power diagrams.

The Geometric Traits

The geometric traits of a regular triangulation must provide a weighted point type and a power test on these weighted points. The concept RegularTriangulationTraits_2, is a refinement of the concept TriangulationTraits_2. Cgal provides the class Regular_triangulation_euclidean_traits_2<Rep,Weight>which is a model for the traits concept RegularTriangulationTraits_2. The class Regular_triangulation_euclidean_traits_2<Rep,Weight>derives from the class Triangulation_euclidean_traits_2<Rep>and uses a Weighted_point type derived from the type Point_2 of Triangulation_euclidean_traits_2<Rep>. Note that, since the type Weighted_point is not defined in Cgal kernels, plugging a filtered kernel such as Exact_predicates_exact_constructions_kernel in Regular_triangulation_euclidean_traits_2<K,Weight> will in fact not provide exact predicates on weighted points.To solve this, there is also another model of the traits concept, Regular_triangulation_filtered_traits_2<FK>, which is providing filtered predicates (exact and efficient). The argument FK must be a model of the Kernel concept, and it is also restricted to be a instance of the Filtered_kernel template.

The Vertex Type and Face Type of a Regular Triangulation

The base vertex type of a regular triangulation includes a Boolean data member to mark the hidden state of the vertex. Therefore Cgal defines the concept RegularTriangulationVertexBase_2 which refine the concept TriangulationVertexBase_2and provides a default model for this concept.
The base face type of a regular triangulation is required to provide a list of hidden vertices, designed to store the points hidden by the face. It has to be a model of the concept RegularTriangulationFaceBase_2. Cgal provides the templated class Regular_triangulation_face_base_2<Traits>as a default base class for faces of regular triangulations.

37.6.2   Example: a Regular Triangulation

The following code creates a regular triangulation of a set of weighted points and output the number of vertices and the number of hidden vertices.

File: examples/Triangulation_2/regular.cpp

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Regular_triangulation_euclidean_traits_2.h>
#include <CGAL/Regular_triangulation_filtered_traits_2.h>
#include <CGAL/Regular_triangulation_2.h>

#include <fstream>

typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Regular_triangulation_filtered_traits_2<K>  Traits;
typedef CGAL::Regular_triangulation_2<Traits> Regular_triangulation;

int main()
{
   std::ifstream in("data/regular.cin");

   Regular_triangulation::Weighted_point wp;
   int count = 0;
   std::vector<Regular_triangulation::Weighted_point> wpoints;
   while(in >> wp){
       count++;
     wpoints.push_back(wp);
   }
   Regular_triangulation rt(wpoints.begin(), wpoints.end());
   rt.is_valid();
   std::cout << "number of inserted points : " << count << std::endl;
   std::cout << "number of vertices :  " ;
   std::cout << rt.number_of_vertices() << std::endl;
   std::cout << "number of hidden vertices :  " ;
   std::cout << rt.number_of_hidden_vertices() << std::endl;
   return 0;
}