CGAL 6.2 - 2D Range and Neighbor Search

Loading...
Searching...
No Matches
List of all members
CGAL::Point_set_2< Gt, Tds > Class Template Reference
Reference Manual

`#include <CGAL/Point_set_2.h>`

## Inherits from

CGAL::Delaunay_triangulation_2< typename Traits, typename 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`.
Vertex _handle | nearest_neighbor (Vertex_handle v)
| computes a handle to a vertex `w` of `PS` that is closest to `v`.
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.
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.
template<class OutputIterator >
OutputIterator | range_search (const Circle &C, OutputIterator res)
| computes handles to all vertices contained in the closure of disk `C`.
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)`.
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)`.

## Additional Inherited Members
Public Types inherited from CGAL::Triangulation_2< typename Traits, typename Tds >
enum | Locate_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
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
Public Member Functions inherited from CGAL::Delaunay_triangulation_2< typename Traits, typename 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)
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 | 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=Face_handle()) const
OutputItFaces | get_conflicts (const Point &p, OutputItFaces fit, Face_handle start=Face_handle()) const
OutputItBoundaryEdges | get_boundary_of_conflicts (const Point &p, OutputItBoundaryEdges eit, Face_handle start=Face_handle()) 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< typename Traits, typename Tds >
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_vertex (Vertex_handle v) 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 &vbb, 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)
size_type | degree (Vertex_handle v) const
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
const Point & | point (Face_handle f, int i) const
const Point & | point (Vertex_handle v) 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< typename Traits, typename Tds >
| 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.

Examples
  Point_set_2/nearest_neighbor.cpp.

## ◆ 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.

Examples
  Point_set_2/nearest_neighbor.cpp.

## ◆ 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.

Examples
  Point_set_2/range_search.cpp.

## ◆ 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.