Distance Functions

Functions to compute the distance between meshes, between a mesh and a point set and between a point set and a mesh.

Functions
template<class PointOutputIterator , class TriangleMesh , class NamedParameters = parameters::Default_named_parameters>
PointOutputIterator	CGAL::Polygon_mesh_processing::sample_triangle_mesh (const TriangleMesh &tm, PointOutputIterator out, const NamedParameters &np=parameters::default_values())
	generates points on tm and outputs them to out; the sampling method is selected using named parameters.
template<class PointOutputIterator , class TriangleRange , class PointRange , class NamedParameters = parameters::Default_named_parameters>
PointOutputIterator	CGAL::Polygon_mesh_processing::sample_triangle_soup (const PointRange &points, const TriangleRange &triangles, PointOutputIterator out, const NamedParameters &np=parameters::default_values())
	generates points on a triangle soup and puts them to out; the sampling method is selected using named parameters.
template<class Concurrency_tag , class TriangleMesh , class PointRange , class NamedParameters = parameters::Default_named_parameters>
double	CGAL::Polygon_mesh_processing::max_distance_to_triangle_mesh (const PointRange &points, const TriangleMesh &tm, const NamedParameters &np=parameters::default_values())
	returns the distance to tm of the point from points that is the furthest from tm.
template<class Concurrency_tag , class TriangleMesh , class NamedParameters1 = parameters::Default_named_parameters, class NamedParameters2 = parameters::Default_named_parameters>
double	CGAL::Polygon_mesh_processing::approximate_Hausdorff_distance (const TriangleMesh &tm1, const TriangleMesh &tm2, const NamedParameters1 &np1=parameters::default_values(), const NamedParameters2 &np2=parameters::default_values())
	computes the approximate Hausdorff distance from tm1 to tm2 by returning the distance of the farthest point from tm2 amongst a sampling of tm1 generated with the function sample_triangle_mesh() with tm1 and np1 as parameter.
template<class Concurrency_tag , class TriangleMesh , class NamedParameters1 = parameters::Default_named_parameters, class NamedParameters2 = parameters::Default_named_parameters>
double	CGAL::Polygon_mesh_processing::approximate_symmetric_Hausdorff_distance (const TriangleMesh &tm1, const TriangleMesh &tm2, const NamedParameters1 &np1=parameters::default_values(), const NamedParameters2 &np2=parameters::default_values())
	returns the approximate symmetric Hausdorff distance between tm1 and tm2, that is the maximum of approximate_Hausdorff_distance(tm1, tm2, np1, np2) and approximate_Hausdorff_distance(tm2, tm1, np2, np1).
template<class TriangleMesh , class PointRange , class NamedParameters = parameters::Default_named_parameters>
double	CGAL::Polygon_mesh_processing::approximate_max_distance_to_point_set (const TriangleMesh &tm, const PointRange &points, const double precision, const NamedParameters &np=parameters::default_values())
	returns an approximation of the distance between points and the point lying on tm that is the farthest from points.
template<class Concurrency_tag , class TriangleMesh1 , class TriangleMesh2 , class NamedParameters1 = parameters::Default_named_parameters, class NamedParameters2 = parameters::Default_named_parameters>
double	CGAL::Polygon_mesh_processing::bounded_error_Hausdorff_distance (const TriangleMesh1 &tm1, const TriangleMesh2 &tm2, const double error_bound=0.0001, const NamedParameters1 &np1=parameters::default_values(), const NamedParameters2 &np2=parameters::default_values())
	returns an estimate on the Hausdorff distance between tm1 and tm2 that is at most error_bound away from the actual Hausdorff distance between the two given meshes.
template<class Concurrency_tag , class TriangleMesh1 , class TriangleMesh2 , class NamedParameters1 = parameters::Default_named_parameters, class NamedParameters2 = parameters::Default_named_parameters>
double	CGAL::Polygon_mesh_processing::bounded_error_symmetric_Hausdorff_distance (const TriangleMesh1 &tm1, const TriangleMesh2 &tm2, const double error_bound, const NamedParameters1 &np1=parameters::default_values(), const NamedParameters2 &np2=parameters::default_values())
	returns the the symmetric Hausdorff distance, that is the maximum of bounded_error_Hausdorff_distance(tm1, tm2, error_bound, np1, np2) and bounded_error_Hausdorff_distance(tm2, tm1, error_bound, np2, np1).
