\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)
CGAL 4.5 - Principal Component Analysis
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
CGAL::linear_least_square_fitting_3()
Principal Component Analysis Reference

template<typename InputIterator , typename K , typename Tag >
K::FT CGAL::linear_least_squares_fitting_3 (InputIterator first, InputIterator beyond, typename K::Line_3 &line, typename K::Point_3 &centroid, const Tag &tag, const K &k)
 The 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, iso cuboids or tetrahedra. More...
 
template<typename InputIterator , typename K , typename Tag >
K::FT CGAL::linear_least_squares_fitting_3 (InputIterator first, InputIterator beyond, typename K::Plane_3 &plane, typename K::Point_3 &centroid, const Tag &tag, const K &k)
 computes the best fitting 3D plane of a 3D object set in the range [first,beyond). More...
 

Function Documentation

template<typename InputIterator , typename K , typename Tag >
K::FT CGAL::linear_least_squares_fitting_3 ( InputIterator  first,
InputIterator  beyond,
typename K::Line_3 &  line,
typename K::Point_3 &  centroid,
const Tag &  tag,
const K &  k 
)

The 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, iso 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 \times 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.

computes the best fitting 3D line of a 3D object set in the range [first,beyond). The value returned is a fitting quality between \( 0\) and \( 1\), where \( 0\) means that the variance is the same along any line contained within the best fitting plane, and \( 1\) means that the variance is null orthogonally to the best fitting line (hence the fit is perfect).

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

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

Requirements

  1. InputIterator must have a value type equivalent to K::Point_3, K::Segment_3, K::Triangle_3, K::Iso_cuboid_3, K::Sphere_3 or K::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.

#include <CGAL/linear_least_squares_fitting_3.h>

Examples:
Principal_component_analysis/linear_least_squares_fitting_triangles_3.cpp.
template<typename InputIterator , typename K , typename Tag >
K::FT CGAL::linear_least_squares_fitting_3 ( InputIterator  first,
InputIterator  beyond,
typename K::Plane_3 &  plane,
typename K::Point_3 &  centroid,
const Tag &  tag,
const K &  k 
)

computes the best fitting 3D plane of a 3D object set in the range [first,beyond).

The value returned is a fitting quality between \( 0\) and \( 1\), where \( 0\) means that the variance is the same along any plane going through the best fitting line, and \( 1\) means that the variance is null orthogonally to the best fitting plane (hence the fit is perfect).

The class K is the kernel in which the value type of InputIterator 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 has a value type equivalent to K::Point_3, K::Segment_3, K::Triangle_3, K::Iso_cuboid_3, K::Sphere_3 or K::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.

#include <CGAL/linear_least_squares_fitting_3.h>