CGAL::Hyperbolic_Delaunay_triangulation_2< Gt, Tds > Class Template Reference

#include <CGAL/Hyperbolic_Delaunay_triangulation_2.h>

Inherits Delaunay_triangulation_2< Gt, Tds >.

Definition

template<class Gt, class Tds>
class CGAL::Hyperbolic_Delaunay_triangulation_2< Gt, Tds >

The class Hyperbolic_Delaunay_triangulation_2 is the main class of the 2D Hyperbolic Delaunay Triangulations package.

It is designed to represent Delaunay triangulations of sets of points in the hyperbolic plane. The hyperbolic plane is represented in the Poincaré disk model.

Template Parameters

Gt	is the geometric traits class and must be a model of HyperbolicDelaunayTriangulationTraits_2.
Tds	is the triangulation graph data structure and must be a model of TriangulationDataStructure_2 whose vertex and face are models of TriangulationVertexBase_2 and HyperbolicTriangulationFaceBase_2, respectively. It defaults to: CGAL::Triangulation_data_structure_2< CGAL::Triangulation_vertex_base_2<Gt>, CGAL::Hyperbolic_triangulation_face_base_2<Gt> >

See also

Delaunay_triangulation_2

Examples

Hyperbolic_triangulation_2/ht2_example.cpp, and Hyperbolic_triangulation_2/ht2_example_color.cpp.

Enums
The enumeration Locate_type is defined to specify which case occurs when locating a point in the triangulation.
enum	Locate_type {   VERTEX = 0 , EDGE , FACE , OUTSIDE_CONVEX_HULL ,   OUTSIDE_AFFINE_HULL }

Types
typedef Gt	Geom_traits
typedef Tds	Triangulation_data_structure
typedef Triangulation_data_structure::size_type	size_type
	Size type (integral unsigned).
typedef Geom_traits::Hyperbolic_point_2	Point
typedef Geom_traits::Hyperbolic_triangle_2	Hyperbolic_triangle
The following types are defined to give access to the elements of the triangulation:
typedef Triangulation_data_structure::Vertex_handle	Vertex_handle
typedef Triangulation_data_structure::Face_handle	Face_handle
typedef Triangulation_data_structure::Edge	Edge
The following types are defined for use in the construction of the Voronoi diagram:
typedef Geom_traits::Hyperbolic_Voronoi_point_2	Hyperbolic_Voronoi_point
typedef Geom_traits::Hyperbolic_segment_2	Hyperbolic_segment
The following iterator and circulator types are defined to give access over hyperbolic faces and edges:
typedef Triangulation_data_structure::Face_iterator	All_faces_iterator
typedef Triangulation_data_structure::Edge_iterator	All_edges_iterator
typedef Triangulation_data_structure::Vertex_iterator	All_vertices_iterator
typedef Triangulation_data_structure::Vertex_circulator	Vertex_circulator

Creation
	Hyperbolic_Delaunay_triangulation_2 (const Geom_traits &gt=Geom_traits())
	Default constructor
	Hyperbolic_Delaunay_triangulation_2 (const Hyperbolic_Delaunay_triangulation_2< Gt, Tds > &tr)
	Copy constructor.
template<class InputIterator >
	Hyperbolic_Delaunay_triangulation_2 (InputIterator first, InputIterator last, const Geom_traits &gt=Geom_traits())
	Equivalent to creating an empty triangulation and calling insert(first, last).

Assignment
Hyperbolic_Delaunay_triangulation_2 &	operator= (Hyperbolic_Delaunay_triangulation_2 tr)
	The triangulation tr is duplicated, and modifying the copy after the duplication does not modify the original.
void	swap (Hyperbolic_Delaunay_triangulation_2 &tr)
	The triangulation is swapped with tr.
void	clear ()
	Deletes all vertices and faces of the triangulation.
bool	operator== (const Hyperbolic_Delaunay_triangulation_2< Gt, Tds > &t1, const Hyperbolic_Delaunay_triangulation_2< Gt, Tds > &t2)
	Equality operator.
bool	operator!= (const Hyperbolic_Delaunay_triangulation_2< Gt, Tds > &t1, const Hyperbolic_Delaunay_triangulation_2< Gt, Tds > &t2)
	Inequality operator.

Access functions
const Geom_traits &	geom_traits () const
	Returns a const reference to the geometric traits object.
const Triangulation_data_structure &	tds () const
	Returns a const reference to the triangulation data structure.