template<class Concurrency_tag , class TriangleMesh1 , class TriangleMesh2 , class NamedParameters1 = parameters::Default_named_parameters, class NamedParameters2 = parameters::Default_named_parameters>
bool	CGAL::Polygon_mesh_processing::is_Hausdorff_distance_larger (const TriangleMesh1 &tm1, const TriangleMesh2 &tm2, const double distance_bound, const double error_bound, const NamedParameters1 &np1=parameters::default_values(), const NamedParameters2 &np2=parameters::default_values())
	returns true if the Hausdorff distance between two meshes is larger than the user-defined max distance, otherwise it returns false.

Function Documentation

approximate_Hausdorff_distance()

template<class Concurrency_tag , class TriangleMesh , class NamedParameters1 = parameters::Default_named_parameters, class NamedParameters2 = parameters::Default_named_parameters>

double CGAL::Polygon_mesh_processing::approximate_Hausdorff_distance	(	const TriangleMesh &	tm1,
		const TriangleMesh &	tm2,
		const NamedParameters1 &	np1 = parameters::default_values(),
		const NamedParameters2 &	np2 = parameters::default_values()
	)

#include <CGAL/Polygon_mesh_processing/distance.h>

computes the approximate Hausdorff distance from tm1 to tm2 by returning the distance of the farthest point from tm2 amongst a sampling of tm1 generated with the function sample_triangle_mesh() with tm1 and np1 as parameter.

A parallel version 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, Parallel_tag, and Parallel_if_available_tag.
TriangleMesh	a model of the concepts EdgeListGraph and FaceListGraph
NamedParameters1	a sequence of Named Parameters for tm1
NamedParameters2	a sequence of Named Parameters for tm2

Parameters

tm1	the triangle mesh that will be sampled
tm2	the triangle mesh to compute the distance to
np1	an optional sequence of Named Parameters forwarded to sample_triangle_mesh()
np2	an optional sequence of Named Parameters among the ones listed below

Optional Named Parameters

vertex_point_map a property map associating points to the vertices of tm2 Type: a class model of ReadablePropertyMap with boost::graph_traits<TriangleMesh>::vertex_descriptor as key type and Point_3 as value type Default: boost::get(CGAL::vertex_point, tm2) Extra: If this parameter is omitted, an internal property map for CGAL::vertex_point_t must be available in TriangleMesh.

Precondition

tm1 and tm2 are non-empty triangle meshes.

Examples

Polygon_mesh_processing/hausdorff_distance_remeshing_example.cpp.

approximate_max_distance_to_point_set()

template<class TriangleMesh , class PointRange , class NamedParameters = parameters::Default_named_parameters>

double CGAL::Polygon_mesh_processing::approximate_max_distance_to_point_set	(	const TriangleMesh &	tm,
		const PointRange &	points,
		const double	precision,
		const NamedParameters &	np = parameters::default_values()
	)

#include <CGAL/Polygon_mesh_processing/distance.h>

returns an approximation of the distance between points and the point lying on tm that is the farthest from points.

Template Parameters

PointRange	a range of Point_3, model of Range
TriangleMesh	a model of the concept FaceListGraph
NamedParameters	a sequence of Named Parameters

Parameters

tm	a triangle mesh
points	a range of points
precision	for each triangle of tm, the distance of its farthest point from points is bounded. A triangle is subdivided into sub-triangles so that the difference of its distance bounds is smaller than precision. precision must be strictly positive to avoid infinite loops.
np	an optional sequence of Named Parameters among the ones listed below

Optional Named Parameters

vertex_point_map a property map associating points to the vertices of tm Type: a class model of ReadablePropertyMap with boost::graph_traits<TriangleMesh>::vertex_descriptor as key type and Point_3 as value type Default: boost::get(CGAL::vertex_point, tm) Extra: If this parameter is omitted, an internal property map for CGAL::vertex_point_t must be available in TriangleMesh.
geom_traits an instance of a geometric traits class Type: a class model of PMPDistanceTraits Default: a CGAL Kernel deduced from the point type, using CGAL::Kernel_traits Extra: The geometric traits class must be compatible with the vertex point type.

