\( \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.12.2 - 2D and Surface Function Interpolation

The functions natural_neighbor_coordinates_2() compute natural neighbor coordinates, also called Sibson's coordinates, for 2D points provided a two-dimensional triangulation and a query point in the convex hull of the vertices of the triangulation.

Requirements

  1. Dt are equivalent to the class Delaunay_triangulation_2<Traits, Tds>.
  2. The traits class Traits of Dt is a model of the concept DelaunayTriangulationTraits_2. Only the following members of this traits class are used:
    • Construct_circumcenter_2
    • FT
    • Point_2
    • construct_circumcenter_2_object
    • Additionally, Traits must meet the requirements for the traits class of the polygon_area_2() function.
  3. The value type of OutputIterator is equivalent to std::pair<Dt::Point_2, Dt::Geom_traits::FT>, i.e., a pair associating a point and its natural neighbor coordinate.

Implementation

This function computes the area of the sub-cells stolen from the Voronoi cells of the points in dt when inserting p. The total area of the Voronoi cell of p is also computed and returned by the function. If p lies outside the convex hull, the coordinate values cannot be computed and the third value of the result triple is set to false.

See also
CGAL::linear_interpolation()
CGAL::sibson_c1_interpolation()
3D Surface Neighbor Coordinates Functions
CGAL::regular_neighbor_coordinates_2()

Functions

template<class Dt , class OutputIterator >
CGAL::Triple< OutputIterator, typename Dt::Geom_traits::FT, bool > CGAL::natural_neighbor_coordinates_2 (const Dt &dt, const typename Dt::Geom_traits::Point_2 &p, OutputIterator out, typename Dt::Face_handle start=typename Dt::Face_handle())
 computes the natural neighbor coordinates for p with respect to the points in the two-dimensional Delaunay triangulation dt. More...
 
template<class Dt , class OutputIterator , class EdgeIterator >
CGAL::Triple< OutputIterator, typename Dt::Geom_traits::FT, bool > CGAL::natural_neighbor_coordinates_2 (const Dt &dt, const typename Dt::Geom_traits::Point_2 &p, OutputIterator out, EdgeIterator hole_begin, EdgeIterator hole_end)
 The same as above. More...
 
template<class Dt , class OutputIterator >
CGAL::Triple< OutputIterator, typename Dt::Geom_traits::FT, bool > CGAL::natural_neighbor_coordinates_2 (const Dt &dt, typename Dt::Vertex_handle vh, OutputIterator out)
 computes the natural neighbor coordinates of the point vh->point() with respect to the vertices of dt excluding vh->point(). More...
 

Function Documentation

◆ natural_neighbor_coordinates_2() [1/3]

template<class Dt , class OutputIterator >
CGAL::Triple<OutputIterator, typename Dt::Geom_traits::FT, bool > CGAL::natural_neighbor_coordinates_2 ( const Dt &  dt,
const typename Dt::Geom_traits::Point_2 &  p,
OutputIterator  out,
typename Dt::Face_handle  start = typename Dt::Face_handle() 
)

#include <CGAL/natural_neighbor_coordinates_2.h>

computes the natural neighbor coordinates for p with respect to the points in the two-dimensional Delaunay triangulation dt.

Template Parameters
Dtmust be of type Delaunay_triangulation_2<Traits, Tds>.
OutputIteratormust have the value type std::pair<Dt::Point_2, Dt::Geom_traits::FT>.

The sequence of point/coordinate pairs that is computed by the function is placed starting at out. The function returns a triple with an iterator that is placed past-the-end of the resulting sequence of point/coordinate pairs, the normalization factor of the coordinates and a Boolean value which is set to true iff the coordinate computation was successful.

Examples:
Interpolation/linear_interpolation_2.cpp, Interpolation/nn_coordinates_2.cpp, and Interpolation/sibson_interpolation_2.cpp.

◆ natural_neighbor_coordinates_2() [2/3]

template<class Dt , class OutputIterator , class EdgeIterator >
CGAL::Triple< OutputIterator, typename Dt::Geom_traits::FT, bool > CGAL::natural_neighbor_coordinates_2 ( const Dt &  dt,
const typename Dt::Geom_traits::Point_2 &  p,
OutputIterator  out,
EdgeIterator  hole_begin,
EdgeIterator  hole_end 
)

#include <CGAL/natural_neighbor_coordinates_2.h>

The same as above.

The iterator range [hole_begin, hole_end) determines the boundary edges of the conflict zone of p in the triangulation. It is the result of the function dt.get_boundary_of_conflicts(p,std::back_inserter(hole), start).

◆ natural_neighbor_coordinates_2() [3/3]

template<class Dt , class OutputIterator >
CGAL::Triple< OutputIterator, typename Dt::Geom_traits::FT, bool > CGAL::natural_neighbor_coordinates_2 ( const Dt &  dt,
typename Dt::Vertex_handle  vh,
OutputIterator  out 
)

#include <CGAL/natural_neighbor_coordinates_2.h>

computes the natural neighbor coordinates of the point vh->point() with respect to the vertices of dt excluding vh->point().

The same as above for the remaining parameters.