\( \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.14 - Point Set Processing

Collection of algorithms of point set processing (smoothing, simplification, etc.).

Classes

class  CGAL::Point_set_with_structure< Kernel >
 A 3D point set with structure information based on a set of detected planes. More...
 

Functions

template<typename ConcurrencyTag , typename PointRange , typename NamedParameters >
double CGAL::bilateral_smooth_point_set (PointRange &points, unsigned int k, const NamedParameters &np)
 This function smooths an input point set by iteratively projecting each point onto the implicit surface patch fitted over its k nearest neighbors. More...
 
template<typename ConcurrencyTag , typename PointRange , typename NamedParameters >
FT CGAL::compute_average_spacing (const PointRange &points, unsigned int k, const NamedParameters &np)
 Computes average spacing from k nearest neighbors. More...
 
template<typename ConcurrencyTag , typename PointRange , typename OutputIterator , typename NamedParameters >
OutputIterator CGAL::edge_aware_upsample_point_set (const PointRange &points, OutputIterator output, const NamedParameters &np)
 This method progressively upsamples the point set while approaching the edge singularities (detected by normal variation), which generates a denser point set from an input point set. More...
 
template<typename PointRange , typename QueryPointRange , typename OutputIterator , typename NamedParameters >
OutputIterator CGAL::estimate_local_k_neighbor_scales (const PointRange &points, const QueryPointRange &queries, OutputIterator output, const NamedParameters &np)
 Estimates the local scale in a K nearest neighbors sense on a set of user-defined query points. More...
 
template<typename PointRange , typename NamedParameters >
std::size_t CGAL::estimate_global_k_neighbor_scale (const PointRange &points, const NamedParameters &np)
 Estimates the global scale in a K nearest neighbors sense. More...
 
template<typename PointRange , typename QueryPointRange , typename OutputIterator , typename NamedParameters >
OutputIterator CGAL::estimate_local_range_scales (const PointRange &points, const QueryPointRange &queries, OutputIterator output, const NamedParameters &np)
 Estimates the local scale in a range sense on a set of user-defined query points. More...
 
template<typename PointRange , typename NamedParameters >
FT CGAL::estimate_global_range_scale (const PointRange &points, const NamedParameters &np)
 Estimates the global scale in a range sense. More...
 
template<typename PointRange , typename NamedParameters >
PointRange::iterator CGAL::grid_simplify_point_set (PointRange &points, double epsilon, const NamedParameters &np)
 Merges points which belong to the same cell of a grid of cell size = epsilon. More...
 
template<typename PointRange , typename NamedParameters >
PointRange::iterator CGAL::hierarchy_simplify_point_set (PointRange &points, const NamedParameters &np)
 Recursively split the point set in smaller clusters until the clusters have less than size elements or until their variation factor is below var_max. More...
 
template<typename ConcurrencyTag , typename PointRange , typename NamedParameters >
void CGAL::jet_estimate_normals (PointRange &points, unsigned int k, const NamedParameters &np)
 Estimates normal directions of the range of points using jet fitting on the k nearest neighbors. More...
 
template<typename ConcurrencyTag , typename PointRange , typename NamedParameters >
void CGAL::jet_smooth_point_set (PointRange &points, unsigned int k, const NamedParameters &np)
 Smoothes the range of points using jet fitting on the k nearest neighbors and reprojection onto the jet. More...
 
template<typename PointRange , typename NamedParameters >
PointRange::iterator CGAL::mst_orient_normals (PointRange &points, unsigned int k, const NamedParameters &np)
 Orients the normals of the range of points using the propagation of a seed orientation through a minimum spanning tree of the Riemannian graph. More...
 
template<typename ConcurrencyTag , typename PointRange , typename NamedParameters >
void CGAL::pca_estimate_normals (PointRange &points, unsigned int k, const NamedParameters &np)
 Estimates normal directions of the range of points by linear least squares fitting of a plane over the k nearest neighbors. More...
 
template<typename PointRange >
PointRange::iterator CGAL::random_simplify_point_set (PointRange &points, double removed_percentage)
 Randomly deletes a user-specified fraction of the input points. More...
 
template<typename PointRange , typename NamedParameters >
PointRange::iterator CGAL::remove_outliers (PointRange &points, unsigned int k, const NamedParameters &np)
 Removes outliers: More...
 
template<typename PointRange , typename PlaneRange , typename OutputIterator , typename NamedParameters >
OutputIterator CGAL::structure_point_set (const PointRange &points, const PlaneRange &planes, OutputIterator output, double epsilon, const NamedParameters &np)
 This is an implementation of the Point Set Structuring algorithm. More...
 
template<class FT , class VCMTraits >
bool CGAL::vcm_is_on_feature_edge (cpp11::array< FT, 6 > &cov, double threshold, VCMTraits)
 determines if a point is on a sharp feature edge from a point set for which the Voronoi covariance Measures have been computed. More...
 
template<typename PointRange , typename NamedParameters >
void CGAL::compute_vcm (const PointRange &points, std::vector< cpp11::array< double, 6 > > &ccov, double offset_radius, double convolution_radius, const NamedParameters &np)
 computes the Voronoi Covariance Measure (VCM) of a point cloud, a construction that can be used for normal estimation and sharp feature detection. More...
 
template<typename PointRange , typename NamedParameters >
void CGAL::vcm_estimate_normals (PointRange &points, double offset_radius, double convolution_radius, const NamedParameters &np)
 Estimates normal directions of the range of points using the Voronoi Covariance Measure with a radius for the convolution. More...
 
template<typename PointRange , typename NamedParameters >
void CGAL::vcm_estimate_normals (PointRange &points, double offset_radius, unsigned int k, const NamedParameters &np)
 Estimates normal directions of the range of points using the Voronoi Covariance Measure with a number of neighbors for the convolution. More...
 
template<typename ConcurrencyTag , typename PointRange , typename OutputIterator , typename NamedParameters >
OutputIterator CGAL::wlop_simplify_and_regularize_point_set (PointRange &points, OutputIterator output, const NamedParameters &np)
 This is an implementation of the Weighted Locally Optimal Projection (WLOP) simplification algorithm. More...
 

Function Documentation

◆ bilateral_smooth_point_set()

template<typename ConcurrencyTag , typename PointRange , typename NamedParameters >
double CGAL::bilateral_smooth_point_set ( PointRange &  points,
unsigned int  k,
const NamedParameters &  np 
)

#include <CGAL/bilateral_smooth_point_set.h>

This function smooths an input point set by iteratively projecting each point onto the implicit surface patch fitted over its k nearest neighbors.

Bilateral projection preserves sharp features according to the normal (gradient) information. Both point positions and normals will be modified. For more details, please see section 4 in [5].

A parallel version of this function is provided and requires the executable to be linked against the Intel TBB library. To control the number of threads used, the user may use the tbb::task_scheduler_init class. See the TBB documentation for more details.

Precondition
Normals must be unit vectors
k >= 2
Template Parameters
ConcurrencyTagenables sequential versus parallel algorithm. Possible values are Sequential_tag And Parallel_tag.
PointRangeis a model of Range. The value type of its iterator is the key type of the named parameter point_map.
Parameters
pointsinput point range.
ksize of the neighborhood for the implicit surface patch fitting. The larger the value is, the smoother the result will be.
npoptional sequence of Named Parameters among the ones listed below.
Named Parameters
point_mapa model of ReadWritePropertyMap with value type geom_traits::Point_3. If this parameter is omitted, CGAL::Identity_property_map<geom_traits::Point_3> is used.
normal_mapa model of ReadWritePropertyMap with value type geom_traits::Vector_3.
sharpness_anglecontrols the sharpness of the result.
callbackan instance of cpp11::function<bool(double)>. It is called regularly when the algorithm is running: the current advancement (between 0. and 1.) is passed as parameter. If it returns true, then the algorithm continues its execution normally; if it returns false, the algorithm is stopped, all points are left unchanged and the function return NaN.
geom_traitsan instance of a geometric traits class, model of Kernel
Returns
Average point movement error. It's a convergence criterium for the algorithm. This value can help the user to decide how many iterations are sufficient.

◆ compute_average_spacing()

template<typename ConcurrencyTag , typename PointRange , typename NamedParameters >
FT CGAL::compute_average_spacing ( const PointRange &  points,
unsigned int  k,
const NamedParameters &  np 
)

#include <CGAL/compute_average_spacing.h>

Computes average spacing from k nearest neighbors.

Precondition
k >= 2.
Template Parameters
ConcurrencyTagenables sequential versus parallel algorithm. Possible values are Sequential_tag and Parallel_tag.
PointRangeis a model of ConstRange. The value type of its iterator is the key type of the named parameter point_map.
Parameters
pointsinput point range.
knumber of neighbors.
npoptional sequence of Named Parameters among the ones listed below.
Named Parameters
point_mapa model of ReadablePropertyMap with value type geom_traits::Point_3. If this parameter is omitted, CGAL::Identity_property_map<geom_traits::Point_3> is used.
callbackan instance of cpp11::function<bool(double)>. It is called regularly when the algorithm is running: the current advancement (between 0. and 1.) is passed as parameter. If it returns true, then the algorithm continues its execution normally; if it returns false, the algorithm is stopped and the average spacing value estimated on the processed subset is returned.
geom_traitsan instance of a geometric traits class, model of Kernel
Returns
average spacing (scalar). The return type FT is a number type. It is either deduced from the geom_traits Named Parameters if provided, or the geometric traits class deduced from the point property map of points.

◆ compute_vcm()

template<typename PointRange , typename NamedParameters >
void CGAL::compute_vcm ( const PointRange &  points,
std::vector< cpp11::array< double, 6 > > &  ccov,
double  offset_radius,
double  convolution_radius,
const NamedParameters &  np 
)

#include <CGAL/vcm_estimate_normals.h>

computes the Voronoi Covariance Measure (VCM) of a point cloud, a construction that can be used for normal estimation and sharp feature detection.

The VCM associates to each point the covariance matrix of its Voronoi cell intersected with the ball of radius offset_radius. In addition, if the second radius convolution_radius is positive, the covariance matrices are smoothed via a convolution process. More specifically, each covariance matrix is replaced by the average of the matrices of the points located at a distance at most convolution_radius. The choice for parameter offset_radius should refer to the geometry of the underlying surface while the choice for parameter convolution_radius should refer to the noise level in the point cloud. For example, if the point cloud is a uniform and noise-free sampling of a smooth surface, offset_radius should be set to the minimum local feature size of the surface, while convolution_radius can be set to zero.

The Voronoi covariance matrix of each vertex is stored in an array a of length 6 and is as follow:

\( \begin{bmatrix} a[0] & a[1] & a[2] \\ a[1] & a[3] & a[4] \\ a[2] & a[4] & a[5] \\ \end{bmatrix}\)
Template Parameters
PointRangeis a model of Range. The value type of its iterator is the key type of the named parameter point_map.
Parameters
pointsinput point range.
ccovoutput range of covariance matrices.
offset_radiusoffset_radius.
convolution_radiusconvolution_radius.
npoptional sequence of Named Parameters among the ones listed below.
Named Parameters
point_mapa model of ReadablePropertyMap with value type geom_traits::Point_3. If this parameter is omitted, CGAL::Identity_property_map<geom_traits::Point_3> is used.
geom_traitsan instance of a geometric traits class, model of Kernel
See also
CGAL::vcm_is_on_feature_edge()
CGAL::vcm_estimate_normals()
Examples:
Point_set_processing_3/edges_example.cpp.

◆ edge_aware_upsample_point_set()

template<typename ConcurrencyTag , typename PointRange , typename OutputIterator , typename NamedParameters >
OutputIterator CGAL::edge_aware_upsample_point_set ( const PointRange &  points,
OutputIterator  output,
const NamedParameters &  np 
)

#include <CGAL/edge_aware_upsample_point_set.h>

This method progressively upsamples the point set while approaching the edge singularities (detected by normal variation), which generates a denser point set from an input point set.

This has applications in point-based rendering, hole filling, and sparse surface reconstruction. Normals of points are required as input. For more details, please refer to [5].

Template Parameters
ConcurrencyTagenables sequential versus parallel versions of compute_average_spacing() (called internally). Possible values are Sequential_tag and Parallel_tag.
PointRangeis a model of ConstRange. The value type of its iterator is the key type of the named parameter point_map.
OutputIteratorType of the output iterator. The type of the objects put in it is std::pair<geom_traits::Point_3, geom_traits::Vector_3>. Note that the user may use a function_output_iterator to match specific needs.
Parameters
pointsinput point range.
outputiterator where output points and normals are put.
npoptional sequence of Named Parameters among the ones listed below.
Named Parameters
point_mapa model of ReadablePropertyMap with value type geom_traits::Point_3. If this parameter is omitted, CGAL::Identity_property_map<geom_traits::Point_3> is used.
normal_mapa model of ReadablePropertyMap with value type geom_traits::Vector_3.
sharpness_anglecontrols the sharpness of the result.
edge_sensitivitycontrols the priority of points inserted along sharp features. See section Parameter: edge_sensitivity for an example.
neighbor_radiusspherical neighborhood radius.
number_of_output_pointsis the number of output points to generate.
geom_traitsan instance of a geometric traits class, model of Kernel

◆ estimate_global_k_neighbor_scale()

template<typename PointRange , typename NamedParameters >
std::size_t CGAL::estimate_global_k_neighbor_scale ( const PointRange &  points,
const NamedParameters &  np 
)

#include <CGAL/estimate_scale.h>

Estimates the global scale in a K nearest neighbors sense.

The computed scale corresponds to the smallest scale such that the K subsets of points have the appearance of a surface in 3D or the appearance of a curve in 2D (see Automatic Scale Estimation).

Template Parameters
PointRangeis a model of ConstRange. The value type of its iterator is the key type of the named parameter point_map.
Parameters
pointsinput point range.
npoptional sequence of Named Parameters among the ones listed below.
Named Parameters
point_mapa model of ReadablePropertyMap with value type geom_traits::Point_3 (or geom_traits::Point_2). If this parameter is omitted, CGAL::Identity_property_map<geom_traits::Point_3> (or CGAL::Identity_property_map<geom_traits::Point_2>) is used.
geom_traitsan instance of a geometric traits class, model of Kernel
Note
This function accepts both 2D and 3D points.
Returns
The estimated scale in the K nearest neighbors sense.
Examples:
Point_set_processing_3/scale_estimation_example.cpp.

◆ estimate_global_range_scale()

template<typename PointRange , typename NamedParameters >
FT CGAL::estimate_global_range_scale ( const PointRange &  points,
const NamedParameters &  np 
)

#include <CGAL/estimate_scale.h>

Estimates the global scale in a range sense.

The computed scale corresponds to the smallest scale such that the subsets of points inside the sphere range have the appearance of a surface in 3D or the appearance of a curve in 2D (see Automatic Scale Estimation).

Template Parameters
PointRangeis a model of ConstRange. The value type of its iterator is the key type of the named parameter point_map.
Parameters
pointsinput point range.
npoptional sequence of Named Parameters among the ones listed below.
Named Parameters
point_mapa model of ReadablePropertyMap with value type geom_traits::Point_3 (or geom_traits::Point_2). If this parameter is omitted, CGAL::Identity_property_map<geom_traits::Point_3> (or CGAL::Identity_property_map<geom_traits::Point_2>) is used.
geom_traitsan instance of a geometric traits class, model of Kernel
Note
This function accepts both 2D and 3D points.
Returns
The estimated scale in the range sense. The return type FT is a number type. It is either deduced from the geom_traits Named Parameters if provided, or the geometric traits class deduced from the point property map of points.
Examples:
Point_set_processing_3/scale_estimation_example.cpp.

◆ estimate_local_k_neighbor_scales()

template<typename PointRange , typename QueryPointRange , typename OutputIterator , typename NamedParameters >
OutputIterator CGAL::estimate_local_k_neighbor_scales ( const PointRange &  points,
const QueryPointRange &  queries,
OutputIterator  output,
const NamedParameters &  np 
)

#include <CGAL/estimate_scale.h>

Estimates the local scale in a K nearest neighbors sense on a set of user-defined query points.

The computed scales correspond to the smallest scales such that the K subsets of points have the appearance of a surface in 3D or the appearance of a curve in 2D (see Automatic Scale Estimation).

Template Parameters
PointRangeis a model of ConstRange. The value type of its iterator is the key type of the named parameter point_map.
QueryPointRangeis a model of ConstRange. The value type of its iterator is the key type of the named parameter query_point_map.
OutputIteratoris used to store the computed scales. It accepts values of type std::size_t.
Parameters
pointsinput point range.
queriesrange of locations where scale must be estimated
outputiterator to store the computed scales
npoptional sequence of Named Parameters among the ones listed below.
Named Parameters
point_mapa model of ReadablePropertyMap with value type geom_traits::Point_3 (or geom_traits::Point_2). If this parameter is omitted, CGAL::Identity_property_map<geom_traits::Point_3> (or CGAL::Identity_property_map<geom_traits::Point_2>) is used.
query_point_mapa model of ReadablePropertyMap with value type geom_traits::Point_3 (or geom_traits::Point_2). If this parameter is omitted, CGAL::Identity_property_map<geom_traits::Point_3> (or CGAL::Identity_property_map<geom_traits::Point_2>) is used.
geom_traitsan instance of a geometric traits class, model of Kernel
Note
This function accepts both 2D and 3D points, but sample points and query must have the same dimension.
Examples:
Point_set_processing_3/scale_estimation_2d_example.cpp.

◆ estimate_local_range_scales()

template<typename PointRange , typename QueryPointRange , typename OutputIterator , typename NamedParameters >
OutputIterator CGAL::estimate_local_range_scales ( const PointRange &  points,
const QueryPointRange &  queries,
OutputIterator  output,
const NamedParameters &  np 
)

#include <CGAL/estimate_scale.h>

Estimates the local scale in a range sense on a set of user-defined query points.

The computed scales correspond to the smallest scales such that the subsets of points included in the sphere range have the appearance of a surface in 3D or the appearance of a curve in 2D (see Automatic Scale Estimation).

Template Parameters
PointRangeis a model of ConstRange. The value type of its iterator is the key type of the named parameter point_map.
QueryPointRangeis a model of ConstRange. The value type of its iterator is the key type of the named parameter query_point_map.
OutputIteratoris used to store the computed scales. It accepts values of type geom_traits::FT.
Parameters
pointsinput point range.
queriesrange of locations where scale must be estimated
outputiterator to store the computed scales
npoptional sequence of Named Parameters among the ones listed below.
Named Parameters
point_mapa model of ReadablePropertyMap with value type geom_traits::Point_3 (or geom_traits::Point_2). If this parameter is omitted, CGAL::Identity_property_map<geom_traits::Point_3> (or CGAL::Identity_property_map<geom_traits::Point_2>) is used.
query_point_mapa model of ReadablePropertyMap with value type geom_traits::Point_3 (or geom_traits::Point_2). If this parameter is omitted, CGAL::Identity_property_map<geom_traits::Point_3> (or CGAL::Identity_property_map<geom_traits::Point_2>) is used.
geom_traitsan instance of a geometric traits class, model of Kernel
Note
This function accepts both 2D and 3D points, but sample points and query must have the same dimension.

◆ grid_simplify_point_set()

template<typename PointRange , typename NamedParameters >
PointRange::iterator CGAL::grid_simplify_point_set ( PointRange &  points,
double  epsilon,
const NamedParameters &  np 
)

#include <CGAL/grid_simplify_point_set.h>

Merges points which belong to the same cell of a grid of cell size = epsilon.

This method modifies the order of input points so as to pack all remaining points first, and returns an iterator over the first point to remove (see erase-remove idiom). For this reason it should not be called on sorted containers.

Precondition
epsilon > 0
Template Parameters
PointRangeis a model of Range. The value type of its iterator is the key type of the named parameter point_map.
Parameters
pointsinput point range.
epsilontolerance value when merging 3D points.
npoptional sequence of Named Parameters among the ones listed below.
Named Parameters
point_mapa model of ReadWritePropertyMap with value type geom_traits::Point_3. If this parameter is omitted, CGAL::Identity_property_map<geom_traits::Point_3> is used.
callbackan instance of cpp11::function<bool(double)>. It is called regularly when the algorithm is running: the current advancement (between 0. and 1.) is passed as parameter. If it returns true, then the algorithm continues its execution normally; if it returns false, the algorithm is stopped and simplification stops with no guarantee on the output.
geom_traitsan instance of a geometric traits class, model of Kernel
Returns
iterator over the first point to remove.
Examples:
Point_set_processing_3/callback_example.cpp, Point_set_processing_3/grid_simplification_example.cpp, Point_set_processing_3/grid_simplify_indices.cpp, and Point_set_processing_3/scale_estimation_example.cpp.

◆ hierarchy_simplify_point_set()

template<typename PointRange , typename NamedParameters >
PointRange::iterator CGAL::hierarchy_simplify_point_set ( PointRange &  points,
const NamedParameters &  np 
)

#include <CGAL/hierarchy_simplify_point_set.h>

Recursively split the point set in smaller clusters until the clusters have less than size elements or until their variation factor is below var_max.

This method modifies the order of input points so as to pack all remaining points first, and returns an iterator over the first point to remove (see erase-remove idiom). For this reason it should not be called on sorted containers.

Precondition
0 < maximum_variation < 1/3
size > 0
Template Parameters
PointRangeis a model of Range. The value type of its iterator is the key type of the named parameter point_map.
Parameters
pointsinput point range.
npoptional sequence of Named Parameters among the ones listed below.
Named Parameters
point_mapa model of ReadWritePropertyMap with value type geom_traits::Point_3. If this parameter is omitted, CGAL::Identity_property_map<geom_traits::Point_3> is used.
sizemaximum cluster size.
maximum_variationmaximum cluster variation value.
diagonalize_traitsa model of DiagonalizeTraits. It can be omitted: if Eigen 3 (or greater) is available and CGAL_EIGEN3_ENABLED is defined then an overload using Eigen_diagonalize_traits is provided. Otherwise, the internal implementation CGAL::Diagonalize_traits is used.
callbackan instance of cpp11::function<bool(double)>. It is called regularly when the algorithm is running: the current advancement (between 0. and 1.) is passed as parameter. If it returns true, then the algorithm continues its execution normally; if it returns false, the algorithm is stopped and simplification stops with no guarantee on the output.
geom_traitsan instance of a geometric traits class, model of Kernel
Returns
iterator over the first point to remove.
Examples:
Point_set_processing_3/hierarchy_simplification_example.cpp.

◆ jet_estimate_normals()

template<typename ConcurrencyTag , typename PointRange , typename NamedParameters >
void CGAL::jet_estimate_normals ( PointRange &  points,
unsigned int  k,
const NamedParameters &  np 
)

#include <CGAL/jet_estimate_normals.h>

Estimates normal directions of the range of points using jet fitting on the k nearest neighbors.

The output normals are randomly oriented.

Precondition
k >= 2
Template Parameters
ConcurrencyTagenables sequential versus parallel algorithm. Possible values are Sequential_tag and Parallel_tag.
PointRangeis a model of Range. The value type of its iterator is the key type of the named parameter point_map.
Parameters
pointsinput point range.
knumber of neighbors
npoptional sequence of Named Parameters among the ones listed below.
Named Parameters
point_mapa model of ReadablePropertyMap with value type geom_traits::Point_3. If this parameter is omitted, CGAL::Identity_property_map<geom_traits::Point_3> is used.
normal_mapa model of ReadWritePropertyMap with value type geom_traits::Vector_3.
degree_fittingdegree of jet fitting.
svd_traitstemplate parameter for the class Monge_via_jet_fitting. If Eigen 3.2 (or greater) is available and CGAL_EIGEN3_ENABLED is defined, then CGAL::Eigen_svd is used.
callbackan instance of cpp11::function<bool(double)>. It is called regularly when the algorithm is running: the current advancement (between 0. and 1.) is passed as parameter. If it returns true, then the algorithm continues its execution normally; if it returns false, the algorithm is stopped and the remaining normals are left unchanged.
geom_traitsan instance of a geometric traits class, model of Kernel

◆ jet_smooth_point_set()

template<typename ConcurrencyTag , typename PointRange , typename NamedParameters >
void CGAL::jet_smooth_point_set ( PointRange &  points,
unsigned int  k,
const NamedParameters &  np 
)

#include <CGAL/jet_smooth_point_set.h>

Smoothes the range of points using jet fitting on the k nearest neighbors and reprojection onto the jet.

As this method relocates the points, it should not be called on containers sorted w.r.t. point locations.

Precondition
k >= 2
Template Parameters
ConcurrencyTagenables sequential versus parallel algorithm. Possible values are Sequential_tag and Parallel_tag.
PointRangeis a model of Range. The value type of its iterator is the key type of the named parameter point_map.
Parameters
pointsinput point range.
knumber of neighbors
npoptional sequence of Named Parameters among the ones listed below.
Named Parameters
point_mapa model of ReadablePropertyMap with value type geom_traits::Point_3. If this parameter is omitted, CGAL::Identity_property_map<geom_traits::Point_3> is used.
degree_fittingdegree of jet fitting.
degree_mongeMonge degree.
svd_traitstemplate parameter for the class Monge_via_jet_fitting. If Eigen 3.2 (or greater) is available and CGAL_EIGEN3_ENABLED is defined, then CGAL::Eigen_svd is used.
callbackan instance of cpp11::function<bool(double)>. It is called regularly when the algorithm is running: the current advancement (between 0. and 1.) is passed as parameter. If it returns true, then the algorithm continues its execution normally; if it returns false, the algorithm is stopped and the remaining points are left unchanged.
geom_traitsan instance of a geometric traits class, model of Kernel

◆ mst_orient_normals()

template<typename PointRange , typename NamedParameters >
PointRange::iterator CGAL::mst_orient_normals ( PointRange &  points,
unsigned int  k,
const NamedParameters &  np 
)

#include <CGAL/mst_orient_normals.h>

Orients the normals of the range of points using the propagation of a seed orientation through a minimum spanning tree of the Riemannian graph.

This method modifies the order of input points so as to pack all sucessfully oriented points first, and returns an iterator over the first point with an unoriented normal (see erase-remove idiom). For this reason it should not be called on sorted containers. It is based on [3].

Warning
This function may fail when Boost version 1.54 is used, because of the following bug: https://svn.boost.org/trac/boost/ticket/9012
Precondition
Normals must be unit vectors
k >= 2
Template Parameters
PointRangeis a model of Range. The value type of its iterator is the key type of the named parameter point_map.
Parameters
pointsinput point range.
knumber of neighbors.
npoptional sequence of Named Parameters among the ones listed below.
Named Parameters
point_mapa model of ReadablePropertyMap with value type geom_traits::Point_3. If this parameter is omitted, CGAL::Identity_property_map<geom_traits::Point_3> is used.
normal_mapa model of ReadWritePropertyMap with value type geom_traits::Vector_3.
point_is_constrained_mapa model of ReadablePropertyMap with value type bool. Points with a true value will be used as seed points: their normal will be considered as already oriented, it won't be altered and it will be propagated to its neighbors. If this parameter is omitted, the highest point (highest Z coordinate) will be used as the unique seed with an upward oriented normal
geom_traitsan instance of a geometric traits class, model of Kernel
Returns
iterator over the first point with an unoriented normal.
Examples:
Point_set_processing_3/normals_example.cpp.

◆ pca_estimate_normals()

template<typename ConcurrencyTag , typename PointRange , typename NamedParameters >
void CGAL::pca_estimate_normals ( PointRange &  points,
unsigned int  k,
const NamedParameters &  np 
)

#include <CGAL/pca_estimate_normals.h>

Estimates normal directions of the range of points by linear least squares fitting of a plane over the k nearest neighbors.

The output normals are randomly oriented.

Precondition
k >= 2
Template Parameters
ConcurrencyTagenables sequential versus parallel algorithm. Possible values are Sequential_tag and Parallel_tag.
PointRangeis a model of Range. The value type of its iterator is the key type of the named parameter point_map.
Parameters
pointsinput point range.
knumber of neighbors
npoptional sequence of Named Parameters among the ones listed below.
Named Parameters
point_mapa model of ReadablePropertyMap with value type geom_traits::Point_3. If this parameter is omitted, CGAL::Identity_property_map<geom_traits::Point_3> is used.
normal_mapa model of WritablePropertyMap with value type geom_traits::Vector_3.
callbackan instance of cpp11::function<bool(double)>. It is called regularly when the algorithm is running: the current advancement (between 0. and 1.) is passed as parameter. If it returns true, then the algorithm continues its execution normally; if it returns false, the algorithm is stopped and the remaining normals are left unchanged.
geom_traitsan instance of a geometric traits class, model of Kernel

◆ random_simplify_point_set()

template<typename PointRange >
PointRange::iterator CGAL::random_simplify_point_set ( PointRange &  points,
double  removed_percentage 
)

#include <CGAL/random_simplify_point_set.h>

Randomly deletes a user-specified fraction of the input points.

This method modifies the order of input points so as to pack all remaining points first, and returns an iterator over the first point to remove (see erase-remove idiom). For this reason it should not be called on sorted containers.

Template Parameters
PointRangeis a model of Range.
Parameters
pointsinput point range.
removed_percentagepercentage of points to remove.
Returns
iterator over the first point to remove.

◆ remove_outliers()

template<typename PointRange , typename NamedParameters >
PointRange::iterator CGAL::remove_outliers ( PointRange &  points,
unsigned int  k,
const NamedParameters &  np 
)

#include <CGAL/remove_outliers.h>

Removes outliers:

  • computes average squared distance to the K nearest neighbors,
  • and sorts the points in increasing order of average distance.

This method modifies the order of input points so as to pack all remaining points first, and returns an iterator over the first point to remove (see erase-remove idiom). For this reason it should not be called on sorted containers.

Precondition
k >= 2
Template Parameters
PointRangeis a model of Range. The value type of its iterator is the key type of the named parameter point_map.
Parameters
pointsinput point range.
knumber of neighbors
npoptional sequence of Named Parameters among the ones listed below.
Named Parameters
point_mapa model of ReadablePropertyMap with value type geom_traits::Point_3. If this parameter is omitted, CGAL::Identity_property_map<geom_traits::Point_3> is used.
threshold_percentmaximum percentage of points to remove.
threshold_distanceminimum distance for a point to be considered as outlier (distance here is the square root of the average squared distance to K nearest neighbors).
callbackan instance of cpp11::function<bool(double)>. It is called regularly when the algorithm is running: the current advancement (between 0. and 1.) is passed as parameter. If it returns true, then the algorithm continues its execution normally; if it returns false, the algorithm is stopped, all points are left unchanged and the function return points.end().
geom_traitsan instance of a geometric traits class, model of Kernel
Returns
iterator over the first point to remove.
Note
There are two thresholds that can be used: threshold_percent and threshold_distance. This function returns the smallest number of outliers such that at least one of these threshold is fullfilled. This means that if threshold_percent=100, only threshold_distance is taken into account; if threshold_distance=0 only threshold_percent is taken into account.
Examples:
Point_set_processing_3/remove_outliers_example.cpp.

◆ structure_point_set()

template<typename PointRange , typename PlaneRange , typename OutputIterator , typename NamedParameters >
OutputIterator CGAL::structure_point_set ( const PointRange &  points,
const PlaneRange &  planes,
OutputIterator  output,
double  epsilon,
const NamedParameters &  np 
)

#include <CGAL/structure_point_set.h>

This is an implementation of the Point Set Structuring algorithm.

This algorithm takes advantage of a set of detected planes: it detects adjacency relationships between planes and resamples the detected planes, edges and corners to produce a structured point set.

The size parameter epsilon is used both for detecting adjacencies and for setting the sampling density of the structured point set.

For more details, please refer to [6].

Template Parameters
PointRangeis a model of ConstRange. The value type of its iterator is the key type of the named parameter point_map.
PlaneRangeis a model of ConstRange. The value type of its iterator is the key type of the named parameter plane_map.
OutputIteratorType of the output iterator. The type of the objects put in it is std::pair<Kernel::Point_3, Kernel::Vector_3>. Note that the user may use a function_output_iterator to match specific needs.
Parameters
pointsinput point range.
planesinput plane range.
outputoutput iterator where output points are written
epsilonsize parameter.
npoptional sequence of Named Parameters among the ones listed below.
Named Parameters
point_mapa model of ReadablePropertyMap with value type geom_traits::Point_3. If this parameter is omitted, CGAL::Identity_property_map<geom_traits::Point_3> is used.
normal_mapa model of ReadablePropertyMap with value type geom_traits::Vector_3.
plane_index_mapa model of ReadablePropertyMap with value type int. Associates the index of a point in the input range to the index of plane (-1 if point does is not assigned to a plane).
plane_mapa model of ReadablePropertyMap with value type geom_traits::Plane_3. If this parameter is omitted, CGAL::Identity_property_map<geom_traits::Plane_3> is used.
attraction_factormultiple of epsilon used to connect simplices.
geom_traitsan instance of a geometric traits class, model of Kernel
Examples:
Point_set_processing_3/structuring_example.cpp.

◆ vcm_estimate_normals() [1/2]

template<typename PointRange , typename NamedParameters >
void CGAL::vcm_estimate_normals ( PointRange &  points,
double  offset_radius,
double  convolution_radius,
const NamedParameters &  np 
)

#include <CGAL/vcm_estimate_normals.h>

Estimates normal directions of the range of points using the Voronoi Covariance Measure with a radius for the convolution.

The output normals are randomly oriented.

See compute_vcm() for a detailed description of the parameters offset_radius and convolution_radius and of the Voronoi Covariance Measure.

Template Parameters
PointRangeis a model of Range. The value type of its iterator is the key type of the named parameter point_map.
Parameters
pointsinput point range.
offset_radiusoffset_radius.
convolution_radiusconvolution_radius.
npoptional sequence of Named Parameters among the ones listed below.
Named Parameters
point_mapa model of ReadablePropertyMap with value type geom_traits::Point_3. If this parameter is omitted, CGAL::Identity_property_map<geom_traits::Point_3> is used.
normal_mapa model of WritablePropertyMap with value type geom_traits::Vector_3.
diagonalize_traitsa model of DiagonalizeTraits. It can be omitted: if Eigen 3 (or greater) is available and CGAL_EIGEN3_ENABLED is defined then an overload using Eigen_diagonalize_traits is provided. Otherwise, the internal implementation CGAL::Diagonalize_traits is used.
geom_traitsan instance of a geometric traits class, model of Kernel

◆ vcm_estimate_normals() [2/2]

template<typename PointRange , typename NamedParameters >
void CGAL::vcm_estimate_normals ( PointRange &  points,
double  offset_radius,
unsigned int  k,
const NamedParameters &  np 
)

#include <CGAL/vcm_estimate_normals.h>

Estimates normal directions of the range of points using the Voronoi Covariance Measure with a number of neighbors for the convolution.

The output normals are randomly oriented.

See compute_vcm() for a detailed description of the parameter offset_radius and of the Voronoi Covariance Measure.

Template Parameters
PointRangeis a model of Range. The value type of its iterator is the key type of the named parameter point_map.
Parameters
pointsinput point range.
offset_radiusoffset_radius.
knumber of neighbor points used for convolution.
npoptional sequence of Named Parameters among the ones listed below.
Named Parameters
point_mapa model of ReadablePropertyMap with value type geom_traits::Point_3. If this parameter is omitted, CGAL::Identity_property_map<geom_traits::Point_3> is used.
normal_mapa model of WritablePropertyMap with value type geom_traits::Vector_3.
diagonalize_traitsa model of DiagonalizeTraits. It can be omitted: if Eigen 3 (or greater) is available and CGAL_EIGEN3_ENABLED is defined then an overload using Eigen_diagonalize_traits is provided. Otherwise, the internal implementation CGAL::Diagonalize_traits is used.
geom_traitsan instance of a geometric traits class, model of Kernel

◆ vcm_is_on_feature_edge()

template<class FT , class VCMTraits >
bool CGAL::vcm_is_on_feature_edge ( cpp11::array< FT, 6 > &  cov,
double  threshold,
VCMTraits   
)

#include <CGAL/vcm_estimate_edges.h>

determines if a point is on a sharp feature edge from a point set for which the Voronoi covariance Measures have been computed.

The sharpness of the edge, specified by parameter threshold, is used to filtered points according to the external angle around a sharp feature.

A point is considered to be on a sharp feature if the external angle alpha at the edge is such that alpha >= 2 / sqrt(3) * sqrt(threshold). In particular this means that if the input contains sharp features with different external angles, the one with the smallest external angle should be considered, which however would result in selecting more points on sharper regions. More details are provided in [7].

Template Parameters
VCMTraitsis a model of DiagonalizeTraits. It can be omitted: if Eigen 3 (or greater) is available and CGAL_EIGEN3_ENABLED is defined then an overload using Eigen_diagonalize_traits is provided. Otherwise, the internal implementation Diagonalize_traits is used.
See also
CGAL::compute_vcm()`
Examples:
Point_set_processing_3/edges_example.cpp.

◆ wlop_simplify_and_regularize_point_set()

template<typename ConcurrencyTag , typename PointRange , typename OutputIterator , typename NamedParameters >
OutputIterator CGAL::wlop_simplify_and_regularize_point_set ( PointRange &  points,
OutputIterator  output,
const NamedParameters &  np 
)

#include <CGAL/wlop_simplify_and_regularize_point_set.h>

This is an implementation of the Weighted Locally Optimal Projection (WLOP) simplification algorithm.

The WLOP simplification algorithm can produce a set of denoised, outlier-free and evenly distributed particles over the original dense point cloud. The core of the algorithm is a Weighted Locally Optimal Projection operator with a density uniformization term. For more details, please refer to [4].

A parallel version of WLOP is provided and requires the executable to be linked against the Intel TBB library. To control the number of threads used, the user may use the tbb::task_scheduler_init class. See the TBB documentation for more details.

Template Parameters
ConcurrencyTagenables sequential versus parallel algorithm. Possible values are Sequential_tag and Parallel_tag.
PointRangeis a model of Range. The value type of its iterator is the key type of the named parameter point_map.
OutputIteratorType of the output iterator. It must accept objects of type geom_traits::Point_3.
Parameters
pointsinput point range.
outputiterator where output points are put.
npoptional sequence of Named Parameters among the ones listed below.
Named Parameters
point_mapa model of ReadWritePropertyMap with value type geom_traits::Point_3. If this parameter is omitted, CGAL::Identity_property_map<geom_traits::Point_3> is used.
normal_mapa model of ReadWritePropertyMap with value type geom_traits::Vector_3.
select_percentagepercentage of points to retain. The default value is set to 5 (%).
neighbor_radiusspherical neighborhood radius. This is a key parameter that needs to be finely tuned. The result will be irregular if too small, but a larger value will impact the runtime. In practice, choosing a radius such that the neighborhood of each sample point includes at least two rings of neighboring sample points gives satisfactory result. The default value is set to 8 times the average spacing of the point set.
number_of_iterationsnumber of iterations to solve the optimsation problem. The default value is 35. More iterations give a more regular result but increase the runtime.
require_uniform_samplingan optional preprocessing, which will give better result if the distribution of the input points is highly non-uniform. The default value is false.
callbackan instance of cpp11::function<bool(double)>. It is called regularly when the algorithm is running: the current advancement (between 0. and 1.) is passed as parameter. If it returns true, then the algorithm continues its execution normally; if it returns false, the algorithm is stopped, no output points are generated.
geom_traitsan instance of a geometric traits class, model of Kernel