\( \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 5.0.1 - 2D Range and Neighbor Search
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 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
 

Member Function Documentation

◆ nearest_neighbor() [1/2]

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.

◆ nearest_neighbor() [2/2]

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.

◆ nearest_neighbors() [1/2]

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.

◆ nearest_neighbors() [2/2]

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.

◆ range_search() [1/3]

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.

◆ range_search() [2/3]

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.

◆ range_search() [3/3]

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.