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

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

Functions
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<class ForwardIterator , class PointPMap , class Kernel >
void	CGAL::compute_vcm (ForwardIterator first, ForwardIterator beyond, PointPMap point_pmap, std::vector< cpp11::array< typename Kernel::FT, 6 > > &ccov, double offset_radius, double convolution_radius, const Kernel &kernel)
	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 ForwardIterator , typename PointPMap , typename NormalPMap , typename VCMTraits >
void	CGAL::vcm_estimate_normals (ForwardIterator first, ForwardIterator beyond, PointPMap point_pmap, NormalPMap normal_pmap, double offset_radius, double convolution_radius, VCMTraits)
	Estimates normal directions of the points in the range `[first, beyond)` using the Voronoi Covariance Measure with a radius for the convolution. More...

template<typename ForwardIterator , typename PointPMap , typename NormalPMap , typename VCMTraits >
void	CGAL::vcm_estimate_normals (ForwardIterator first, ForwardIterator beyond, PointPMap point_pmap, NormalPMap normal_pmap, double offset_radius, unsigned int k, VCMTraits)
	Estimates normal directions of the points in the range `[first, beyond)` using the Voronoi Covariance Measure with a number of neighbors for the convolution. More...

template<typename Traits , typename OutputIterator >
OutputIterator	CGAL::structure_point_set (typename Traits::Input_range::iterator first, typename Traits::Input_range::iterator beyond, typename Traits::Point_map point_map, typename Traits::Normal_map normal_map, OutputIterator output, Shape_detection_3::Efficient_RANSAC< Traits > &shape_detection, double epsilon, double attraction_factor=3.)
	This is an implementation of the Point Set Structuring algorithm. More...

template<typename ForwardIterator , typename PointPMap , typename NormalPMap , typename Kernel >
ForwardIterator	CGAL::mst_orient_normals (ForwardIterator first, ForwardIterator beyond, PointPMap point_pmap, NormalPMap normal_pmap, unsigned int k, const Kernel &kernel)
	Orients the normals of the `[first, beyond)` range of points using the propagation of a seed orientation through a minimum spanning tree of the Riemannian graph [Hoppe92]. More...

template<typename Concurrency_tag , typename OutputIterator , typename RandomAccessIterator , typename PointPMap , typename Kernel >
OutputIterator	CGAL::wlop_simplify_and_regularize_point_set (RandomAccessIterator first, RandomAccessIterator beyond, OutputIterator output, PointPMap point_pmap, double select_percentage, double radius, unsigned int iter_number, bool require_uniform_sampling, const Kernel &)
	This is an implementation of the Weighted Locally Optimal Projection (WLOP) simplification algorithm. More...

template<typename Concurrency_tag , typename ForwardIterator , typename PointPMap , typename NormalPMap , typename Kernel >
double	CGAL::bilateral_smooth_point_set (ForwardIterator first, ForwardIterator beyond, PointPMap point_pmap, NormalPMap normal_pmap, unsigned int k, typename Kernel::FT sharpness_angle, const Kernel &)
	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 Concurrency_tag , typename OutputIterator , typename ForwardIterator , typename PointPMap , typename NormalPMap , typename Kernel >
OutputIterator	CGAL::edge_aware_upsample_point_set (ForwardIterator first, ForwardIterator beyond, OutputIterator output, PointPMap point_pmap, NormalPMap normal_pmap, const typename Kernel::FT sharpness_angle, typename Kernel::FT edge_sensitivity, typename Kernel::FT neighbor_radius, const std::size_t number_of_output_points, const Kernel &)
	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 ForwardIterator , typename PointPMap , typename DiagonalizeTraits , typename Kernel >
ForwardIterator	CGAL::hierarchy_simplify_point_set (ForwardIterator begin, ForwardIterator end, PointPMap point_pmap, const unsigned int size, const double var_max, const DiagonalizeTraits &, const Kernel &)
	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 ForwardIterator , typename PointPMap , typename Kernel >
ForwardIterator	CGAL::random_simplify_point_set (ForwardIterator first, ForwardIterator beyond, PointPMap, double removed_percentage, const Kernel &)
	Randomly deletes a user-specified fraction of the input points. More...

template<typename Concurrency_tag , typename InputIterator , typename PointPMap , typename Kernel , typename SvdTraits >
void	CGAL::jet_smooth_point_set (InputIterator first, InputIterator beyond, PointPMap point_pmap, unsigned int k, const Kernel &, unsigned int degree_fitting=2, unsigned int degree_monge=2)
	Smoothes the `[first, beyond)` range of points using jet fitting on the k nearest neighbors and reprojection onto the jet. More...