Precondition

tm is a non-empty triangle mesh and points is not empty.

Examples

Poisson_surface_reconstruction_3/poisson_reconstruction_example.cpp.

approximate_symmetric_Hausdorff_distance()

template<class Concurrency_tag , class TriangleMesh , class NamedParameters1 = parameters::Default_named_parameters, class NamedParameters2 = parameters::Default_named_parameters>

double CGAL::Polygon_mesh_processing::approximate_symmetric_Hausdorff_distance	(	const TriangleMesh &	tm1,
		const TriangleMesh &	tm2,
		const NamedParameters1 &	np1 = parameters::default_values(),
		const NamedParameters2 &	np2 = parameters::default_values()
	)

#include <CGAL/Polygon_mesh_processing/distance.h>

returns the approximate symmetric Hausdorff distance between tm1 and tm2, that is the maximum of approximate_Hausdorff_distance(tm1, tm2, np1, np2) and approximate_Hausdorff_distance(tm2, tm1, np2, np1).

See the function approximate_Hausdorff_distance() for a complete description of the parameters and requirements.

bounded_error_Hausdorff_distance()

template<class Concurrency_tag , class TriangleMesh1 , class TriangleMesh2 , class NamedParameters1 = parameters::Default_named_parameters, class NamedParameters2 = parameters::Default_named_parameters>

double CGAL::Polygon_mesh_processing::bounded_error_Hausdorff_distance	(	const TriangleMesh1 &	tm1,
		const TriangleMesh2 &	tm2,
		const double	error_bound = 0.0001,
		const NamedParameters1 &	np1 = parameters::default_values(),
		const NamedParameters2 &	np2 = parameters::default_values()
	)

#include <CGAL/Polygon_mesh_processing/distance.h>

returns an estimate on the Hausdorff distance between tm1 and tm2 that is at most error_bound away from the actual Hausdorff distance between the two given meshes.

Template Parameters

Concurrency_tag	enables sequential versus parallel algorithm. Possible values are Sequential_tag and Parallel_tag. Currently, the parallel version is not implemented and the sequential version is always used whatever tag is chosen!
TriangleMesh1	a model of the concept FaceListGraph
TriangleMesh2	a model of the concept FaceListGraph
NamedParameters	a sequence of Named Parameters

Parameters

tm1	a triangle mesh
tm2	another triangle mesh
error_bound	a maximum bound by which the Hausdorff distance estimate is allowed to deviate from the actual Hausdorff distance.
np1	an optional sequence of Named Parameters among the ones listed below
np2	an optional sequence of Named Parameters among the ones listed below

Optional Named Parameters

vertex_point_map a property map associating points to the vertices of tmX Type: a class model of ReadablePropertyMap with boost::graph_traits<TriangleMeshX>::vertex_descriptor as key type and Point_3 as value type Default: boost::get(CGAL::vertex_point, tmX) Extra: If this parameter is omitted, an internal property map for CGAL::vertex_point_t must be available in TriangleMeshX.
match_faces a boolean tag that turns on the preprocessing step that filters out all faces which belong to both meshes and hence do not contribute to the final distance Type: Boolean Default: true Extra: Both np1 and np2 must have this tag set to true in order to activate this preprocessing.

Precondition

tm1 and tm2 are non-empty triangle meshes.

Returns

the one-sided Hausdorff distance

bounded_error_symmetric_Hausdorff_distance()

template<class Concurrency_tag , class TriangleMesh1 , class TriangleMesh2 , class NamedParameters1 = parameters::Default_named_parameters, class NamedParameters2 = parameters::Default_named_parameters>

double CGAL::Polygon_mesh_processing::bounded_error_symmetric_Hausdorff_distance	(	const TriangleMesh1 &	tm1,
		const TriangleMesh2 &	tm2,
		const double	error_bound,
		const NamedParameters1 &	np1 = parameters::default_values(),
		const NamedParameters2 &	np2 = parameters::default_values()
	)

