An instance $$T of data type Point_set_2<Traits> is a planar embedded bidirected graph representing the Delaunay Triangulation of its vertex set. The position of a vertex $$v is given by $$T.pos(v) and we use $$S = { T.pos(v) v T } to denote the underlying point set. Each face of $$T (except for the outer face) is a triangle whose circumscribing circle does not contain any point of $$S in its interior. For every edge $$e, the sequence

$$e, T.face_cycle_succ(e), T.face_cycle_succ(T.face_cycle_succ(e)),...

traces the boundary of the face to the left of $$e. The edges of the outer face of $$T form the convex hull of $$S; the trace of the convex hull is clockwise. The subgraph obtained from $$T by removing all diagonals of co-circular quadrilaterals is called the Delaunay Diagram of $$S.

The class Point_set_2<Traits> provides operations for inserting and deleting points, point location, nearest neighbor searches, and navigation in both the triangulation and the diagram.

Note that the Point_set_2<Traits> is derived from the LEDA GRAPH class (Parameterized Graphs). That means that it provides all constant graph operations (like $$reversal, $$all_edges, ...). See the LEDA user manual or LEDA book  [MN99] for more details.

Be aware that the nearest neighbor queries for a point (not for a node) and the range search queries for circles, triangles, and rectangles are non-const operations and modify the underlying graph. The set of nodes and edges is not changed; however, it is not guaranteed that the underlying Delaunay triangulation is unchanged.

The Point_set_2<Traits> class of CGAL depends on a template parameter standing for a geometric traits class. This traits class has to provide the geometric objects needed in Point_set_2<Traits> and geometric predicates on these objects.

Types

Point_set_2<Traits>::Vertex
	the vertex type.
Point_set_2<Traits>::Edge
	the edge type.

Creation

Point_set_2<Traits> T;
	creates an empty Point_set_2<Traits> .
Point_set_2<Traits> T ( std::list<Point> S);
	creates a Point_set_2<Traits> T of the points in $$S. If $$S contains multiple occurrences of points only the last occurrence of each point is retained.
template<class InputIterator>
Point_set_2<Traits> T ( InputIterator first, InputIterator last);
	creates a Point_set_2<Traits> T of the points in the range [$$first,$$last).

Operations

void	T.init ( std::list<Point> L)
		makes T a Point_set_2<Traits> for the points in $$L.
template<class InputIterator>
void	T.init ( InputIterator first, InputIterator last)
		makes T a Point_set_2<Traits> for the points in the range [$$first,$$last).
template<class OutputIterator>
OutputIterator	T.points ( OutputIterator out)
		places all points of Tas a sequence of objects of type $$Point in a container of value type of $$out, which points to the first object in the sequence. The function returns an output iterator pointing to the position beyond the end of the sequence.
template<class OutputIterator>
OutputIterator	T.segments ( OutputIterator out)
		places all segments of T as a sequence of objects of type $$Segment in a container of value type of $$out, which points to the first object in the sequence. The function returns an output iterator pointing to the position beyond the end of the sequence.
template<class OutputIterator>
OutputIterator	T.vertices ( OutputIterator out)
		places all vertices of T as a sequence of objects of type $$Vertex in a container of value type of $$out, which points to the first object in the sequence. The function returns an output iterator pointing to the position beyond the end of the sequence.
template<class OutputIterator>
OutputIterator	T.edges ( OutputIterator out)
		places all points of T as a sequence of objects of type $$Edge in a container of value type of $$out, which points to the first object in the sequence. The function returns an output iterator pointing to the position beyond the end of the sequence.
Edge	T.d_face_cycle_succ ( Edge e)
		returns the face cycle successor of $$e in the Delaunay diagram of T. Precondition: $$e belongs to the Delaunay diagram.
Edge	T.d_face_cycle_pred ( Edge e)
		returns the face cycle predecessor of $$e in the Delaunay diagram of T. Precondition: $$e belongs to the Delaunay diagram.
bool	T.is_empty ()	decides whether T is empty.
void	T.clear ()	makes T empty.
Edge	T.locate ( Point p)
		returns an edge $$e of T that contains $$p or that borders the face that contains $$p. In the former case, a hull edge is returned if $$p lies on the boundary of the convex hull. In the latter case we have $$T.orientation(e,p) > 0 except if all points of $$T are collinear and $$p lies on the induced line. In this case $$target(e) is visible from $$p. The function returns $$NULL if $$T has no edge.
Vertex	T.lookup ( Point p)
		if T contains a Vertex $$v with $$|pos(v)| = p the result is $$v otherwise the result is $$NULL.