template<typename Concurrency_tag , typename InputIterator , typename PointPMap , typename Kernel >
Kernel::FT	CGAL::compute_average_spacing (InputIterator first, InputIterator beyond, PointPMap point_pmap, unsigned int k, const Kernel &)
	Computes average spacing from k nearest neighbors. More...

template<typename Concurrency_tag , typename ForwardIterator , typename PointPMap , typename NormalPMap , typename Kernel , typename SvdTraits >
void	CGAL::jet_estimate_normals (ForwardIterator first, ForwardIterator beyond, PointPMap point_pmap, NormalPMap normal_pmap, unsigned int k, const Kernel &, unsigned int degree_fitting=2)
	Estimates normal directions of the `[first, beyond)` range of points using jet fitting on the k nearest neighbors. More...

template<typename SamplesInputIterator , typename SamplesPointPMap , typename QueriesInputIterator , typename QueriesPointPMap , typename OutputIterator , typename Kernel >
OutputIterator	CGAL::estimate_local_k_neighbor_scales (SamplesInputIterator first, SamplesInputIterator beyond, SamplesPointPMap samples_pmap, QueriesInputIterator first_query, QueriesInputIterator beyond_query, QueriesPointPMap queries_pmap, OutputIterator output, const Kernel &)
	Estimates the local scale in a K nearest neighbors sense on a set of user-defined query points. More...

template<typename InputIterator , typename PointPMap , typename Kernel >
std::size_t	CGAL::estimate_global_k_neighbor_scale (InputIterator first, InputIterator beyond, PointPMap point_pmap, const Kernel &kernel)
	Estimates the global scale in a K nearest neighbors sense. More...

template<typename SamplesInputIterator , typename SamplesPointPMap , typename QueriesInputIterator , typename QueriesPointPMap , typename OutputIterator , typename Kernel >
OutputIterator	CGAL::estimate_local_range_scales (SamplesInputIterator first, SamplesInputIterator beyond, SamplesPointPMap samples_pmap, QueriesInputIterator first_query, QueriesInputIterator beyond_query, QueriesPointPMap queries_pmap, OutputIterator output, const Kernel &)
	Estimates the local scale in a range sense on a set of user-defined query points. More...

template<typename InputIterator , typename PointPMap , typename Kernel >
Kernel::FT	CGAL::estimate_global_range_scale (InputIterator first, InputIterator beyond, PointPMap point_pmap, const Kernel &kernel)
	Estimates the global scale in a range sense. More...

template<typename Concurrency_tag , typename ForwardIterator , typename PointPMap , typename NormalPMap , typename Kernel >
void	CGAL::pca_estimate_normals (ForwardIterator first, ForwardIterator beyond, PointPMap point_pmap, NormalPMap normal_pmap, unsigned int k, const Kernel &)
	Estimates normal directions of the `[first, beyond)` range of points by linear least squares fitting of a plane over the k nearest neighbors. More...

template<typename InputIterator , typename PointPMap , typename Kernel >
InputIterator	CGAL::remove_outliers (InputIterator first, InputIterator beyond, PointPMap point_pmap, unsigned int k, double threshold_percent, double threshold_distance, const Kernel &)
	Removes outliers: More...

template<typename ForwardIterator , typename PointPMap , typename Kernel >
ForwardIterator	CGAL::grid_simplify_point_set (ForwardIterator first, ForwardIterator beyond, PointPMap point_pmap, double epsilon, const Kernel &)
	Merges points which belong to the same cell of a grid of cell size = `epsilon`. More...

Function Documentation

template<typename Concurrency_tag , typename ForwardIterator , typename PointPMap , typename NormalPMap , typename Kernel >

double CGAL::bilateral_smooth_point_set	(	ForwardIterator	first,
		ForwardIterator	beyond,
		PointPMap	point_pmap,
		NormalPMap	normal_pmap,
		unsigned int	k,
		typename Kernel::FT	sharpness_angle,
		const Kernel &
	)

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