#include <CGAL/Polygon_mesh_processing/distance.h>

returns the the symmetric Hausdorff distance, that is the maximum of bounded_error_Hausdorff_distance(tm1, tm2, error_bound, np1, np2) and bounded_error_Hausdorff_distance(tm2, tm1, error_bound, np2, np1).

This function optimizes all internal calls to shared data structures in order to speed up the computation.

See the function CGAL::Polygon_mesh_processing::bounded_error_Hausdorff_distance() for a complete description of the parameters and requirements.

is_Hausdorff_distance_larger()

template<class Concurrency_tag , class TriangleMesh1 , class TriangleMesh2 , class NamedParameters1 = parameters::Default_named_parameters, class NamedParameters2 = parameters::Default_named_parameters>

bool CGAL::Polygon_mesh_processing::is_Hausdorff_distance_larger	(	const TriangleMesh1 &	tm1,
		const TriangleMesh2 &	tm2,
		const double	distance_bound,
		const double	error_bound,
		const NamedParameters1 &	np1 = parameters::default_values(),
		const NamedParameters2 &	np2 = parameters::default_values()
	)

#include <CGAL/Polygon_mesh_processing/distance.h>

returns true if the Hausdorff distance between two meshes is larger than the user-defined max distance, otherwise it returns false.

The distance used to compute the proximity of the meshes is the bounded-error Hausdorff distance. Instead of computing the full distance and checking it against the user-provided value, this function returns early if certain criteria show that the meshes do not satisfy the provided distance_bound.

See the function CGAL::Polygon_mesh_processing::bounded_error_Hausdorff_distance() for a complete description of the parameters and requirements. The following extra named parameter is available for np1:

Optional Named Parameters

use_one_sided_hausdorff a boolean tag indicating if the one-sided Hausdorff distance should be used. Type: Boolean Default: true Extra: If this tag is set to false, the symmetric Hausdorff distance is used.

max_distance_to_triangle_mesh()

template<class Concurrency_tag , class TriangleMesh , class PointRange , class NamedParameters = parameters::Default_named_parameters>

double CGAL::Polygon_mesh_processing::max_distance_to_triangle_mesh	(	const PointRange &	points,
		const TriangleMesh &	tm,
		const NamedParameters &	np = parameters::default_values()
	)

#include <CGAL/Polygon_mesh_processing/distance.h>

returns the distance to tm of the point from points that is the furthest from tm.

Template Parameters

PointRange	a range of Point_3, model of Range. Its iterator type is RandomAccessIterator.
TriangleMesh	a model of the concepts EdgeListGraph and FaceListGraph
NamedParameters	a sequence of Named Parameters

Parameters

points	the range of points of interest
tm	the triangle mesh to compute the distance to
np	an optional sequence of Named Parameters among the ones listed below

Optional Named Parameters

vertex_point_map a property map associating points to the vertices of tm Type: a class model of ReadablePropertyMap with boost::graph_traits<TriangleMesh>::vertex_descriptor as key type and Point_3 as value type Default: boost::get(CGAL::vertex_point, tm) Extra: If this parameter is omitted, an internal property map for CGAL::vertex_point_t must be available in TriangleMesh.
geom_traits an instance of a geometric traits class Type: a class model of PMPDistanceTraits Default: a CGAL Kernel deduced from the point type, using CGAL::Kernel_traits Extra: The geometric traits class must be compatible with the vertex point type.

Precondition

tm is a non-empty triangle mesh and points is not empty.

sample_triangle_mesh()

template<class PointOutputIterator , class TriangleMesh , class NamedParameters = parameters::Default_named_parameters>

PointOutputIterator CGAL::Polygon_mesh_processing::sample_triangle_mesh	(	const TriangleMesh &	tm,
		PointOutputIterator	out,
		const NamedParameters &	np = parameters::default_values()
	)

#include <CGAL/Polygon_mesh_processing/distance.h>

generates points on tm and outputs them to out; the sampling method is selected using named parameters.

Template Parameters

TriangleMesh	a model of the concepts EdgeListGraph and FaceListGraph
PointOutputIterator	a model of OutputIterator holding objects of the same point type as the value type of the point type associated to the mesh tm, i.e. the value type of the vertex point map property map, if provided, or the value type of the internal point property map otherwise
NamedParameters	a sequence of Named Parameters

