#include <CGAL/Point_set_2.h>

Inherits from

CGAL::Delaunay_triangulation_2< Gt, Tds >.

Definition

template<typename Gt, typename Tds = Triangulation_data_structure_2< Triangulation_vertex_base_2<Gt> >>
class CGAL::Point_set_2< Gt, Tds >

An instance PS of the data type Point_set_2 is a Delaunay Triangulation of its vertex set.

The class Point_set_2 is inherited from the CGAL Delaunay triangulation, and provides additional nearest neighbor query operations and range searching operations.

The Point_set_2 class of CGAL depends on template parameters standing for the geometric traits classes used by the point set and by the Delaunay triangulation (Gt) and for the triangulation data structure (Tds).

Examples:: Point_set_2/nearest_neighbor.cpp, and Point_set_2/range_search.cpp.

Types
typedef Gt::Point_2	Point
	the point type

typedef Gt::Segment_2	Segment
	the segment type

typedef Gt::Circle_2	Circle
	the circle type

typedef Gt::FT	Numb_type
	the representation field number type.

typedef unspecified_type	Triangulation
	the underlying triangulation type.

typedef Triangulation::size_type	size_type
	the size type of the underlying triangulation.

typedef Triangulation::Vertex	Vertex
	the vertex type of the underlying triangulation.

typedef Triangulation::Edge	Edge
	the edge type of the underlying triangulation.

typedef Triangulation::Vertex_handle	Vertex_handle
	handles to vertices.

Creation
	Point_set_2 ()
	creates an empty `Point_set_2`.

template<class InputIterator >
	Point_set_2 (InputIterator first, InputIterator last)
	creates a `Point_set_2` `PS` of the points in the range [`first`,`last`).

Operations
Vertex _handle	lookup (Point p)
	if `PS` contains a vertex `v` with `v.point() == p` the result is a handle to `v` otherwise the result is `NULL`.

Vertex _handle	nearest_neighbor (Point p)
	computes a handle to a vertex `v` of `PS` that is closest to `p`. More...

Vertex _handle	nearest_neighbor (Vertex_handle v)
	computes a handle to a vertex `w` of `PS` that is closest to `v`. More...

template<class OutputIterator >
OutputIterator	nearest_neighbors (Point p, size_type k, OutputIterator res)
	computes the `k` nearest neighbors of `p` in `PS`, and places the handles to the corresponding vertices as a sequence of objects of type Vertex_handle in a container of value type of `res` which points to the first object in the sequence. More...

template<class OutputIterator >
OutputIterator	nearest_neighbors (Vertex_handle v, size_type k, OutputIterator res)
	computes the `k` nearest neighbors of `v`, and places them as a sequence of objects of type Vertex_handle in a container of value type of `res` which points to the first object in the sequence. More...

template<class OutputIterator >
OutputIterator	range_search (const Circle &C, OutputIterator res)
	computes handles to all vertices contained in the closure of disk `C`. More...

template<class OutputIterator >
OutputIterator	range_search (const Point &a, const Point &b, const Point &c, OutputIterator res)
	computes handles to all vertices contained in the closure of the triangle `(a,b,c)`. More...

template<class OutputIterator >
OutputIterator	range_search (const Point &a1, const Point &b1, const Point &c1, const Point &d1, OutputIterator res)
	computes handles to all vertices contained in the closure of the iso-rectangle `(a1,b1,c1,d1)`. More...

Additional Inherited Members
Public Types inherited from CGAL::Triangulation_2< class, class >
enum	Locate_type

typedef Traits	Geom_traits

typedef Tds	Triangulation_data_structure

typedef Traits::Point_2	Point

typedef Traits::Segment_2	Segment

typedef Traits::Triangle_2	Triangle

typedef Tds::Vertex	Vertex

typedef Tds::Face	Face

typedef Tds::Edge	Edge

typedef Tds::size_type	size_type

typedef Tds::difference_type	difference_type

typedef Tds::Vertex_handle	Vertex_handle

typedef Tds::Face_handle	Face_handle

typedef Tds::Face_iterator	All_faces_iterator

typedef Tds::Edge_iterator	All_edges_iterator

typedef Tds::Vertex_iterator	All_vertices_iterator

typedef unspecified_type	Finite_faces_iterator

