\( \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.13.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.

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, as second value of a triple.

Attention
If p lies outside the convex hull, the coordinate values cannot be computed, and the third value of the resulting triple is set to false (the other values of the triple are then meaningless).

Output Format

The return type is identical for all overloads of CGAL::natural_neighbor_coordinates_2(): it is CGAL::Triple<CoordinateOutputIterator, Dt::Geom_traits::FT, bool >

Natural neighbor coordinates are output in the first value of the triple, using an output iterator (see the concept OutputIterator). Internally, these coordinates are associated to some of the vertices of the triangulation, and a natural value type for the output iterator would thus be std::pair<Dt::Vertex_handle, Dt::Geom_traits::FT>. However, to allow flexibility in the format of the output, a functor passed as argument can be used to format the output as desired: this functor must have argument type std::pair<Dt::Vertex_handle, Dt::Geom_traits::FT> and its result type and the value type of the output iterator must be identical.

For example, we can use a functor of type CGAL::Identity<std::pair<Dt::Vertex_handle, Dt::Geom_traits::FT> > and an output iterator with value type std::pair<Dt::Vertex_handle, Dt::Geom_traits::FT> or we could extract the bare point and use a value type: std::pair<Dt::Point, Dt::Geom_traits::FT>, or simply the coordinates, etc.

This functor can be omitted and will default, for backward compatibility reasons, to a functor that extracts the point from the vertex, and the output iterator must then have value type std::pair<Dt::Point, Dt::Geom_traits::FT>.

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

Functions

template<class Dt , class CoordinateOutputIterator , class OutputFunctor >
CGAL::Triple< CoordinateOutputIterator, typename Dt::Geom_traits::FT, bool > CGAL::natural_neighbor_coordinates_2 (const Dt &dt, const typename Dt::Geom_traits::Point_2 &p, CoordinateOutputIterator out, OutputFunctor fct, 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 CoordinateOutputIterator , class OutputFunctor , class EdgeIterator >
CGAL::Triple< CoordinateOutputIterator, typename Dt::Geom_traits::FT, bool > CGAL::natural_neighbor_coordinates_2 (const Dt &dt, const typename Dt::Geom_traits::Point_2 &p, CoordinateOutputIterator out, OutputFunctor fct, EdgeIterator hole_begin, EdgeIterator hole_end)
 Computes the natural neighbor coordinates for p with respect to the points in the two-dimensional Delaunay triangulation dt. More...
 
template<class Dt , class CoordinateOutputIterator , class OutputFunctor >
CGAL::Triple< CoordinateOutputIterator, typename Dt::Geom_traits::FT, bool > CGAL::natural_neighbor_coordinates_2 (const Dt &dt, typename Dt::Vertex_handle vh, CoordinateOutputIterator out, OutputFunctor fct)
 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 CoordinateOutputIterator , class OutputFunctor >
CGAL::Triple<CoordinateOutputIterator, typename Dt::Geom_traits::FT, bool > CGAL::natural_neighbor_coordinates_2 ( const Dt &  dt,
const typename Dt::Geom_traits::Point_2 &  p,
CoordinateOutputIterator  out,
OutputFunctor  fct,
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>. Traits must be a model of the concepts DelaunayTriangulationTraits_2 and PolygonTraits_2.
CoordinateOutputIteratormust be a model of OutputIterator and have the value type OutputFunctor::result_type. The output computed by the function is placed starting at out.
OutputFunctormust be a functor with argument type std::pair<Dt::Vertex_handle, Dt::Geom_traits::FT>. See above for a detailed explanation on the usage of OutputFunctor.
Parameters
dtis the Delaunay triangulation.
pis the query point.
outis an object of type CoordinateOutputIterator.
fctis an object of type OutputFunctor.
startis an optional argument that is used as a hint of where the locate process has to start its search.
Returns
A triple consisting of:
  • a sequence of objects of types OutputFunctor::result_type, starting at out.
  • the normalization factor of the coordinates.
  • a Boolean value which is set to true if the coordinate computation was successful, and false otherwise.
Examples:
Interpolation/interpolation_2.cpp, Interpolation/linear_interpolation_2.cpp, Interpolation/nn_coordinates_2.cpp, Interpolation/nn_coordinates_with_info_2.cpp, Interpolation/sibson_interpolation_2.cpp, and Interpolation/sibson_interpolation_vertex_with_info_2.cpp.

◆ natural_neighbor_coordinates_2() [2/3]

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

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

The iterator range [hole_begin, hole_end) determines the boundary edges of the conflict zone of p in the triangulation. It can, for example, be computed using the function: dt.get_boundary_of_conflicts(p, std::back_inserter(hole), start).

Requirements
Same as above.

◆ natural_neighbor_coordinates_2() [3/3]

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

#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().

Requirements
Same as above.