CGAL::linear_least_squares_fitting_3

Definition

Function linear_least_squares_fitting_3 computes the best fitting 3D line or plane (in the least squares sense) of a set of 3D objects such as points, segments, triangles, spheres, balls, cuboids or tetrahedra.

The best fitting linear sub-space (here line or plane) minimizes the sum of squared distances from all points comprising these objects to their orthogonal projections onto this linear subspace. It can be shown that the best line or plane goes through the centroid of the set. This problem is equivalent to search for the linear sub-space which maximizes the variance of projected points (sum of squared distances to the centroid). Internally we solve this problem by eigen decomposition of the covariance matrix of the whole set. Note that the 3 × 3 covariance matrix is computed internally in closed form and not by point sampling the objects. Eigenvectors corresponding to large eigenvalues are the directions in which the data has strong component, or equivalently large variance.

The fitting quality property is characterized by the values of the three eigenvalues. When all three values are distinct the best linear subspace is uniquely determined, be it a line or a plane. When all three eigenvalues are equal there is no preferable sub-space and any line or plane going through the centroid share the same fitting property (a horizontal plane or a line along the x axis are returned by default). A best fitting line is uniquely determined as soon as the largest eigenvalue is different from the two others, otherwise all lines contained in the best fitting plane share the same fitting property. A best fitting plane is uniquely determined as soon as the smallest eigenvalue is different from the two others, otherwise all planes going through the best fitting line share the same fitting property.

#include <CGAL/linear_least_squares_fitting_3.h>

The class K is the kernel in which the type InputIterator::value_type is defined. It can be omitted and deduced automatically from the value type.

The tag tag identifies the dimension to be considered from the objects. For point sets it should be 0. For segment sets it could be 1 or 0 according to whether one wants to fit the entire segments or just the end points. For triangle sets it can range from 0 to 2 according to whether one wants to fit either the corner points, the segments or the whole triangles. For cuboid sets it can range from 0 to 3 according to whether one wants to fit either the corners, the segments, the faces or the whole solid cuboids. For sphere sets it can be 2 or 3 according to whether one wants to fit either the surface of the spheres or the whole solid balls. For tetrahedron sets it can range from 0 to 3 according to whether one wants to fit either the points, the segments, the surface triangles or the whole solid tetrahedra.

Requirements

1. InputIterator::value_type can be either K::Point_3, K::Segment_3, Triangle_3, Cuboid_3, Sphere_3 or Tetrahedron_3.
2. line is the best fitting line computed.
3. centroid is the centroid computed. This parameter is optional and can be omitted.
4. tag is the tag identifying the dimension to be considered from the objects. It should range from Dimension_tag<0> to Dimension_tag<3>. Also, it should not be of a dimension greater nor smaller than the geometry of the object. For example, a Triangle can not have a Dimension_tag<3> tag. A Segment can not have a Dimension_tag<2> nor a Dimension_tag<3> tag. A Sphere can not have a Dimension_tag<0> nor a Dimension_tag<1> tag.

The class K is the kernel in which the type InputIterator::value_type is defined. It can be omitted and deduced automatically from the value type. The tag tag identifies the dimension to be considered from the objects (see above).

Requirements

1. InputIterator::value_type can either be K::Point_3, K::Segment_3, Triangle_3, Cuboid_3, Sphere_3 or Tetrahedron_3.
2. plane is the best fitting plane computed.
3. centroid is the centroid computed. This parameter is optional and can be omitted.
4. tag is the tag identifying the dimension to be considered from the objects. It should range from Dimension_tag<0> to Dimension_tag<3>. Also, it should not be of a dimension greater nor smaller than the geometry of the object. For example, a Triangle can not have a Dimension_tag<3> tag. A Segment can not have a Dimension_tag<2> nor a Dimension_tag<3> tag. A Sphere can not have a Dimension_tag<0> nor a Dimension_tag<1> tag.