Triangulation_data_structure &	tds ()
	Returns a reference to the triangulation data structure.
bool	is_valid ()
	Checks the combinatorial validity of the triangulation, the validity of its geometric embedding, and also that all edges and faces are Delaunay hyperbolic.
int	dimension () const
	Returns the dimension of the affine hull.
size_type	number_of_vertices () const
	Returns the number of vertices.
size_type	number_of_hyperbolic_edges () const
	Returns the number of hyperbolic edges.
size_type	number_of_hyperbolic_faces () const
	Returns the number of hyperbolic faces.

Geometric access functions
Hyperbolic_triangle	hyperbolic_triangle (const Face_handle f) const
Hyperbolic_segment	hyperbolic_segment (const Face_handle f, const int i) const
	Returns the hyperbolic segment formed by the vertices of the edge (f, i).
Hyperbolic_segment	hyperbolic_segment (const Edge &e) const
	Returns the hyperbolic segment formed by the vertices of edge e.

Insertion
Vertex_handle	insert (const Point &p, Face_handle start=Face_handle())
	Inserts the point p in the triangulation.
template<class InputIterator >
std::ptrdiff_t	insert (InputIterator first, InputIterator last)
	Inserts the points in the range [first,last) into the triangulation.

Removal
void	remove (Vertex_handle v)
	Removes the vertex v from the triangulation.
template<class VertexRemoveIterator >
void	remove (VertexRemoveIterator first, VertexRemoveIterator last)
	Removes the vertices in the iterator range [first, last) from the triangulation.

Point Location
Face_handle	locate (const Point &query, const Face_handle hint=Face_handle()) const
	Locates the point query in the triangulation.
Face_handle	locate (const Point &query, Locate_type &lt, int &li, Face_handle hint=Face_handle()) const
	Same as above.

Queries
template<class OutputItFaces >
OutputItFaces	find_conflicts (const Point &p, OutputItFaces fit, Face_handle start=Face_handle()) const
	Computes the conflict zone induced by p.

Vertex, Face and Edge iterators and circulators
All_vertices_iterator	all_vertices_begin () const
All_vertices_iterator	all_vertices_end () const
All_edges_iterator	all_edges_begin () const
All_edges_iterator	all_edges_end () const
All_faces_iterator	all_faces_begin () const
All_faces_iterator	all_faces_end () const
Vertex_circulator	adjacent_vertices (Vertex_handle v) const

Voronoi Diagram
Users should use a kernel with exact constructions in order to guarantee the computation of the Voronoi diagram (as opposed to computing the triangulation only, which requires only exact predicates).
Hyperbolic_Voronoi_point	dual (Face_handle f) const
	Returns the hyperbolic center of the circumdisk of f.
Hyperbolic_segment	dual (const Edge &e) const
	Returns the hyperbolic segment that is dual to e.
Hyperbolic_segment	dual (Face_handle f, int i) const
	Returns the hyperbolic segment that is dual to the edge (f,i).

Member Typedef Documentation

All_edges_iterator

template<class Gt , class Tds >

typedef Triangulation_data_structure::Edge_iterator CGAL::Hyperbolic_Delaunay_triangulation_2< Gt, Tds >::All_edges_iterator

All_faces_iterator

template<class Gt , class Tds >

typedef Triangulation_data_structure::Face_iterator CGAL::Hyperbolic_Delaunay_triangulation_2< Gt, Tds >::All_faces_iterator

All_vertices_iterator

template<class Gt , class Tds >

typedef Triangulation_data_structure::Vertex_iterator CGAL::Hyperbolic_Delaunay_triangulation_2< Gt, Tds >::All_vertices_iterator

Edge

template<class Gt , class Tds >

typedef Triangulation_data_structure::Edge CGAL::Hyperbolic_Delaunay_triangulation_2< Gt, Tds >::Edge

Face_handle

template<class Gt , class Tds >

typedef Triangulation_data_structure::Face_handle CGAL::Hyperbolic_Delaunay_triangulation_2< Gt, Tds >::Face_handle

Geom_traits

template<class Gt , class Tds >

typedef Gt CGAL::Hyperbolic_Delaunay_triangulation_2< Gt, Tds >::Geom_traits

Hyperbolic_segment

template<class Gt , class Tds >

typedef Geom_traits::Hyperbolic_segment_2 CGAL::Hyperbolic_Delaunay_triangulation_2< Gt, Tds >::Hyperbolic_segment