Concurrency_tag	enables sequential versus parallel algorithm. Possible values are `Sequential_tag` and `Parallel_tag`.
ForwardIterator	iterator over input points.
PointPMap	is a model of `ReadWritePropertyMap` with the value type of `ForwardIterator` as key and `Kernel::Point_3` as value type. It can be omitted if the value type of `ForwardIterator` is convertible to `Kernel::Point_3`.
NormalPMap	is a model of `ReadWritePropertyMap` with the value type of `ForwardIterator` as key and `Kernel::Vector_3` as value type.
Kernel	Geometric traits class. It can be omitted and deduced automatically from the value type of `PointPMap` using `Kernel_traits`.

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.

Parameters

first	forward iterator on the first input point.
beyond	past-the-end iterator.
point_pmap	point property map.
normal_pmap	normal property map.
k	size of the neighborhood for the implicit surface patch fitting. The larger the value is, the smoother the result will be.
sharpness_angle	controls the sharpness of the result. The larger the value is, the smoother the result will be. The range of possible value is [0, 90].

#include <CGAL/bilateral_smooth_point_set.h>

template<typename Concurrency_tag , typename InputIterator , typename PointPMap , typename Kernel >

Kernel::FT CGAL::compute_average_spacing	(	InputIterator	first,
		InputIterator	beyond,
		PointPMap	point_pmap,
		unsigned int	k,
		const Kernel &
	)

Computes average spacing from k nearest neighbors.

Precondition: k >= 2.

Template Parameters

Concurrency_tag	enables sequential versus parallel algorithm. Possible values are `Sequential_tag` and `Parallel_tag`.
InputIterator	iterator over input points.
PointPMap	is a model of `ReadablePropertyMap` with value type `Point_3<Kernel>`. It can be omitted if the value type of `InputIterator` is convertible to `Point_3<Kernel>`.
Kernel	Geometric traits class. It can be omitted and deduced automatically from the value type of `PointPMap`.

Returns: average spacing (scalar).

Parameters

first	iterator over the first input point.
beyond	past-the-end iterator over the input points.
point_pmap	property map: value_type of InputIterator -> Point_3
k	number of neighbors.

#include <CGAL/compute_average_spacing.h>

template<class ForwardIterator , class PointPMap , class Kernel >

void CGAL::compute_vcm	(	ForwardIterator	first,
		ForwardIterator	beyond,
		PointPMap	point_pmap,
		std::vector< cpp11::array< typename Kernel::FT, 6 > > &	ccov,
		double	offset_radius,
		double	convolution_radius,
		const Kernel &	kernel
	)

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

ForwardIterator	iterator over input points.
PointPMap	is a model of `ReadablePropertyMap` with a value_type = `Kernel::Point_3`.
CovariancePMap	is a model of `ReadWritePropertyMap` with a value_type = `cpp11::array<Kernel::FT,6>`.
Kernel	Geometric traits class.

See Also: CGAL::vcm_is_on_feature_edge(); CGAL::vcm_estimate_normals()

#include <CGAL/vcm_estimate_normals.h>

Examples:: Point_set_processing_3/edges_example.cpp.

template<typename Concurrency_tag , typename OutputIterator , typename ForwardIterator , typename PointPMap , typename NormalPMap , typename Kernel >

OutputIterator CGAL::edge_aware_upsample_point_set	(	ForwardIterator	first,
		ForwardIterator	beyond,
		OutputIterator	output,
		PointPMap	point_pmap,
		NormalPMap	normal_pmap,
		const typename Kernel::FT	sharpness_angle,
		typename Kernel::FT	edge_sensitivity,
		typename Kernel::FT	neighbor_radius,
		const std::size_t	number_of_output_points,
		const Kernel &
	)

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

Concurrency_tag	enables sequential versus parallel versions of `compute_average_spacing()` (called internally). Possible values are `Sequential_tag` and `Parallel_tag`.
OutputIterator	Type 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.
ForwardIterator	iterator over input points.
PointPMap	is a model of `ReadablePropertyMap` with the value type of `ForwardIterator` as key and `Kernel::Point_3` as value type. It can be omitted if the value type of `ForwardIterator` is convertible to `Kernel::Point_3`.
NormalPMap	is a model of `ReadablePropertyMap` with the value type of `ForwardIterator` as key and `Kernel::Vector_3` as value type.
Kernel	Geometric traits class. It can be omitted and deduced automatically from the value type of `PointPMap` using `Kernel_traits`.

Parameters