Parameters

tm	the triangle mesh to be sampled
out	output iterator to be filled with sample points
np	an optional sequence of Named Parameters among the ones listed below

Optional Named Parameters

vertex_point_map a property map associating points to the vertices of tm Type: a class model of ReadablePropertyMap with boost::graph_traits<TriangleMesh>::vertex_descriptor as key type and Point_3 as value type Default: boost::get(CGAL::vertex_point, tm) Extra: If this parameter is omitted, an internal property map for CGAL::vertex_point_t must be available in TriangleMesh.
geom_traits an instance of a geometric traits class Type: a class model of PMPDistanceTraits Default: a CGAL Kernel deduced from the point type, using CGAL::Kernel_traits Extra: The geometric traits class must be compatible with the vertex point type.
random_seed a value to seed the random number generator Type: unsigned int Default: a value generated with std::time()
use_random_uniform_sampling If true is passed, points are generated uniformly at random on faces and/or edges of tm. If do_sample_faces is true, random points will be iteratively generated uniformly at random in the triangle of a face selected with probability proportional to its area. If do_sample_edges is true, random points will be iteratively generated uniformly at random in the segment of an edge selected with probability proportional to its length. Type: Boolean Type: true Extra: For faces, the number of sample points is the value passed to the named parameter number_of_points_on_faces. If not set, the value passed to the named parameter number_of_points_per_area_unit is multiplied by the area of tm to get the number of sample points. If none of these parameters is set, the number of points sampled is num_vertices(tm). For edges, the number of the number of sample points is the value passed to the named parameter number_of_points_on_edges. If not set, the value passed to the named parameter number_of_points_per_distance_unit is multiplied by the sum of the length of edges of tm to get the number of sample points. If none of these parameters is set, the number of points sampled is num_vertices(tm).
use_grid_sampling If true is passed, points are generated on a grid in each triangle, with a minimum of one point per triangle. Type: Boolean Default: false Extra: The distance between two consecutive points in the grid is that of the length of the smallest non-null edge of tm or the value passed to the named parameter grid_spacing. Edges are also split using the same distance, if requested.
use_monte_carlo_sampling if true is passed, points are generated randomly in each triangle and/or on each edge. Type: Boolean Default: false Extra: For faces, the number of points per triangle is the value passed to the named parameter number_of_points_per_face. If not set, the value passed to the named parameter number_of_points_per_area_unit is used to pick a number of points per face proportional to the triangle area with a minimum of one point per face. If none of these parameters is set, 2 divided by the square of the length of the smallest non-null edge of tm is used as if it was passed to number_of_points_per_area_unit. For edges, the number of points per edge is the value passed to the named parameter number_of_points_per_edge. If not set, the value passed to the named parameter number_of_points_per_distance_unit is used to pick a number of points per edge proportional to the length of the edge with a minimum of one point per face. If none of these parameters is set, 1 divided by the length of the smallest non-null edge of tm is used as if it was passed to number_of_points_per_distance_unit.
do_sample_vertices If true is passed, the vertices of tm are part of the sample. Type: Boolean Default: true
do_sample_edges If true is passed, edges of tm are sampled. Type: Boolean Default: true
do_sample_faces If true is passed, faces of tm are sampled. Type: Boolean Default: true
grid_spacing a value used as the grid spacing for the grid sampling method Type: double Default: the length of the shortest, non-degenerate edge of tm
number_of_points_on_edges a value used for the random sampling method as the number of points to pick exclusively on edges Type: unsigned int Default: num_vertices(tm) or a value based on nb_points_per_distance_unit, if it is defined
number_of_points_on_faces a value used for the random sampling method as the number of points to pick on the surface Type: unsigned int Default: num_vertices(tm) or a value based on nb_points_per_area_unit, if it is defined
number_of_points_per_distance_unit a value used for the random sampling and the Monte Carlo sampling methods to respectively determine the total number of points on edges and the number of points per edge Type: double Default: 1 divided by the length of the shortest, non-degenerate edge of tm
number_of_points_per_edge a value used by the Monte-Carlo sampling method as the number of points per edge to pick Type: unsigned int Default: 0
number_of_points_per_area_unit a value used for the random sampling and the Monte Carlo sampling methods to respectively determine the total number of points inside faces and the number of points per face Type: double Default: 2 divided by the squared length of the shortest, non-degenerate edge of tm
number_of_points_per_face a value used by the Monte-Carlo sampling method as the number of points per face to pick Type: unsigned int Default: 0