Hyperbolic_triangle

template<class Gt , class Tds >

typedef Geom_traits::Hyperbolic_triangle_2 CGAL::Hyperbolic_Delaunay_triangulation_2< Gt, Tds >::Hyperbolic_triangle

Hyperbolic_Voronoi_point

template<class Gt , class Tds >

typedef Geom_traits::Hyperbolic_Voronoi_point_2 CGAL::Hyperbolic_Delaunay_triangulation_2< Gt, Tds >::Hyperbolic_Voronoi_point

Point

template<class Gt , class Tds >

typedef Geom_traits::Hyperbolic_point_2 CGAL::Hyperbolic_Delaunay_triangulation_2< Gt, Tds >::Point

size_type

template<class Gt , class Tds >

typedef Triangulation_data_structure::size_type CGAL::Hyperbolic_Delaunay_triangulation_2< Gt, Tds >::size_type

Size type (integral unsigned).

Triangulation_data_structure

template<class Gt , class Tds >

typedef Tds CGAL::Hyperbolic_Delaunay_triangulation_2< Gt, Tds >::Triangulation_data_structure

Vertex_circulator

template<class Gt , class Tds >

typedef Triangulation_data_structure::Vertex_circulator CGAL::Hyperbolic_Delaunay_triangulation_2< Gt, Tds >::Vertex_circulator

Vertex_handle

template<class Gt , class Tds >

typedef Triangulation_data_structure::Vertex_handle CGAL::Hyperbolic_Delaunay_triangulation_2< Gt, Tds >::Vertex_handle

Member Enumeration Documentation

Locate_type

template<class Gt , class Tds >

enum CGAL::Hyperbolic_Delaunay_triangulation_2::Locate_type

Enumerator
VERTEX
EDGE
FACE
OUTSIDE_CONVEX_HULL
OUTSIDE_AFFINE_HULL

Constructor & Destructor Documentation

Hyperbolic_Delaunay_triangulation_2() [1/3]

template<class Gt , class Tds >

CGAL::Hyperbolic_Delaunay_triangulation_2< Gt, Tds >::Hyperbolic_Delaunay_triangulation_2

(

const Geom_traits &

gt = Geom_traits()

)

Default constructor

Hyperbolic_Delaunay_triangulation_2() [2/3]

template<class Gt , class Tds >

CGAL::Hyperbolic_Delaunay_triangulation_2< Gt, Tds >::Hyperbolic_Delaunay_triangulation_2

(

const Hyperbolic_Delaunay_triangulation_2< Gt, Tds > &

tr

)

Copy constructor.

Hyperbolic_Delaunay_triangulation_2() [3/3]

template<class Gt , class Tds >

template<class InputIterator >

CGAL::Hyperbolic_Delaunay_triangulation_2< Gt, Tds >::Hyperbolic_Delaunay_triangulation_2	(	InputIterator	first,
		InputIterator	last,
		const Geom_traits &	gt = Geom_traits()
	)

Equivalent to creating an empty triangulation and calling insert(first, last).

Member Function Documentation

adjacent_vertices()

template<class Gt , class Tds >

Vertex_circulator CGAL::Hyperbolic_Delaunay_triangulation_2< Gt, Tds >::adjacent_vertices

(

Vertex_handle

v

)

const

all_edges_begin()

template<class Gt , class Tds >

All_edges_iterator CGAL::Hyperbolic_Delaunay_triangulation_2< Gt, Tds >::all_edges_begin

(

)

const

all_edges_end()

template<class Gt , class Tds >

All_edges_iterator CGAL::Hyperbolic_Delaunay_triangulation_2< Gt, Tds >::all_edges_end

(

)

const

all_faces_begin()

template<class Gt , class Tds >

All_faces_iterator CGAL::Hyperbolic_Delaunay_triangulation_2< Gt, Tds >::all_faces_begin

(

)

const

all_faces_end()

template<class Gt , class Tds >

All_faces_iterator CGAL::Hyperbolic_Delaunay_triangulation_2< Gt, Tds >::all_faces_end

(

)

const

all_vertices_begin()

template<class Gt , class Tds >

All_vertices_iterator CGAL::Hyperbolic_Delaunay_triangulation_2< Gt, Tds >::all_vertices_begin

(

)

const

all_vertices_end()

template<class Gt , class Tds >

