## CGAL::natural_neighbor_coordinates_2

### Definition

The function natural_neighbor_coordinates_2 computes natural neighbor coordinates, also called Sibson's coordinates, for 2D points provided a two-dimensional triangulation and a query point inside the convex hull of the vertices of the triangulation.

#include <CGAL/natural_neighbor_coordinates_2.h>

template < class Dt, class OutputIterator >
CGAL::Triple< OutputIterator, typename Dt::Geom_traits::FT, bool >

natural_neighbor_coordinates_2 ( | Dt dt, 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. The template class Dt should be of type Delaunay_triangulation_2<Traits, Tds>. The value type of the OutputIterator is a pair of Dt::Point_2 and the coordinate value of type 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, i.e. if p lies inside the convex hull of the points in dt.

template <class Dt, class OutputIterator, class EdgeIterator >
CGAL::Triple< OutputIterator, typename Dt::Geom_traits::FT, bool >

natural_neighbor_coordinates_2 ( | Dt dt, typename Dt::Geom_traits::Point_2 p, OutputIterator out, EdgeIterator hole_begin, EdgeIterator hole_end)

|  | The same as above. hole_begin and hole_end determines the iterator range over the boundary edges of the conflict zone of p in the triangulation. It is the result of the function T.get_boundary_of_conflicts(p,std::back_inserter(hole), start), see Delaunay_triangulation_2<Traits, Tds>.
template <class Dt, class OutputIterator>
CGAL::Triple< OutputIterator, typename Dt::Geom_traits::FT, bool >

natural_neighbor_coordinates_2 ( | Dt dt, typename Dt::Vertex_handle vh, OutputIterator out)

|  | This function 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.

### 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. OutputIterator::value_type is equivalent to std::pair<Dt::Point_2, Dt::Geom_traits::FT>, i.e. a pair associating a point and its natural neighbor coordinate.

### See Also

CGAL::linear_interpolation
CGAL::sibson_c1_interpolation
CGAL::surface_neighbor_coordinates_3
CGAL::regular_neighbor_coordinates_2

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