first	forward iterator on the first input point.
beyond	past-the-end iterator.
output	output iterator where output points and normals are put.
point_pmap	point property map.
normal_pmap	vector property map.
sharpness_angle	controls the preservation of sharp features. The larger the value is, the smoother the result will be. The range of possible values is `[0, 90]`. See section Parameter: sharpness_angle for an example.
edge_sensitivity	larger values of edge-sensitivity give higher priority to inserting points along sharp features. The range of possible values is `[0, 1]`. See section Parameter: edge_sensitivity for an example.
neighbor_radius	indicates the radius of the largest hole that should be filled. The default value is set to 3 times the average spacing of the point set. If the value given by user is smaller than the average spacing, the function will use the default value instead.
number_of_output_points	number of output points to generate.

#include <CGAL/edge_aware_upsample_point_set.h>

template<typename InputIterator , typename PointPMap , typename Kernel >

std::size_t CGAL::estimate_global_k_neighbor_scale	(	InputIterator	first,
		InputIterator	beyond,
		PointPMap	point_pmap,
		const Kernel &	kernel
	)

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

InputIterator	iterator over input points.
PointPMap	is a model of `ReadablePropertyMap` with value type `Point_3<Kernel>` or `Point_2<Kernel>`. It can be omitted if the value type of `InputIterator` is convertible to `Point_3<Kernel>` or to `Point_2<Kernel>`.
Kernel	Geometric traits class. It can be omitted and deduced automatically from the value type of `PointPMap`.

Note: This function accepts both 2D and 3D points.

Returns: The estimated scale in the K nearest neighbors sense.

Parameters

first	iterator over the first input point.
beyond	past-the-end iterator over the input points.
point_pmap	property map: value_type of InputIterator -> Point_3 or Point_2
kernel	geometric traits.

#include <CGAL/estimate_scale.h>

Examples:: Point_set_processing_3/scale_estimation_example.cpp.

template<typename InputIterator , typename PointPMap , typename Kernel >

Kernel::FT CGAL::estimate_global_range_scale	(	InputIterator	first,
		InputIterator	beyond,
		PointPMap	point_pmap,
		const Kernel &	kernel
	)

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

InputIterator	iterator over input points.
PointPMap	is a model of `ReadablePropertyMap` with value type `Point_3<Kernel>` or `Point_2<Kernel>`. It can be omitted if the value type of `InputIterator` is convertible to `Point_3<Kernel>` or to `Point_2<Kernel>`.
Kernel	Geometric traits class. It can be omitted and deduced automatically from the value type of `PointPMap`.

Note: This function accepts both 2D and 3D points.

Returns: The estimated scale in the range sense.

Parameters

first	iterator over the first input point.
beyond	past-the-end iterator over the input points.
point_pmap	property map: value_type of InputIterator -> Point_3 or Point_3
kernel	geometric traits.

#include <CGAL/estimate_scale.h>

Examples:: Point_set_processing_3/scale_estimation_example.cpp.

template<typename SamplesInputIterator , typename SamplesPointPMap , typename QueriesInputIterator , typename QueriesPointPMap , typename OutputIterator , typename Kernel >

OutputIterator CGAL::estimate_local_k_neighbor_scales	(	SamplesInputIterator	first,
		SamplesInputIterator	beyond,
		SamplesPointPMap	samples_pmap,
		QueriesInputIterator	first_query,
		QueriesInputIterator	beyond_query,
		QueriesPointPMap	queries_pmap,
		OutputIterator	output,
		const Kernel &
	)

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

SamplesInputIterator	iterator over input sample points.
SamplesPointPMap	is a model of `ReadablePropertyMap` with value type `Point_3<Kernel>` or `Point_2<Kernel>`. It can be omitted if the value type of `SamplesInputIterator` is convertible to `Point_3<Kernel>` or to `Point_2<Kernel>`.
QueriesInputIterator	iterator over points where scale should be computed.
QueriesInputIterator	is a model of `ReadablePropertyMap` with value type `Point_3<Kernel>` or `Point_2<Kernel>`. It can be omitted if the value type of `QueriesInputIterator` is convertible to `Point_3<Kernel>` or to `Point_2<Kernel>`.
OutputIterator	is used to store the computed scales. It accepts values of type `std::size_t`.
Kernel	Geometric traits class. It can be omitted and deduced automatically from the value type of `SamplesPointPMap`.

Note: This function accepts both 2D and 3D points, but sample points and query must have the same dimension.

Parameters

