The CGAL class CGAL_Regular_triangulation_2<Gt, Tds> is designed to maintain the regular triangulation of a set of weighted points. The template parameters Gt and Tds stand respectively for a geometric traits class and a triangulation data structure class. Any triangulation data structure that fulfills the requirements of section  can be used for a regular triangulation. The geometric traits class must provide a weighted point type and a power test on these weighted points. The requirements and defaults for the geometric traits and the power point type are list below.

#include <CGAL/Regular_triangulation_2.h>

Inherits From

The functions insert and remove are overwritten to maintain the regular property and the checking function is_valid() is also overwritten to additionally test the local regular property of any pair of neighboring faces.

typedef Gt::Distance
	Distance;
typedef Gt::Line	Line;
typedef Gt::Direction
	Direction;
typedef GT::Ray	Ray;
typedef GT::Bare_point
	Point;
typedef GT::Weighted_point
	Weighted_point;

Creation

CGAL_Regular_triangulation_2<Gt, Tds> rt ( Gt gt = Gt());
	Introduces an empty Delaunay triangulation rt.
CGAL_Regular_triangulation_2<Gt, Tds> rt ( Vertex_handle v; Traits t = Traits());
	Introduces a Regular triangulation rt that is initialized with the vertices and faces that are linked to vertex v. If v has no incident face the triangulation consists only of v. Otherwise v must be the vertex at infinity.

Insertion and Removal

The vertices of the regular triangulation of a set of weighted points $$PW form only a subset of the set of center points of $$PW. Therefore the insertion of a weighted point in a regular triangulation does not necessarily imply the creation of a new vertex. If the new inserted point does not appear as a vertex in the regular triangulation, it is said to be hidden by the face in which the corresponding center point is located. Such a point is stored in a list attached to the hiding face, to be used for later tentative insertions, when future removal of some points implies the destruction of the hiding face.

bool	rt.insert ( Point p, Face_handle f=Face_handle())
		Inserts point p. returns true if a new vertex is created. If a weighted point with the same center point but a different weight already exists in the triangulation, it is removed and replaced by the new point.
bool	rt.insert ( Point p, Locate_type& lt. Face_handle f=Face_handle())
		Same as above. Additionally, parameter lt describes where point p was located before updating the triangulation.
Vertex_handle	rt.push_back ( Point p)
		Equivalent to insert(p).
template < class InputIterator >
int	rt.insert ( InputIterator first, InputIterator last)
		Inserts the points in the range $[.$first, last$.)$. Returns the number of created vertices. Precondition: The value_type of first and last is Point.
int	rt.remove ( Vertex_handle v)
		Removes the vertex from the triangulation and return the number of new vertices created by the insertion of previously hidden points.

Geometric Predicates

CGAL_Oriented_side	rt.power_test ( Face_handle f, Weighted_point p)
		Returns the power test of p with respect to the power circle associated with f

Miscellaneous

bool	rt.is_valid ( bool verbose = false, int level = 0)
		Tests the validity of the triangulation as a CGAL_Triangulation_2 and additionally test the Delaunay property. This method is mainly useful for debugging Delaunay triangulation algorithms designed by the user.