typedef unspecified_type	Finite_edges_iterator

typedef unspecified_type	Finite_vertices_iterator

typedef unspecified_type	Point_iterator

typedef Iterator_range< unspecified_type >	All_face_handles

typedef Iterator_range< All_edges_iterator >	All_edges

typedef Iterator_range< unspecified_type >	All_vertex_handles

typedef Iterator_range< unspecified_type >	Finite_face_handles

typedef Iterator_range< Finite_edges_iterator >	Finite_edges

typedef Iterator_range< unspecified_type >	Finite_vertex_handles

typedef Iterator_range< Point_iterator >	Points

typedef unspecified_type	Line_face_circulator

typedef unspecified_type	Face_circulator

typedef unspecified_type	Edge_circulator

typedef unspecified_type	Vertex_circulator

Public Member Functions inherited from CGAL::Delaunay_triangulation_2< Gt, Tds >
	Delaunay_triangulation_2 (const Traits &gt=Traits())

	Delaunay_triangulation_2 (const Delaunay_triangulation_2< Traits, Tds > &tr)

	Delaunay_triangulation_2 (InputIterator first, InputIterator last, Traits gt=Traits())

Vertex_handle	insert (const Point &p, Face_handle f=Face_handle())

Vertex_handle	insert (const Point &p, Locate_type &lt, Face_handle loc, int li)

std::ptrdiff_t	insert (PointInputIterator first, PointInputIterator last)

std::ptrdiff_t	insert (PointWithInfoInputIterator first, PointWithInfoInputIterator last)

Vertex_handle	push_back (const Point &p)

void	remove (Vertex_handle v)

Vertex_handle	move_if_no_collision (Vertex_handle v, const Point &p)

Vertex_handle	move (Vertex_handle v, const Point &p)

Vertex_handle	nearest_vertex (const Point &p, Face_handle f=Face_handle()) const

std::pair< OutputItFaces, OutputItBoundaryEdges >	get_conflicts_and_boundary (const Point &p, OutputItFaces fit, OutputItBoundaryEdges eit, Face_handle start) const

OutputItFaces	get_conflicts (const Point &p, OutputItFaces fit, Face_handle start) const

OutputItBoundaryEdges	get_boundary_of_conflicts (const Point &p, OutputItBoundaryEdges eit, Face_handle start) const

Point	dual (const Face_handle &f) const

Object	dual (const Edge &e) const

Object	dual (const Edge_circulator &ec) const

Object	dual (const Edge_iterator &ei) const

Stream &	draw_dual (Stream &ps)

Oriented_side	side_of_oriented_circle (Face_handle f, const Point &p) const

bool	is_valid (bool verbose=false, int level=0) const

Public Member Functions inherited from CGAL::Triangulation_2< class, class >
ostream &	operator<< (ostream &os, const Triangulation_2< Traits, Tds > &T)

istream &	operator>> (istream &is, const Triangulation_2< Traits, Tds > &T)

	Triangulation_2 (const Traits &gt=Traits())

	Triangulation_2 (const Triangulation_2 &tr)

	Triangulation_2 (InputIterator first, InputIterator last, const Traits &gt=Traits())

Triangulation_2	operator= (const Triangulation_2< Traits, Tds > &tr)

void	swap (Triangulation_2 &tr)

void	clear ()

int	dimension () const

size_type	number_of_vertices () const

size_type	number_of_faces () const

Face_handle	infinite_face () const

Vertex_handle	infinite_vertex () const

Vertex_handle	finite_vertex () const

const Geom_traits &	geom_traits () const

const TriangulationDataStructure_2 &	tds () const

TriangulationDataStructure_2 &	tds ()

bool	is_infinite (Vertex_handle v) const

bool	is_infinite (Face_handle f) const

bool	is_infinite (Face_handle f, int i) const

bool	is_infinite (Edge e) const

bool	is_infinite (Edge_circulator ec) const

bool	is_infinite (All_edges_iterator ei) const

bool	is_edge (Vertex_handle va, Vertex_handle vb)

bool	is_edge (Vertex_handle va, Vertex_handle vb, Face_handle &fr, int &i)

bool	includes_edge (Vertex_handle va, Vertex_handle vb, Vertex_handle &vbr, Face_handle &fr, int &i)