All_vertices_iterator CGAL::Hyperbolic_Delaunay_triangulation_2< Gt, Tds >::all_vertices_end

(

)

const

clear()

template<class Gt , class Tds >

void CGAL::Hyperbolic_Delaunay_triangulation_2< Gt, Tds >::clear

(

)

Deletes all vertices and faces of the triangulation.

dimension()

template<class Gt , class Tds >

int CGAL::Hyperbolic_Delaunay_triangulation_2< Gt, Tds >::dimension

(

)

const

Returns the dimension of the affine hull.

dual() [1/3]

template<class Gt , class Tds >

Hyperbolic_segment CGAL::Hyperbolic_Delaunay_triangulation_2< Gt, Tds >::dual

(

const Edge &

e

)

const

Returns the hyperbolic segment that is dual to e.

dual() [2/3]

template<class Gt , class Tds >

Hyperbolic_Voronoi_point CGAL::Hyperbolic_Delaunay_triangulation_2< Gt, Tds >::dual

(

Face_handle

f

)

const

Returns the hyperbolic center of the circumdisk of f.

Precondition

f is hyperbolic

dual() [3/3]

template<class Gt , class Tds >

Hyperbolic_segment CGAL::Hyperbolic_Delaunay_triangulation_2< Gt, Tds >::dual	(	Face_handle	f,
		int	i
	)		const

Returns the hyperbolic segment that is dual to the edge (f,i).

Precondition

f is hyperbolic

find_conflicts()

template<class Gt , class Tds >

template<class OutputItFaces >

OutputItFaces CGAL::Hyperbolic_Delaunay_triangulation_2< Gt, Tds >::find_conflicts	(	const Point &	p,
		OutputItFaces	fit,
		Face_handle	start = Face_handle()
	)		const

Computes the conflict zone induced by p.

If the optional parameter start is given, then it must be a face in conflict with p. Returns an iterator on the faces of the triangulation in conflict with p.

geom_traits()

template<class Gt , class Tds >

const Geom_traits & CGAL::Hyperbolic_Delaunay_triangulation_2< Gt, Tds >::geom_traits

(

)

const

Returns a const reference to the geometric traits object.

hyperbolic_segment() [1/2]

template<class Gt , class Tds >

Hyperbolic_segment CGAL::Hyperbolic_Delaunay_triangulation_2< Gt, Tds >::hyperbolic_segment

(

const Edge &

e

)

const

Returns the hyperbolic segment formed by the vertices of edge e.

hyperbolic_segment() [2/2]

template<class Gt , class Tds >

Hyperbolic_segment CGAL::Hyperbolic_Delaunay_triangulation_2< Gt, Tds >::hyperbolic_segment	(	const Face_handle	f,
		const int	i
	)		const

Returns the hyperbolic segment formed by the vertices of the edge (f, i).

hyperbolic_triangle()

template<class Gt , class Tds >

Hyperbolic_triangle CGAL::Hyperbolic_Delaunay_triangulation_2< Gt, Tds >::hyperbolic_triangle

(

const Face_handle

f

)

const

insert() [1/2]

template<class Gt , class Tds >

Vertex_handle CGAL::Hyperbolic_Delaunay_triangulation_2< Gt, Tds >::insert	(	const Point &	p,
		Face_handle	start = Face_handle()
	)

Inserts the point p in the triangulation.

If the point p coincides with an existing vertex, then the vertex is returned and the triangulation is not modified. The optional parameter start is used to initialize the location of p.

insert() [2/2]

template<class Gt , class Tds >

template<class InputIterator >

std::ptrdiff_t CGAL::Hyperbolic_Delaunay_triangulation_2< Gt, Tds >::insert	(	InputIterator	first,
		InputIterator	last
	)

Inserts the points in the range [first,last) into the triangulation.

Returns the number of inserted points. Note that this function is not guaranteed to insert the points following the order of InputIterator, as spatial_sort() is used to improve efficiency.

Template Parameters

InputIterator

must be an input iterator with the value type Point.

is_valid()

template<class Gt , class Tds >

bool CGAL::Hyperbolic_Delaunay_triangulation_2< Gt, Tds >::is_valid

(

)

Checks the combinatorial validity of the triangulation, the validity of its geometric embedding, and also that all edges and faces are Delaunay hyperbolic.

locate() [1/2]

template<class Gt , class Tds >

Face_handle CGAL::Hyperbolic_Delaunay_triangulation_2< Gt, Tds >::locate	(	const Point &	query,
		const Face_handle	hint = Face_handle()
	)		const