first	iterator over the first input sample.
beyond	past-the-end iterator over the input samples.
samples_pmap	property map: value_type of InputIterator -> Point_3 or Point_2
first_query	iterator over the first point where scale must be estimated
beyond_query	past-the-end iterator over the points where scale must be estimated
queries_pmap	property map: value_type of InputIterator -> Point_3 or Point_2
output	output iterator to store the computed scales

#include <CGAL/estimate_scale.h>

Examples:: Point_set_processing_3/scale_estimation_2d_example.cpp.

template<typename SamplesInputIterator , typename SamplesPointPMap , typename QueriesInputIterator , typename QueriesPointPMap , typename OutputIterator , typename Kernel >

OutputIterator CGAL::estimate_local_range_scales	(	SamplesInputIterator	first,
		SamplesInputIterator	beyond,
		SamplesPointPMap	samples_pmap,
		QueriesInputIterator	first_query,
		QueriesInputIterator	beyond_query,
		QueriesPointPMap	queries_pmap,
		OutputIterator	output,
		const Kernel &
	)

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

SamplesInputIterator	iterator over input sample points.
SamplesPointPMap	is a model of `ReadablePropertyMap` with value type `Point_3<Kernel>` or `Point_2<Kernel>`. It can be omitted if the value type of `SamplesInputIterator` is convertible to `Point_3<Kernel>` or to `Point_2<Kernel>`.
QueriesInputIterator	iterator over points where scale should be computed.
QueriesInputIterator	is a model of `ReadablePropertyMap` with value type `Point_3<Kernel>` or `Point_2<Kernel>`. It can be omitted if the value type of `QueriesInputIterator` is convertible to `Point_3<Kernel>` or to `Point_2<Kernel>`.
OutputIterator	is used to store the computed scales. It accepts values of type `Kernel::FT`.
Kernel	Geometric traits class. It can be omitted and deduced automatically from the value type of `SamplesPointPMap`.

Note: This function accepts both 2D and 3D points, but sample points and query must have the same dimension.

Parameters

first	iterator over the first input sample.
beyond	past-the-end iterator over the input samples.
samples_pmap	property map: value_type of InputIterator -> Point_3 or Point_2
first_query	iterator over the first point where scale must be estimated
beyond_query	past-the-end iterator over the points where scale must be estimated
queries_pmap	property map: value_type of InputIterator -> Point_3 or Point_2
output	output iterator to store the computed scales

#include <CGAL/estimate_scale.h>

template<typename ForwardIterator , typename PointPMap , typename Kernel >

ForwardIterator CGAL::grid_simplify_point_set	(	ForwardIterator	first,
		ForwardIterator	beyond,
		PointPMap	point_pmap,
		double	epsilon,
		const Kernel &
	)

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

ForwardIterator	iterator over input points.
PointPMap	is a model of `ReadablePropertyMap` with value type `Point_3<Kernel>`. It can be omitted if the value type of `ForwardIterator` is convertible to `Point_3<Kernel>`.
Kernel	Geometric traits class. It can be omitted and deduced automatically from the value type of `PointPMap`.

Returns: iterator over the first point to remove.

Parameters

first	iterator over the first input point.
beyond	past-the-end iterator over the input points.
point_pmap	property map: value_type of ForwardIterator -> Point_3
epsilon	tolerance value when merging 3D points.

#include <CGAL/grid_simplify_point_set.h>

Examples:: 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.

template<typename ForwardIterator , typename PointPMap , typename DiagonalizeTraits , typename Kernel >

ForwardIterator CGAL::hierarchy_simplify_point_set	(	ForwardIterator	begin,
		ForwardIterator	end,
		PointPMap	point_pmap,
		const unsigned int	size,
		const double	var_max,
		const DiagonalizeTraits &	,
		const Kernel &
	)

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 < var_max < 1/3; size > 0

Template Parameters

ForwardIterator	iterator over input points.
PointPMap	is a model of `ReadablePropertyMap` with value type `Point_3<Kernel>`. It can be omitted if the value type of `ForwardIterator` is convertible to `Point_3<Kernel>`.
DiagonalizeTraits	is 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 `Internal_diagonalize_traits` is used.
Kernel	Geometric traits class. It can be omitted and deduced automatically from the value type of `PointPMap`.

Returns: iterator over the first point to remove.

#include <CGAL/hierarchy_simplify_point_set.h>

Examples:: Point_set_processing_3/hierarchy_simplification_example.cpp.

template<typename Concurrency_tag , typename ForwardIterator , typename PointPMap , typename NormalPMap , typename Kernel , typename SvdTraits >