bool	is_face (Vertex_handle v1, Vertex_handle v2, Vertex_handle v3)

bool	is_face (Vertex_handle v1, Vertex_handle v2, Vertex_handle v3, Face_handle &fr)

Face_handle	locate (const Point &query, Face_handle f=Face_handle()) const

Face_handle	inexact_locate (const Point &query, Face_handle start=Face_handle()) const

Face_handle	locate (const Point &query, Locate_type &lt, int &li, Face_handle h=Face_handle()) const

Oriented_side	oriented_side (Face_handle f, const Point &p) const

Oriented_side	side_of_oriented_circle (Face_handle f, const Point &p)

void	flip (Face_handle f, int i)

Vertex_handle	insert (const Point &p, Face_handle f=Face_handle())

Vertex_handle	insert (const Point &p, Locate_type lt, Face_handle loc, int li)

Vertex_handle	push_back (const Point &p)

std::ptrdiff_t	insert (PointInputIterator first, PointInputIterator last)

std::ptrdiff_t	insert (PointWithInfoInputIterator first, PointWithInfoInputIterator last)

void	remove (Vertex_handle v)

Vertex_handle	move_if_no_collision (Vertex_handle v, const Point &p)

Vertex_handle	move (Vertex_handle v, const Point &p)

Vertex_handle	insert_first (const Point &p)

Vertex_handle	insert_second (const Point &p)

Vertex_handle	insert_in_face (const Point &p, Face_handle f)

Vertex_handle	insert_in_edge (const Point &p, Face_handle f, int i)

Vertex_handle	insert_outside_convex_hull (const Point &p, Face_handle f)

Vertex_handle	insert_outside_affine_hull (const Point &p)

void	remove_degree_3 (Vertex_handle v)

void	remove_second (Vertex_handle v)

void	remove_first (Vertex_handle v)

Vertex_handle	star_hole (Point p, EdgeIt edge_begin, EdgeIt edge_end)

Vertex_handle	star_hole (Point p, EdgeIt edge_begin, EdgeIt edge_end, FaceIt face_begin, FaceIt face_end)

Finite_vertices_iterator	finite_vertices_begin () const

Finite_vertices_iterator	finite_vertices_end () const

Finite_edges_iterator	finite_edges_begin () const

Finite_edges_iterator	finite_edges_end () const

Finite_faces_iterator	finite_faces_begin () const

Finite_faces_iterator	finite_faces_end () const

Point_iterator	points_begin () const

Point_iterator	points_end () const

Finite_vertex_handles	finite_vertex_handles () const

Finite_edges	finite_edges () const

Finite_face_handles	finite_face_handles () const

Points	points () const

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

All_vertex_handles	all_vertex_handles () const

All_edges	all_edges () const

All_face_handles	all_face_handles () const

Line_face_circulator	line_walk (const Point &p, const Point &q, Face_handle f=Face_handle()) const

Face_circulator	incident_faces (Vertex_handle v) const

Face_circulator	incident_faces (Vertex_handle v, Face_handle f) const

Edge_circulator	incident_edges (Vertex_handle v) const

Edge_circulator	incident_edges (Vertex_handle v, Face_handle f) const

Vertex_circulator	incident_vertices (Vertex_handle v) const

Vertex_circulator	incident_vertices (Vertex_handle v, Face_handle f)

Vertex_handle	mirror_vertex (Face_handle f, int i) const

int	mirror_index (Face_handle f, int i) const

Edge	mirror_edge (Edge e) const

int	ccw (int i) const

int	cw (int i) const

Triangle	triangle (Face_handle f) const

Segment	segment (Face_handle f, int i) const

Segment	segment (const Edge &e) const

Segment	segment (const Edge_circulator &ec) const

Segment	segment (const Edge_iterator &ei) const

Point	circumcenter (Face_handle f) const

void	set_infinite_vertex (const Vertex_handle &v)

bool	is_valid (bool verbose=false, int level=0) const

Public Member Functions inherited from CGAL::Triangulation_cw_ccw_2
	Triangulation_cw_ccw_2 ()

int	ccw (const int i) const

int	cw (const int i) const

Public Attributes inherited from CGAL::Triangulation_2< class, class >
	VERTEX

	EDGE

	FACE

	OUTSIDE_CONVEX_HULL

	OUTSIDE_AFFINE_HULL