Locates the point query in the triangulation.

If the point query lies inside the hyperbolic convex hull of the points of the triangulation, then the hyperbolic face that contains the query in its interior is returned.

If query lies on a vertex or on an edge, then one of the faces having query on its boundary is returned.

Todo:

verify case when query lies on dangling edge!

If query lies outside of the convex hull of the points of the triangulation, then a default-constructed Face_handle() is returned.

The optional argument hint is used as a starting place for the search.

locate() [2/2]

template<class Gt , class Tds >

Face_handle CGAL::Hyperbolic_Delaunay_triangulation_2< Gt, Tds >::locate	(	const Point &	query,
		Locate_type &	lt,
		int &	li,
		Face_handle	hint = Face_handle()
	)		const

Same as above.

The variable lt contains information about the element in which query has been located. See the enumeration Locate_type for details.

If lt is Locate_type::VERTEX, then the variable li contains the index of the vertex in the returned face. If lt is Locate_type::EDGE, then li is the index of the edge in the returned face.

number_of_hyperbolic_edges()

template<class Gt , class Tds >

size_type CGAL::Hyperbolic_Delaunay_triangulation_2< Gt, Tds >::number_of_hyperbolic_edges

(

)

const

Returns the number of hyperbolic edges.

number_of_hyperbolic_faces()

template<class Gt , class Tds >

size_type CGAL::Hyperbolic_Delaunay_triangulation_2< Gt, Tds >::number_of_hyperbolic_faces

(

)

const

Returns the number of hyperbolic faces.

number_of_vertices()

template<class Gt , class Tds >

size_type CGAL::Hyperbolic_Delaunay_triangulation_2< Gt, Tds >::number_of_vertices

(

)

const

Returns the number of vertices.

operator!=()

template<class Gt , class Tds >

bool CGAL::Hyperbolic_Delaunay_triangulation_2< Gt, Tds >::operator!=	(	const Hyperbolic_Delaunay_triangulation_2< Gt, Tds > &	t1,
		const Hyperbolic_Delaunay_triangulation_2< Gt, Tds > &	t2
	)

Inequality operator.

Todo:

implement!

operator=()

template<class Gt , class Tds >

Hyperbolic_Delaunay_triangulation_2 & CGAL::Hyperbolic_Delaunay_triangulation_2< Gt, Tds >::operator=

(

Hyperbolic_Delaunay_triangulation_2< Gt, Tds >

tr

)

The triangulation tr is duplicated, and modifying the copy after the duplication does not modify the original.

operator==()

template<class Gt , class Tds >

bool CGAL::Hyperbolic_Delaunay_triangulation_2< Gt, Tds >::operator==	(	const Hyperbolic_Delaunay_triangulation_2< Gt, Tds > &	t1,
		const Hyperbolic_Delaunay_triangulation_2< Gt, Tds > &	t2
	)

Equality operator.

Todo:

implement!

remove() [1/2]

template<class Gt , class Tds >

void CGAL::Hyperbolic_Delaunay_triangulation_2< Gt, Tds >::remove

(

Vertex_handle

v

)

Removes the vertex v from the triangulation.

Precondition

v is a vertex of the triangulation.

remove() [2/2]

template<class Gt , class Tds >

template<class VertexRemoveIterator >

void CGAL::Hyperbolic_Delaunay_triangulation_2< Gt, Tds >::remove	(	VertexRemoveIterator	first,
		VertexRemoveIterator	last
	)

Removes the vertices in the iterator range [first, last) from the triangulation.

Precondition

all vertices in [first, last) are vertices of the triangulation.

swap()

template<class Gt , class Tds >

void CGAL::Hyperbolic_Delaunay_triangulation_2< Gt, Tds >::swap

(

Hyperbolic_Delaunay_triangulation_2< Gt, Tds > &

tr

)

The triangulation is swapped with tr.

tds() [1/2]

template<class Gt , class Tds >

Triangulation_data_structure & CGAL::Hyperbolic_Delaunay_triangulation_2< Gt, Tds >::tds

(

)

Returns a reference to the triangulation data structure.

tds() [2/2]

template<class Gt , class Tds >

const Triangulation_data_structure & CGAL::Hyperbolic_Delaunay_triangulation_2< Gt, Tds >::tds

(

)

const

Returns a const reference to the triangulation data structure.