## 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

_{i}is 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:

Π(p_{i}, w_{i}, p_{j}, w_{j}) = p_{i}p_{j} ^{2} - w_{i} - w_{j} . |

_{i}, w

_{i}, p

_{j}, 0) is simply the power of point p

_{j}with 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

_{i}p

_{j}p

_{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

| |
| | |

_{i}p

_{j}p

_{k}and p

_{i}p

_{j}p

_{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}

^{2}- 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**To solve this, there is also another model of the traits concept,

*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.*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_2*and 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;

}

## No comments:

## Post a Comment