void CGAL::jet_estimate_normals	(	ForwardIterator	first,
		ForwardIterator	beyond,
		PointPMap	point_pmap,
		NormalPMap	normal_pmap,
		unsigned int	k,
		const Kernel &	,
		unsigned int	degree_fitting = `2`
	)

Estimates normal directions of the [first, beyond) range of points using jet fitting on the k nearest neighbors.

The output normals are randomly oriented.

Precondition: k >= 2

Template Parameters

Concurrency_tag	enables sequential versus parallel algorithm. Possible values are `Sequential_tag` and `Parallel_tag`.
ForwardIterator	iterator model of the concept of the same name over input points and able to store output normals.
PointPMap	is a model of `ReadablePropertyMap` with value type `Point_3<Kernel>`. It can be omitted if the value type of `ForwardIterator` is convertible to `Point_3<Kernel>`.
NormalPMap	is a model of `WritablePropertyMap` with value type `Vector_3<Kernel>`.
Kernel	Geometric traits class. It can be omitted and deduced automatically from the value type of `PointPMap`.
SvdTraits	template parameter for the class `Monge_via_jet_fitting` that can be ommited under conditions described in the documentation of `Monge_via_jet_fitting`.

Parameters

first	iterator over the first input point.
beyond	past-the-end iterator over the input points.
point_pmap	property map: value_type of ForwardIterator -> Point_3.
normal_pmap	property map: value_type of ForwardIterator -> Vector_3.
k	number of neighbors.
degree_fitting	fitting degree

#include <CGAL/jet_estimate_normals.h>

template<typename Concurrency_tag , typename InputIterator , typename PointPMap , typename Kernel , typename SvdTraits >

void CGAL::jet_smooth_point_set	(	InputIterator	first,
		InputIterator	beyond,
		PointPMap	point_pmap,
		unsigned int	k,
		const Kernel &	,
		unsigned int	degree_fitting = `2`,
		unsigned int	degree_monge = `2`
	)

Smoothes the [first, beyond) 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

Concurrency_tag	enables sequential versus parallel algorithm. Possible values are `Sequential_tag` and `Parallel_tag`.
InputIterator	iterator over input points.
PointPMap	is a model of `ReadWritePropertyMap` with value type `Point_3<Kernel>`. It can be omitted if the value type of `InputIterator` is convertible to `Point_3<Kernel>`.
Kernel	Geometric traits class. It can be omitted and deduced automatically from the value type of `PointPMap`.
SvdTraits	template parameter for the class `Monge_via_jet_fitting` that can be ommited under conditions described in the documentation of `Monge_via_jet_fitting`.

Parameters

first	iterator over the first input point.
beyond	past-the-end iterator over the input points.
point_pmap	property map: value_type of InputIterator -> Point_3.
k	number of neighbors.
degree_fitting	fitting degree
degree_monge	Monge degree

#include <CGAL/jet_smooth_point_set.h>

template<typename ForwardIterator , typename PointPMap , typename NormalPMap , typename Kernel >

ForwardIterator CGAL::mst_orient_normals	(	ForwardIterator	first,
		ForwardIterator	beyond,
		PointPMap	point_pmap,
		NormalPMap	normal_pmap,
		unsigned int	k,
		const Kernel &	kernel
	)

Orients the normals of the [first, beyond) range of points using the propagation of a seed orientation through a minimum spanning tree of the Riemannian graph [Hoppe92].

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.

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

ForwardIterator	iterator over input points.
PointPMap	is a model of `ReadablePropertyMap` with value type `Point_3<Kernel>`. It can be omitted if the value type of `ForwardIterator` is convertible to `Point_3<Kernel>`.
NormalPMap	is a model of `ReadWritePropertyMap` with value type `Vector_3<Kernel>` .
Kernel	Geometric traits class. It can be omitted and deduced automatically from the value type of `PointPMap`.

Returns: iterator over the first point with an unoriented normal.

Parameters

first	iterator over the first input point.
beyond	past-the-end iterator over the input points.
point_pmap	property map: value_type of ForwardIterator -> Point_3.
normal_pmap	property map: value_type of ForwardIterator -> Vector_3.
k	number of neighbors
kernel	geometric traits.

#include <CGAL/mst_orient_normals.h>

Examples:: Point_set_processing_3/normals_example.cpp.

template<typename Concurrency_tag , typename ForwardIterator , typename PointPMap , typename NormalPMap , typename Kernel >

