CGAL 5.3 - 2D and Surface Function Interpolation
3D Surface Neighbors Functions

Given a set of sample points issued from a surface and a query point p, the functions surface_neighbors_3() compute the neighbors of p on the surface within the sample points.

If the sampling is sufficiently dense, the neighbors are provably close to the point p on the surface (cf. the manual pages and [2],[5]). They are defined to be the neighbors of p in the regular triangulation dual to the power diagram which is equivalent to the intersection of the Voronoi cell of the query point p with the tangent plane to the surface at p.

The functions surface_neighbors_certified_3() also return, in addition, a Boolean value that certifies whether or not, the Voronoi cell of p can be affected by points that lie outside the input range, i.e. outside the ball centered on p passing through the furthest sample point from p in the range [first, beyond). If the sample points are collected by a k-nearest neighbor or a range search query, this permits to verify that a large enough neighborhood has been considered.

Requirements

1. Dt is equivalent to the class Delaunay_triangulation_3.
2. OutputIterator::value_type is equivalent to Dt::Point_3, i.e. a point type.
3. ITraits is equivalent to the class Voronoi_intersection_2_traits_3<K>.
CGAL::Voronoi_intersection_2_traits_3<K>
3D Surface Neighbor Coordinates Functions

Implementation

These functions compute the regular triangulation of the sample points and the point p using a traits class equivalent to Voronoi_intersection_2_traits_3<K>. They determine the neighbors of p in this triangulation. The functions which certify the result need to compute, in addition, the Voronoi vertices of the cell of p in this diagram.

## Functions

template<class OutputIterator , class InputIterator , class Kernel >
OutputIterator CGAL::surface_neighbors_3 (InputIterator first, InputIterator beyond, const typename Kernel::Point_3 &p, const typename Kernel::Vector_3 &normal, OutputIterator out, const Kernel &K)
The sample points $$\mathcal{P}$$ are provided in the range [first, beyond). More...

template<class OutputIterator , class InputIterator , class ITraits >
OutputIterator CGAL::surface_neighbors_3 (InputIterator first, InputIterator beyond, const typename ITraits::Point_2 &p, OutputIterator out, const ITraits &traits)
Same as above only that the traits class must be instantiated by the user. More...

template<class OutputIterator , class InputIterator , class Kernel >
std::pair< OutputIterator, bool > CGAL::surface_neighbors_certified_3 (InputIterator first, InputIterator beyond, const typename Kernel::Point_3 &p, const typename Kernel::Vector_3 &normal, OutputIterator out, const Kernel &K)
Similar to the first function. More...

template<class OutputIterator , class InputIterator , class Kernel >
std::pair< OutputIterator, bool > CGAL::surface_neighbors_certified_3 (InputIterator first, InputIterator beyond, const typename Kernel::Point_3 &p, const typename Kernel::Vector_3 &normal, const typename Kernel::FT &max_distance, OutputIterator out, const Kernel &kernel)
Same as above except that this function takes the maximal distance from p to the points in the range [first, beyond) as additional parameter.

template<class OutputIterator , class InputIterator , class ITraits >
std::pair< OutputIterator, bool > CGAL::surface_neighbors_certified_3 (InputIterator first, InputIterator beyond, const typename ITraits::Point_2 &p, OutputIterator out, const ITraits &traits)
Same as above only that the traits class must be instantiated by the user. More...

template<class OutputIterator , class InputIterator , class ITraits >
std::pair< OutputIterator, bool > CGAL::surface_neighbors_certified_3 (InputIterator first, InputIterator beyond, const typename ITraits::Point_2 &p, const typename ITraits::FT &max_distance, OutputIterator out, const ITraits &traits)
Same as above with the parameter max_distance.

template<class Dt , class OutputIterator >
OutputIterator CGAL::surface_neighbors_3 (const Dt &dt, const typename Dt::Geom_traits::Point_3 &p, const typename Dt::Geom_traits::Vector_3 &normal, OutputIterator out, typename Dt::Cell_handle start=typename Dt::Cell_handle())
Computes the surface neighbor coordinates with respect to the points that are vertices of the Delaunay triangulation dt. More...

template<class Dt , class OutputIterator , class ITraits >
OutputIterator CGAL::surface_neighbors_3 (const Dt &dt, const typename ITraits::Point_2 &p, OutputIterator out, const ITraits &traits, typename Dt::Cell_handle start=typename Dt::Cell_handle())
Same as above only that the parameter traits instantiates the geometric traits class. More...

