\( \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.5 - 2D and Surface Function Interpolation
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
Functions
3D Surface Neighbor Coordinates Functions
Surface Neighbor and Surface Neighbor Coordinate Computation

The functions surface_neighbor_coordinates_3() compute natural neighbor coordinates for surface points associated to a finite set of sample points issued from the surface.

The coordinates are computed from the intersection of the Voronoi cell of the query point p with the tangent plane to the surface at p. If the sampling is sufficiently dense, the coordinate system meets the properties described in the manual pages and in [2],[5]. The query point p needs to lie inside the convex hull of the projection of the sample points onto the tangent plane at p.

The functions surface_neighbor_coordinates_certified_3() return, in addition, a second Boolean value (the fourth value of the quadruple) 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 check whether the neighborhood which has been considered is large enough.

Requirements

  1. Dt is equivalent to the class Delaunay_triangulation_3.
  2. The value type of OutputIterator is equivalent to std::pair<Dt::Point_3, Dt::Geom_traits::FT>, i.e. a pair associating a point and its natural neighbor coordinate.
  3. ITraits is equivalent to the class Voronoi_intersection_2_traits_3<K>.
See Also
CGAL::linear_interpolation()
CGAL::sibson_c1_interpolation()
CGAL::farin_c1_interpolation()
CGAL::Voronoi_intersection_2_traits_3<K>
3D Surface Neighbors Functions

Implementation

This functions construct the regular triangulation of the input points instantiated with Voronoi_intersection_2_traits_3<Kernel> or ITraits if provided. They return the result of the function call PkgInterpolationRegularNeighborCoordinates2 with the regular triangulation and p as arguments.

Functions

template<class OutputIterator , class InputIterator , class Kernel >
CGAL::Triple< OutputIterator,
typename Kernel::FT, bool > 		CGAL::surface_neighbor_coordinates_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 >
CGAL::Triple< OutputIterator,
typename ITraits::FT, bool > 		CGAL::surface_neighbor_coordinates_3 (InputIterator first, InputIterator beyond, const typename ITraits::Point_2 &p, OutputIterator out, const ITraits &traits)
 the same as above only that the traits class must be instantiated by the user. More...
 
template<class OutputIterator , class InputIterator , class Kernel >
CGAL::Quadruple
< OutputIterator, typename
Kernel::FT, bool, bool > 		CGAL::surface_neighbor_coordinates_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 >
CGAL::Quadruple
< OutputIterator, typename
Kernel::FT, bool, bool > 		CGAL::surface_neighbor_coordinates_certified_3 (InputIterator first, InputIterator beyond, const typename Kernel::Point_3 &p, const typename Kernel::FT &max_distance, OutputIterator out, const Kernel &kernel)
 The 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 >
CGAL::Quadruple
< OutputIterator, typename
ITraits::FT, bool, bool > 		CGAL::surface_neighbor_coordinates_certified_3 (InputIterator first, InputIterator beyond, const typename ITraits::Point_2 &p, OutputIterator out, const ITraits &traits)
 The same as above only that the traits class must be instantiated by the user and without the parameter max_distance. More...
 
template<class OutputIterator , class InputIterator , class ITraits >
CGAL::Quadruple
< OutputIterator, typename
ITraits::FT, bool, bool > 		CGAL::surface_neighbor_coordinates_certified_3 (InputIterator first, InputIterator beyond, const typename ITraits::Point_2 &p, const typename ITraits::FT &max_distance, OutputIterator out, const ITraits &traits)
 The same as above with the parameter max_distance.
 
template<class Dt , class OutputIterator >
CGAL::Triple< OutputIterator,
typename Dt::Geom_traits::FT,
bool > 		CGAL::surface_neighbor_coordinates_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 >
CGAL::Triple< OutputIterator,
typenameDt::Geom_traits::FT,
bool > 		CGAL::surface_neighbor_coordinates_3 (const Dt &dt, const typename Dt::Geom_traits::Point_3 &p, OutputIterator out, const ITraits &traits, typename Dt::Cell_handle start=typename Dt::Cell_handle())
 The same as above only that the parameter traits instantiates the geometric traits class. More...
 

Function Documentation

template<class OutputIterator , class InputIterator , class Kernel >
CGAL::Triple< OutputIterator, typename Kernel::FT, bool > CGAL::surface_neighbor_coordinates_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)`.

The value type of InputIterator 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 natural neighbor coordinates for p are computed in the power diagram that results from the intersection of the 3D Voronoi diagram of \( \mathcal{P}\) with the tangent plane. 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 projection of the points \( \mathcal{P}\) onto the tangent plane.

#include <CGAL/surface_neighbor_coordinates_3.h>

Examples:
Interpolation/surface_neighbor_coordinates_3.cpp.
template<class OutputIterator , class InputIterator , class ITraits >
CGAL::Triple< OutputIterator, typename ITraits::FT, bool > CGAL::surface_neighbor_coordinates_3 ( InputIterator  first,
InputIterator  beyond,
const typename ITraits::Point_2 &  p,
OutputIterator  out,
const ITraits &  traits 
)

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

#include <CGAL/surface_neighbor_coordinates_3.h>

template<class Dt , class OutputIterator >
CGAL::Triple< OutputIterator, typename Dt::Geom_traits::FT, bool > CGAL::surface_neighbor_coordinates_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.

The type Dt must be equivalent to Delaunay_triangulation_3<Gt, Tds>. The optional parameter start is 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\}\).

#include <CGAL/surface_neighbor_coordinates_3.h>

template<class Dt , class OutputIterator , class ITraits >
CGAL::Triple< OutputIterator, typenameDt::Geom_traits::FT, bool > CGAL::surface_neighbor_coordinates_3 ( const Dt &  dt,
const typename Dt::Geom_traits::Point_3 &  p,
OutputIterator  out,
const ITraits &  traits,
typename Dt::Cell_handle  start = typename Dt::Cell_handle() 
)

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

#include <CGAL/surface_neighbor_coordinates_3.h>

template<class OutputIterator , class InputIterator , class Kernel >
CGAL::Quadruple< OutputIterator, typename Kernel::FT, bool,bool > CGAL::surface_neighbor_coordinates_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.

The additional fourth 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 by (p,normal). It is false otherwise.

#include <CGAL/surface_neighbor_coordinates_3.h>

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

The same as above only that the traits class must be instantiated by the user and without the parameter max_distance.

ITraits must be equivalent to Voronoi_intersection_2_traits_3<K>.

#include <CGAL/surface_neighbor_coordinates_3.h>