void CGAL::pca_estimate_normals	(	ForwardIterator	first,
		ForwardIterator	beyond,
		PointPMap	point_pmap,
		NormalPMap	normal_pmap,
		unsigned int	k,
		const Kernel &
	)

Estimates normal directions of the [first, beyond) 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

Concurrency_tag	enables sequential versus parallel algorithm. Possible values are `Sequential_tag` and `Parallel_tag`.
ForwardIterator	iterator over input points.
PointPMap	is a model of `ReadablePropertyMap` with value type `Point_3<Kernel>`. It can be omitted if the value type of `ForwardIterator` is convertible to `Point_3<Kernel>`.
NormalPMap	is a model of `WritablePropertyMap` with value type `Vector_3<Kernel>`.
Kernel	Geometric traits class. It can be omitted and deduced automatically from the value type of `PointPMap`.

Parameters

first	iterator over the first input point.
beyond	past-the-end iterator over the input points.
point_pmap	property map: value_type of ForwardIterator -> Point_3.
normal_pmap	property map: value_type of ForwardIterator -> Vector_3.
k	number of neighbors.

#include <CGAL/pca_estimate_normals.h>

template<typename ForwardIterator , typename PointPMap , typename Kernel >

ForwardIterator CGAL::random_simplify_point_set	(	ForwardIterator	first,
		ForwardIterator	beyond,
		PointPMap	,
		double	removed_percentage,
		const Kernel &
	)

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

ForwardIterator	iterator over input points.
PointPMap	is a model of `ReadablePropertyMap` with value type `Point_3<Kernel>`. It can be omitted if the value type of `ForwardIterator` is convertible to `Point_3<Kernel>`.
Kernel	Geometric traits class. It can be omitted and deduced automatically from the value type of `PointPMap`.

Returns: iterator over the first point to remove.

Parameters

first	iterator over the first input point.
beyond	past-the-end iterator over the input points.
removed_percentage	percentage of points to remove.

#include <CGAL/random_simplify_point_set.h>

template<typename InputIterator , typename PointPMap , typename Kernel >

InputIterator CGAL::remove_outliers	(	InputIterator	first,
		InputIterator	beyond,
		PointPMap	point_pmap,
		unsigned int	k,
		double	threshold_percent,
		double	threshold_distance,
		const Kernel &
	)

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

InputIterator	iterator over input points.
PointPMap	is a model of `ReadablePropertyMap` with value type `Point_3<Kernel>`. It can be omitted ifthe value type of `InputIterator` is convertible to `Point_3<Kernel>`.
Kernel	Geometric traits class. It can be omitted and deduced automatically from the value type of `PointPMap`.

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.

Parameters

first	iterator over the first input point.
beyond	past-the-end iterator over the input points.
point_pmap	property map: value_type of InputIterator -> Point_3
k	number of neighbors.
threshold_percent	maximum percentage of points to remove.
threshold_distance	minimum distance for a point to be considered as outlier (distance here is the square root of the average squared distance to K nearest neighbors)

#include <CGAL/remove_outliers.h>

Examples:: Point_set_processing_3/remove_outliers_example.cpp.

template<typename Traits , typename OutputIterator >

OutputIterator CGAL::structure_point_set	(	typename Traits::Input_range::iterator	first,
		typename Traits::Input_range::iterator	beyond,
		typename Traits::Point_map	point_map,
		typename Traits::Normal_map	normal_map,
		OutputIterator	output,
		Shape_detection_3::Efficient_RANSAC< Traits > &	shape_detection,
		double	epsilon,
		double	attraction_factor = `3.`
	)

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

Traits

a model of EfficientRANSACTraits that must provide in addition a function Intersect_3 intersection_3_object() const and a functor Intersect_3 with:

boost::optional< boost::variant< Traits::Plane_3, Traits::Line_3 > > operator()(typename Traits::Plane_3, typename Traits::Plane_3)
boost::optional< boost::variant< Traits::Line_3, Traits::Point_3 > > operator()(typename Traits::Line_3, typename Traits::Plane_3)

OutputIterator Type of the output iterator. The type of the objects put in it is std::pair<Traits::Point_3, Traits::Vector_3>. Note that the user may use a function_output_iterator to match specific needs.

Note: If no plane is found in the shape detection object, the algorithm does nothing and the output points are the unaltered input points.; Both property maps can be omitted if the default constructors of these property maps can be safely used.

Parameters