See also

CGAL::Polygon_mesh_processing::sample_triangle_soup()

sample_triangle_soup()

template<class PointOutputIterator , class TriangleRange , class PointRange , class NamedParameters = parameters::Default_named_parameters>

PointOutputIterator CGAL::Polygon_mesh_processing::sample_triangle_soup	(	const PointRange &	points,
		const TriangleRange &	triangles,
		PointOutputIterator	out,
		const NamedParameters &	np = parameters::default_values()
	)

#include <CGAL/Polygon_mesh_processing/distance.h>

generates points on a triangle soup and puts them to out; the sampling method is selected using named parameters.

Template Parameters

PointRange	a model of the concept RandomAccessContainer whose value type is the point type.
TriangleRange	a model of the concept RandomAccessContainer whose value_type is itself a model of the concept RandomAccessContainer whose value_type is an unsigned integral value.
PointOutputIterator	a model of OutputIterator holding objects of the same type as PointRange's value type
NamedParameters	a sequence of Named Parameters

Parameters

points	the points of the soup
triangles	a TriangleRange containing the triangles of the soup to be sampled
out	output iterator to be filled with sample points
np	an optional sequence of Named Parameters among the ones listed below

Optional Named Parameters

geom_traits an instance of a geometric traits class Type: a class model of PMPDistanceTraits Default: a CGAL Kernel deduced from the point type, using CGAL::Kernel_traits Extra: The geometric traits class must be compatible with the point range's point type.
random_seed a value to seed the random number generator Type: unsigned int Default: a value generated with std::time()
use_random_uniform_sampling If true is passed, points are generated in a random and uniform way over the triangles of the soup. Type: Boolean Type: true Extra: The number of sample points is the value passed to the named parameter number_of_points_on_faces. If not set, the value passed to the named parameter number_of_points_per_area_unit is multiplied by the area of the soup to get the number of sample points. If none of these parameters is set, the number of points sampled is points.size().
use_grid_sampling If true is passed, points are generated on a grid in each triangle, with a minimum of one point per triangle. Type: Boolean Default: false Extra: The distance between two consecutive points in the grid is that of the length of the smallest non-null edge of the soup or the value passed to the named parameter grid_spacing.
use_monte_carlo_sampling if true is passed, points are generated randomly in each triangle. Type: Boolean Default: false Extra: The number of points per triangle is the value passed to the named parameter number_of_points_per_face. If not set, the value passed to the named parameter number_of_points_per_area_unit is used to pick a number of points per face proportional to the triangle area with a minimum of one point per face. If none of these parameters is set, the number of points per area unit is set to 2 divided by the square of the length of the smallest non-null edge of the soup.
do_sample_vertices If true is passed, the points of points are part of the sample. Type: Boolean Default: true
do_sample_faces If true is passed, faces of the soup are sampled. Type: Boolean Default: true
grid_spacing a value used as the grid spacing for the grid sampling method Type: double Default: the length of the shortest, non-degenerate edge of the soup
number_of_points_on_faces a value used for the random sampling method as the number of points to pick on the surface Type: unsigned int Default: points.size() or a value based on nb_points_per_area_unit, if it is defined
number_of_points_per_face a value used by the Monte-Carlo sampling method as the number of points per face to pick Type: unsigned int Default: 0
number_of_points_per_area_unit a value used for the random sampling and the Monte Carlo sampling methods to respectively determine the total number of points inside faces and the number of points per face Type: double Default: 2 divided by the squared length of the shortest, non-degenerate edge of the soup

Attention

Contrary to sample_triangle_mesh(), this method does not allow to sample edges.

See also

CGAL::Polygon_mesh_processing::sample_triangle_mesh()