## ◆ surface_neighbors_3() [1/4]

template<class OutputIterator , class InputIterator , class Kernel >
 OutputIterator CGAL::surface_neighbors_3 ( InputIterator first, InputIterator beyond, const typename Kernel::Point_3 & p, const typename Kernel::Vector_3 & normal, OutputIterator out, const Kernel & K )

#include <CGAL/surface_neighbors_3.h>

The sample points $$\mathcal{P}$$ are provided in the range [first, beyond).

InputIterator::value_type is the point type Kernel::Point_3. The tangent plane is defined by the point p and the vector normal. The parameter K determines the kernel type that will instantiate the template parameter of Voronoi_intersection_2_traits_3<K>.

The surface neighbors of p are computed which are the neighbors of p in the regular triangulation that is dual to the intersection of the 3D Voronoi diagram of $$\mathcal{P}$$ with the tangent plane. The point sequence that is computed by the function is placed starting at out. The function returns an iterator that is placed past-the-end of the resulting point sequence.

## ◆ surface_neighbors_3() [2/4]

template<class OutputIterator , class InputIterator , class ITraits >
 OutputIterator CGAL::surface_neighbors_3 ( InputIterator first, InputIterator beyond, const typename ITraits::Point_2 & p, OutputIterator out, const ITraits & traits )

#include <CGAL/surface_neighbors_3.h>

Same as above only that the traits class must be instantiated by the user.

ITraits must be equivalent to Voronoi_intersection_2_traits_3<K>.

## ◆ surface_neighbors_3() [3/4]

template<class Dt , class OutputIterator >
 OutputIterator CGAL::surface_neighbors_3 ( const Dt & dt, const typename Dt::Geom_traits::Point_3 & p, const typename Dt::Geom_traits::Vector_3 & normal, OutputIterator out, typename Dt::Cell_handle start = typename Dt::Cell_handle() )

#include <CGAL/surface_neighbors_3.h>

Computes the surface neighbor coordinates with respect to the points that are vertices of the Delaunay triangulation dt.

The type Dt must be equivalent to Delaunay_triangulation_3<Gt, Tds>. The optional parameter start is used for the used as a starting place for the search of the conflict zone. It may be the result of the call dt.locate(p). This function instantiates the template parameter ITraits to be Voronoi_intersection_2_traits_3<Dt::Geom_traits>.

This function allows to filter some potential neighbors of the query point p from $$\mathcal{P}$$ via its three-dimensional Delaunay triangulation. All surface neighbors of p are necessarily neighbors in the Delaunay triangulation of $$\mathcal{P} \cup \{p\}$$.

## ◆ surface_neighbors_3() [4/4]

template<class Dt , class OutputIterator , class ITraits >
 OutputIterator CGAL::surface_neighbors_3 ( const Dt & dt, const typename ITraits::Point_2 & p, OutputIterator out, const ITraits & traits, typename Dt::Cell_handle start = typename Dt::Cell_handle() )

#include <CGAL/surface_neighbors_3.h>

Same as above only that the parameter traits instantiates the geometric traits class.

Its type ITraits must be equivalent to Voronoi_intersection_2_traits_3<K>.

## ◆ surface_neighbors_certified_3() [1/2]

template<class OutputIterator , class InputIterator , class Kernel >
 std::pair< OutputIterator, bool > CGAL::surface_neighbors_certified_3 ( InputIterator first, InputIterator beyond, const typename Kernel::Point_3 & p, const typename Kernel::Vector_3 & normal, OutputIterator out, const Kernel & K )

#include <CGAL/surface_neighbors_3.h>

Similar to the first function.

The additional third return value is true if the furthest point in the range [first, beyond) is further away from p than twice the distance from p to the furthest vertex of the intersection of the Voronoi cell of p with the tangent plane defined be (p,normal). It is false otherwise.

## ◆ surface_neighbors_certified_3() [2/2]

template<class OutputIterator , class InputIterator , class ITraits >
 std::pair< OutputIterator, bool > CGAL::surface_neighbors_certified_3 ( InputIterator first, InputIterator beyond, const typename ITraits::Point_2 & p, OutputIterator out, const ITraits & traits )

#include <CGAL/surface_neighbors_3.h>

Same as above only that the traits class must be instantiated by the user.

ITraits must be equivalent to Voronoi_intersection_2_traits_3<K>. There is no parameter max_distance.