first	iterator over the first input point.
beyond	past-the-end iterator over the input points.
point_map	property map: value_type of InputIterator -> Point_3.
normal_map	property map: value_type of InputIterator -> Vector_3.
output	output iterator where output points are written
shape_detection	shape detection object
epsilon	size parameter
attraction_factor	attraction factor

#include <CGAL/structure_point_set.h>

Examples:: Point_set_processing_3/structuring_example.cpp.

template<typename ForwardIterator , typename PointPMap , typename NormalPMap , typename VCMTraits >

void CGAL::vcm_estimate_normals	(	ForwardIterator	first,
		ForwardIterator	beyond,
		PointPMap	point_pmap,
		NormalPMap	normal_pmap,
		double	offset_radius,
		double	convolution_radius,
		VCMTraits
	)

Estimates normal directions of the points in the range [first, beyond) 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

ForwardIterator	iterator over input points.
PointPMap	is a model of `ReadablePropertyMap` with a value_type = `Kernel::Point_3`.
NormalPMap	is a model of `WritablePropertyMap` with a value_type = `Kernel::Vector_3`.
VCMTraits	is 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.

Parameters

first	iterator over the first input point.
beyond	past-the-end iterator over the input points.
point_pmap	property map: value_type of ForwardIterator -> Point_3.
normal_pmap	property map: value_type of ForwardIterator -> Vector_3.
offset_radius	offset radius.
convolution_radius	convolution radius.

#include <CGAL/vcm_estimate_normals.h>

template<typename ForwardIterator , typename PointPMap , typename NormalPMap , typename VCMTraits >

void CGAL::vcm_estimate_normals	(	ForwardIterator	first,
		ForwardIterator	beyond,
		PointPMap	point_pmap,
		NormalPMap	normal_pmap,
		double	offset_radius,
		unsigned int	k,
		VCMTraits
	)

Estimates normal directions of the points in the range [first, beyond) 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

ForwardIterator	iterator over input points.
PointPMap	is a model of `ReadablePropertyMap` with a value_type = `Kernel::Point_3`.
NormalPMap	is a model of `WritablePropertyMap` with a value_type = `Kernel::Vector_3`.
VCMTraits	is 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.

Parameters

first	iterator over the first input point.
beyond	past-the-end iterator over the input points.
point_pmap	property map: value_type of ForwardIterator -> Point_3.
normal_pmap	property map: value_type of ForwardIterator -> Vector_3.
offset_radius	offset radius.
k	number of neighbor points used for the convolution.

#include <CGAL/vcm_estimate_normals.h>

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.

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

VCMTraits is 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()`

#include <CGAL/vcm_estimate_edges.h>

Examples:: Point_set_processing_3/edges_example.cpp.

template<typename Concurrency_tag , typename OutputIterator , typename RandomAccessIterator , typename PointPMap , typename Kernel >

OutputIterator CGAL::wlop_simplify_and_regularize_point_set	(	RandomAccessIterator	first,
		RandomAccessIterator	beyond,
		OutputIterator	output,
		PointPMap	point_pmap,
		double	select_percentage,
		double	radius,
		unsigned int	iter_number,
		bool	require_uniform_sampling,
		const Kernel &
	)

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

Concurrency_tag	enables sequential versus parallel algorithm. Possible values are `Sequential_tag` and `Parallel_tag`.
OutputIterator	Type of the output iterator. It must accept objects of type `Kernel::Point_3`.
RandomAccessIterator	Iterator over input points.
PointPMap	is a model of `ReadablePropertyMap` with the value type of `ForwardIterator` as key type and `Kernel::Point_3` as value type. It can be omitted if the value type of `RandomAccessIterator` is convertible to `Kernel::Point_3`.
Kernel	Geometric traits class. It can be omitted and deduced automatically from the value type of `PointPMap` using `Kernel_traits`.

Parameters

first	random-access iterator to the first input point.
beyond	past-the-end iterator.
output	output iterator where output points are put.
point_pmap	point property map.
select_percentage	percentage of points to retain. The default value is set to 5 (%).
radius	spherical 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.
iter_number	number 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_sampling	an optional preprocessing, which will give better result if the distribution of the input points is highly non-uniform. The default value is `false`.

#include <CGAL/wlop_simplify_and_regularize_point_set.h>

Examples:: Point_set_processing_3/wlop_simplify_and_regularize_point_set_example.cpp.

Classes

Functions

Function Documentation