\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)
CGAL 4.4 - 2D Range and Neighbor Search
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
List of all members
CGAL::Point_set_2< Gt, Tds > Class Template Reference
2D Range and Neighbor Search Reference

#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 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
< Traits, Tds > 		dt (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
 

Member Function Documentation

template<typename Gt, typename Tds = Triangulation_data_structure_2< Triangulation_vertex_base_2<Gt> >>
Vertex _handle CGAL::Point_set_2< Gt, Tds >::nearest_neighbor ( Point  p)

computes a handle to a vertex v of PS that is closest to p.

If PS is empty, NULL is returned.

template<typename Gt, typename Tds = Triangulation_data_structure_2< Triangulation_vertex_base_2<Gt> >>
Vertex _handle CGAL::Point_set_2< Gt, Tds >::nearest_neighbor ( Vertex_handle  v)

computes a handle to a vertex w of PS that is closest to v.

If v is the only vertex in PS , NULL is returned.

template<typename Gt, typename Tds = Triangulation_data_structure_2< Triangulation_vertex_base_2<Gt> >>
template<class OutputIterator >
OutputIterator CGAL::Point_set_2< Gt, Tds >::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.

The function returns an output iterator pointing to the position beyond the end of the sequence.

template<typename Gt, typename Tds = Triangulation_data_structure_2< Triangulation_vertex_base_2<Gt> >>
template<class OutputIterator >
OutputIterator CGAL::Point_set_2< Gt, Tds >::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.

The function returns an output iterator pointing to the position beyond the end of the sequence.

template<typename Gt, typename Tds = Triangulation_data_structure_2< Triangulation_vertex_base_2<Gt> >>
template<class OutputIterator >
OutputIterator CGAL::Point_set_2< Gt, Tds >::range_search ( const Circle &  C,
OutputIterator  res 
)

computes handles to all vertices contained in the closure of disk C.

The computed vertex handles 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.

template<typename Gt, typename Tds = Triangulation_data_structure_2< Triangulation_vertex_base_2<Gt> >>
template<class OutputIterator >
OutputIterator CGAL::Point_set_2< Gt, Tds >::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).

Precondition
a, b, and c must not be collinear. The computed vertex handles 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.
template<typename Gt, typename Tds = Triangulation_data_structure_2< Triangulation_vertex_base_2<Gt> >>
template<class OutputIterator >
OutputIterator CGAL::Point_set_2< Gt, Tds >::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).

Precondition
a1 is the upper left point, b1 the lower left, c1 the lower right and d1 the upper right point of the iso rectangle. The computed vertex handles 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.