Vertex	T.insert ( Point p)
		inserts point $$p into T and returns the corresponding vertex. More precisely, if there is already a vertex $$v in T positioned at $$p then $$pos(v) is made identical to $$p and if there is no such node then a new node $$v with $$pos(v) = p is added to $$T. In either case, $$v is returned.
void	T.del ( Vertex v)	removes the vertex $$v from T. Precondition: v is a vertex in T.
void	T.del ( Point p)	removes the vertex $$v with position $$p from T. If there is no such vertex in T, the function returns without changing T.
Vertex	T.nearest_neighbor ( Point p)
		computes a vertex $$v of T that is closest to $$p. If T is empty, $$NULL is returned. This is a non-const operation.
Vertex	T.nearest_neighbor ( Vertex v)
		computes a vertex $$w of T that is closest to $$v. If $$v is the only vertex in T , $$NULL is returned. Precondition: $$v is a vertex in T.
template<class OutputIterator>
OutputIterator	T.nearest_neighbors ( Point p, int k, OutputIterator res)
		computes the $$k nearest neighbors of $$p, and places them as a sequence of objects of type $$Vertex in a container of value type of $$res which points to the first object in the sequence. The function returns an output iterator pointing to the position beyond the end of the sequence.
template<class OutputIterator>
OutputIterator	T.nearest_neighbors ( Vertex v, int k, OutputIterator res)
		computes the $$k nearest neighbors of $$v, and places them as a sequence of objects of type $$Vertex in a container of value type of $$res which points to the first object in the sequence. The function returns an output iterator pointing to the position beyond the end of the sequence.
template<class OutputIterator>
OutputIterator	T.range_search ( Circle C, OutputIterator res)
		computes all vertices contained in the closure of disk $$C. Precondition: $$C must be a proper circle (not a straight line). The computed vertices will be placed as a sequence of objects in a container of value type of $$res which points to the first object in the sequence. The function returns an output iterator pointing to the position beyond the end of the sequence. This is a non-const operation.
template<class OutputIterator>
OutputIterator	T.range_search ( Point a, Point b, Point c, OutputIterator res)
		computes all vertices contained in the closure of the triangle $$(a,b,c). Precondition: $$a, $$b, and $$c must not be collinear. The computed vertices will be placed as a sequence of objects in a container of value type of $$res which points to the first object in the sequence. The function returns an output iterator pointing to the position beyond the end of the sequence. This is a non-const operation.
template<class OutputIterator>
OutputIterator	T.range_search ( Point a1, Point b1, Point c1, Point d1, OutputIterator res)
		computes all vertices contained in the closure of the iso-rectangle $$(a1,b1,c1,d1). Precondition: $$a1 is the lower left point, $$b1 the lower right, $$c1 the upper right and $$d1 the upper left point of the iso rectangle. The computed vertices will be placed as a sequence of objects in a container of value type of $$res which points to the first object in the sequence. The function returns an output iterator pointing to the position beyond the end of the sequence. This is a non-const operation.
template<class OutputIterator>
OutputIterator	T.minimum_spanning_tree ( OutputIterator result)
		places all edges of the minimum spanning tree of T as a sequence of objects of type $$Edge in a container of type corresponding to the type of $$out which points to the first object in the sequence. The function returns an output iterator pointing to the position beyond the end of the sequence.
bool	T.is_non_diagram_edge ( Edge e)
		checks whether $$e is a non-diagram edge.
Point	T.pos ( Vertex v)	returns the position of $$v in T.
Vertex	T.source ( Edge e)	returns the source vertex of $$e.
Vertex	T.target ( Edge e)	returns the target vertex of $$e.
Point	T.pos_source ( Edge e)
		returns the position of the source of $$e in T.
Point	T.pos_target ( Edge e)
		returns the position of the target of $$e in T.
Segment	T.seg ( Edge e)	returns the line segment corresponding to edge $$e starting at $$pos_source(e).
Line	T.supporting_line ( Edge e)
		returns the supporting line of edge $$e.
int	T.orientation ( Edge e, Point p)
		returns $$orientation(T.pos_source(e),T.pos_target(e),p).
Edge	T.get_hull_edge ()	returns an edge of the outer face of T (i.e., an edge of the convex hull).
bool	T.is_diagram_edge ( Edge e)
		returns true if $$e is an edge of the Delaunay diagram, i.e., either an edge on the convex hull or an edge where the incident triangles have distinct circumcircles.
bool	T.is_hull_edge ( Edge e)
		returns true if $$e is an edge of the convex hull of T, i.e., an edge on the face cycle of the outer face.
int	T.dim ()	returns $$-1 if T is empty, returns $$0 if Tconsists of only one point, returns $$1 if T consists of at least two points and all points in T are collinear, and returns $$2 otherwise.