DGtal::AffineGeometry< TPoint > Struct Template Reference

Aim: Utility class to determine the affine geometry of an input set of points. It provides exact results when the input is composed of lattice points, and may determine a basis, the dimension, or an orthogonal vector. More...

#include <DGtal/geometry/tools/AffineGeometry.h>

Public Types
typedef TPoint	Point
typedef Point::Coordinate	Scalar
typedef Point::Container	Container
typedef std::size_t	Size
typedef std::vector< Point >	Points
	type for range of points.
typedef std::vector< Size >	Sizes
	type for range of sizes.
typedef DGtal::detail::AffineGeometryPointOperations< dimension, Scalar, Container >	PointOps
typedef DGtal::detail::AffineGeometryScalarOperations< Scalar >	ScalarOps

Static Public Member Functions
static affine services
template<typename TInputPoint >
static DGtal::int64_t	affineDimension (const std::vector< TInputPoint > &X, const double tolerance=1e-12)
template<typename TInputPoint >
static std::vector< Size >	affineSubset (const std::vector< TInputPoint > &X, const double tolerance=1e-12)
template<typename TInputPoint , typename TIndexRange >
static std::vector< Size >	affineSubset (const std::vector< TInputPoint > &X, const TIndexRange &I, const double tolerance=1e-12)
template<typename TInputPoint >
static std::pair< Point, Points >	affineBasis (const std::vector< TInputPoint > &X, const double tolerance=1e-12)
template<typename TInputPoint , typename TIndexRange >
static std::pair< TInputPoint, Points >	affineBasis (const std::vector< TInputPoint > &X, const TIndexRange &I, const double tolerance=1e-12)
static Point	independentVector (const Points &basis, const double tolerance=1e-12)
template<typename TOtherPoint >
static TOtherPoint	independentVector (const Points &basis, const double tolerance=1e-12)
static void	completeBasis (Points &basis, bool normal_vector, const double tolerance=1e-12)
template<typename TInputPoint >
static std::vector< Point >	orthogonalLatticeBasis (const TInputPoint &N, bool shortened=false)
static specific services
(Used internally)
static Point	reductionOnBasis (const Point &v, const Points &basis, const double tolerance)
static bool	addIfIndependent (Points &basis, const Point &v, const double tolerance)
static std::pair< Scalar, Scalar >	reduceVector (Point &w, const Point &b, const double tolerance)
static std::pair< Scalar, Scalar >	reduceVector (Point &w, const Point &b, Dimension start, const double tolerance)
static const Point &	transform (const Point &w)
template<typename TInputPoint >
static Point	transform (const TInputPoint &w)
static Point	orthogonalVector (const Points &basis)
template<typename TInternalNumber >
static Point	orthogonalVector (const Points &basis)
static Point	simplifiedVector (Point v)

Static Public Attributes
static const Size	dimension = Point::dimension

Detailed Description

template<typename TPoint>
struct DGtal::AffineGeometry< TPoint >

Aim: Utility class to determine the affine geometry of an input set of points. It provides exact results when the input is composed of lattice points, and may determine a basis, the dimension, or an orthogonal vector.

Description of template class 'AffineGeometry'

Note

Useful for algorithms that requires the exact dimensionality of a set of points before processing, like QuickHull.

Warning

You can use this class to test the dimensionality of a set of points with floating point coordinates, but this approach is less robust than singular value decomposition.

Template Parameters

TPoint

the type for points, which may be lattice points or points with floating-point coordinates.

#include <iostream>
#include <vector>
#include "DGtal/base/Common.h"
#include "DGtal/kernel/SpaceND.h"
#include "DGtal/geometry/tools/AffineGeometry.h"
...
typedef SpaceND< 3, int >                Space;      
typedef Space::Point                     Point;
typedef AffineGeometry< Point >          Affine;
std::vector<Point> X = { Point{1, 0, 0}, Point{2, 1, 0}, Point{3, 2, 0}, Point{3, 1, 1}, Point{5, 2, 2}, Point{4, 2, 1} };
auto I = Affine::affineSubset( X ); 
auto B = Affine::affineBasis( X ); 
auto d = Affine::affineDimension( X ); 

See also

testAffineGeometry.cpp

Definition at line 453 of file AffineGeometry.h.

Member Typedef Documentation

Container

template<typename TPoint >

typedef Point::Container DGtal::AffineGeometry< TPoint >::Container

Definition at line 457 of file AffineGeometry.h.

Point

template<typename TPoint >

typedef TPoint DGtal::AffineGeometry< TPoint >::Point

Definition at line 455 of file AffineGeometry.h.

PointOps

template<typename TPoint >

typedef DGtal::detail::AffineGeometryPointOperations< dimension, Scalar, Container > DGtal::AffineGeometry< TPoint >::PointOps

Definition at line 463 of file AffineGeometry.h.

Points

template<typename TPoint >

typedef std::vector< Point > DGtal::AffineGeometry< TPoint >::Points

type for range of points.

Definition at line 459 of file AffineGeometry.h.

Scalar

template<typename TPoint >

typedef Point::Coordinate DGtal::AffineGeometry< TPoint >::Scalar

Definition at line 456 of file AffineGeometry.h.

ScalarOps

template<typename TPoint >

typedef DGtal::detail::AffineGeometryScalarOperations< Scalar > DGtal::AffineGeometry< TPoint >::ScalarOps

Definition at line 464 of file AffineGeometry.h.

Size

template<typename TPoint >

typedef std::size_t DGtal::AffineGeometry< TPoint >::Size

Definition at line 458 of file AffineGeometry.h.

Sizes

template<typename TPoint >

typedef std::vector< Size > DGtal::AffineGeometry< TPoint >::Sizes

type for range of sizes.

Definition at line 460 of file AffineGeometry.h.

Member Function Documentation

addIfIndependent()

template<typename TPoint >

static bool DGtal::AffineGeometry< TPoint >::addIfIndependent ( Points &  basis, const Point &  v, const double  tolerance  )

inlinestatic

Checks if the vector v can be decomposed as a linear combination of the vectors of the basis. If yes, returns 'false', otherwise returns 'true' and adds the obtained reduced vector to the basis after normalizing it.

Parameters

[in,out]	basis	a range of vectors forming a (partial or not) basis of the space.
[in]	v	any vector.
[in]	tolerance	the accepted oo-norm below which the vector is null (used only for points with float/double coordinates).

Returns

'true' iff the vector v was not a linear combination of the vectors of the basis and the basis is then enriched by the direction indicated by v, otherwise returns 'false'.

Note

If the points have integer coordinates, the normalization of the new basis vector is its reduction by its gcd, otherwise the vector has unit L2-norm.

Definition at line 834 of file AffineGeometry.h.

    {
      Point  w = reductionOnBasis( v, basis, tolerance );
      Scalar x;
      functions::getSquaredNormL2( x, w );
      if ( ScalarOps::isNonZero( x, tolerance ) )
        {
          // Useful to reduce the norm of vectors for lattice vectors
          // and necessary for real vectors so that `tolerance` keeps
          // the same meaning.
          PointOps::normalizeVector( w, x ); 
          basis.push_back( w );
          return true;
        }
      return false;
    }

References DGtal::functions::getSquaredNormL2(), DGtal::detail::AffineGeometryScalarOperations< TScalar >::isNonZero(), DGtal::detail::AffineGeometryPointOperations< dim, TEuclideanRing, TContainer >::normalizeVector(), and DGtal::AffineGeometry< TPoint >::reductionOnBasis().

Referenced by DGtal::AffineGeometry< TPoint >::affineBasis(), DGtal::AffineGeometry< TPoint >::affineBasis(), DGtal::AffineGeometry< TPoint >::affineSubset(), and DGtal::AffineGeometry< TPoint >::affineSubset().

affineBasis() [1/2]

template<typename TPoint >

template<typename TInputPoint >

static std::pair< Point, Points > DGtal::AffineGeometry< TPoint >::affineBasis ( const std::vector< TInputPoint > &  X, const double  tolerance = 1e-12  )

inlinestatic

Given a range of points X, returns a point and a range of vectors forming an affine basis containing X.

Template Parameters

TInputPoint

the type of input points (may be less precise).

Parameters

[in]	X	the range of input points (may be lattice points or not).
[in]	tolerance	the accepted oo-norm below which the vector is null (used only for points with float/double coordinates).

Returns

a point and a range of vectors forming an affine basis containing X.

Note

Complexity is O( m n^2 ), where m=Cardinal(X) and n=dimension.

Definition at line 589 of file AffineGeometry.h.

    {
      Points basis;  //< direction vectors
      Size m = X.size();
      // Process trivial cases.
      if ( m == 0 ) return std::make_pair( Point::zero, basis );
      const Point o = transform( X[ 0 ] );
      if ( m == 1 ) return std::make_pair( o, basis );
      // Process general case.
      basis.reserve( dimension );
      for ( Size i = 1; i < m; i++ )
        {
          Point v = transform( X[ i ] ) - o;
          if ( addIfIndependent( basis, v, tolerance ) )
            if ( basis.size() >= dimension ) break;
        }
      return std::make_pair( o, basis );
    }

References DGtal::AffineGeometry< TPoint >::addIfIndependent(), DGtal::AffineGeometry< TPoint >::dimension, and DGtal::AffineGeometry< TPoint >::transform().

Referenced by DGtal::functions::getAffineBasis(), DGtal::functions::getAffineBasis(), and DGtal::AffineBasis< TPoint >::reduce().

affineBasis() [2/2]

template<typename TPoint >

template<typename TInputPoint , typename TIndexRange >

static std::pair< TInputPoint, Points > DGtal::AffineGeometry< TPoint >::affineBasis ( const std::vector< TInputPoint > &  X, const TIndexRange &  I, const double  tolerance = 1e-12  )

inlinestatic

Given a range of points X and a range of indices I describing its subset of interest, returns a point and a range of vectors forming an affine basis containing the subset X[I].

Template Parameters

TInputPoint

the type of input points (may be less precise).

Parameters

[in]	X	the range of input points (may be lattice points or not).
[in]	I	the range of indices within X that specifies the subset of interest.
[in]	tolerance	the accepted oo-norm below which the vector is null (used only for points with float/double coordinates).

Returns

a point and a range of vectors forming an affine basis containing X[I].

Note

Complexity is O( m n^2 ), where m=Cardinal(I) and n=dimension.

Definition at line 627 of file AffineGeometry.h.

    {
      Points basis;  //< direction vectors
      Size m = I.size();
      // Process trivial cases.
      if ( m == 0 ) return std::make_pair( TInputPoint::zero, basis );
      if ( m == 1 ) return std::make_pair( X[ I[ 0 ] ], basis );
      // Process general case.
      const Point  o = transform( X[ I[ 0 ] ] );
      basis.reserve( dimension );
      for ( Size i = 1; i < m; i++ )
        {
          Point v = transform( X[ I[ i ] ] ) - o;
          if ( addIfIndependent( basis, v, tolerance ) )
            if ( basis.size() > dimension ) break;
        }
      return std::make_pair( X[ I[ 0 ] ], basis );
    }

References DGtal::AffineGeometry< TPoint >::addIfIndependent(), DGtal::AffineGeometry< TPoint >::dimension, and DGtal::AffineGeometry< TPoint >::transform().

affineDimension()

template<typename TPoint >

template<typename TInputPoint >

static DGtal::int64_t DGtal::AffineGeometry< TPoint >::affineDimension ( const std::vector< TInputPoint > &  X, const double  tolerance = 1e-12  )

inlinestatic

Given a range of points X, returns the affine dimension of its spanned affine subspace.

Template Parameters

TInputPoint

the type of input points (may be less precise).

Parameters

[in]	X	the range of input points (may be lattice points or not).
[in]	tolerance	the accepted oo-norm below which the vector is null (used only for points with float/double coordinates).

Returns

the affine dimension of X (-1 is empty set, 0 is a point, 1 is a line, etc)

Definition at line 486 of file AffineGeometry.h.

    {
      return DGtal::int64_t( affineSubset( X, tolerance ).size() ) - 1;
    }

References DGtal::AffineGeometry< TPoint >::affineSubset().

Referenced by DGtal::functions::computeAffineDimension(), and SCENARIO().

affineSubset() [1/2]

template<typename TPoint >

template<typename TInputPoint >

static std::vector< Size > DGtal::AffineGeometry< TPoint >::affineSubset ( const std::vector< TInputPoint > &  X, const double  tolerance = 1e-12  )

inlinestatic

Given a range of points X, returns a subset of these points that form an affine basis of X. Equivalently it is a simplex whose affine space spans all the points of X.

Template Parameters

TInputPoint

the type of input points (may be less precise).

Parameters

[in]	X	the range of input points (may be lattice points or not).
[in]	tolerance	the accepted oo-norm below which the vector is null (used only for points with float/double coordinates).

Returns

a subset of these points as a range of indices.

Note

Complexity is \(O( m n^2 )\), where m=Cardinal(X) and n=dimension.

Definition at line 508 of file AffineGeometry.h.

    {
      Size m = X.size();
      // Process trivial cases.
      if ( m == 0 ) return { };
      if ( m == 1 ) return { Size( 0 ) };
      // Process general case.
      Points basis;  //< direction vectors
      Sizes  chosen; //< selected points
      chosen.push_back( 0 ); //< reference point (first one, as it may be any one)
      for ( Size i = 1; i < m; i++ )
        {
          Point v = transform( X[ i ] - X[ 0 ] );
          if ( addIfIndependent( basis, v, tolerance ) )
            chosen.push_back( i );
          if ( chosen.size() > dimension ) break;
        }
      return chosen;
    }

References DGtal::AffineGeometry< TPoint >::addIfIndependent(), DGtal::AffineGeometry< TPoint >::dimension, and DGtal::AffineGeometry< TPoint >::transform().

Referenced by DGtal::AffineGeometry< TPoint >::affineDimension(), DGtal::functions::computeAffineSubset(), DGtal::functions::computeAffineSubset(), DGtal::functions::getOrthogonalVector(), and DGtal::QuickHull< TKernel >::pickInitialSimplex().

affineSubset() [2/2]

template<typename TPoint >

template<typename TInputPoint , typename TIndexRange >

static std::vector< Size > DGtal::AffineGeometry< TPoint >::affineSubset ( const std::vector< TInputPoint > &  X, const TIndexRange &  I, const double  tolerance = 1e-12  )

inlinestatic

Given a range of points X and a subset of it given by indices I, returns a subset of these points that form an affine basis of X[I]. Equivalently it is a simplex whose affine space spans all the points of X[I].

Template Parameters

TInputPoint	the type of input points (may be less precise).
TIndexRange	any type of range of indices that specifies the subset of points of interest.

Parameters

[in]	X	the range of input points (may be lattice points or not).
[in]	I	the range of indices specifying the subset of interest.
[in]	tolerance	the accepted oo-norm below which the vector is null (used only for points with float/double coordinates).

Returns

a subset of these points as a range of indices.

Note

Complexity is \(O( m n^2 )\), where m=Cardinal(X) and n=dimension.

Definition at line 551 of file AffineGeometry.h.

    {
      Size m = I.size();
      // Process trivial cases.
      if ( m == 0 ) return { };
      if ( m == 1 ) return { I[ 0 ] };
      // Process general case.
      Points basis;  //< direction vectors
      Sizes  chosen; //< selected points
      chosen.push_back( I[ 0 ] ); //< reference point (first one, as it may be any one)
      for ( Size i = 1; i < m; i++ )
        {
          Point v = transform( X[ I[ i ] ] - X[ I[ 0 ] ] );
          if ( addIfIndependent( basis, v, tolerance ) )
            chosen.push_back( I[ i ] );
          if ( chosen.size() > dimension ) break;
        }
      return chosen;
    }

References DGtal::AffineGeometry< TPoint >::addIfIndependent(), DGtal::AffineGeometry< TPoint >::dimension, and DGtal::AffineGeometry< TPoint >::transform().

completeBasis()

template<typename TPoint >

static void DGtal::AffineGeometry< TPoint >::completeBasis ( Points &  basis, bool  normal_vector, const double  tolerance = 1e-12  )

inlinestatic

Complete the vectors basis with independent vectors so as to form a basis of the space. When normal_vector is true, the last added vector is guaranteed to be orthogonal to all the previous vectors.

Note

In 3D, given two independent vectors as input, then the added vector is the cross product of these two vectors. In nD, it is thus a generalization of the cross product.

Parameters

[in,out]	basis	a range of independent vectors of size less than dimension.
[in]	normal_vector	when 'true', the last vector of the basis is orthogonal to all the other vectors of the basis, otherwise it is just an independent canonic vector.
[in]	tolerance	the accepted oo-norm below which the vector is null (used only for points with float/double coordinates).

Definition at line 737 of file AffineGeometry.h.

    {
      if ( basis.size() >= dimension ) return;
      while ( ( basis.size() + 1 ) < dimension )
        { // add an independent vector
          const Point u = independentVector( basis, tolerance );
          basis.push_back( u );
        }
      if ( normal_vector )
        basis.push_back( orthogonalVector( basis ) );
      else
        basis.push_back( independentVector( basis, tolerance ) );
    }

References DGtal::AffineGeometry< TPoint >::dimension, DGtal::AffineGeometry< TPoint >::independentVector(), and DGtal::AffineGeometry< TPoint >::orthogonalVector().

Referenced by DGtal::functions::getCompleteBasis().

independentVector() [1/2]

template<typename TPoint >

static Point DGtal::AffineGeometry< TPoint >::independentVector ( const Points &  basis, const double  tolerance = 1e-12  )

inlinestatic

Given a partial basis of vectors, returns a new vector that is independent.

Parameters

[in]	basis	a range of independent vectors that defines a partial basis of the space.
[in]	tolerance	the accepted oo-norm below which the vector is null (used only for points with float/double coordinates).

Returns

a canonic unit vector independent of all vectors of basis, or the null vector if the basis was not partial.

Definition at line 660 of file AffineGeometry.h.

    {
      // If basis has already d independent vectors, then there is no
      // other independent vector.
      if ( basis.size() >= dimension ) return Point::zero;
      // At least one trivial canonic vector should be independant.
      Dimension k = 0;
      for ( ; k < dimension; k++ )
        {
          Point e_k = Point::base( k );
          Point w   = reductionOnBasis( e_k, basis, tolerance );
          Scalar sql2;
          functions::getSquaredNormL2( sql2, w );
          if ( ScalarOps::isNonZero( sql2, tolerance ) )
            return e_k;
        }
      trace.error() << "[AffineGeometry::independentVector]"
                    << " Unable to find independent vector." << std::endl;
      return Point::zero;
    }

References DGtal::AffineGeometry< TPoint >::dimension, DGtal::Trace::error(), DGtal::functions::getSquaredNormL2(), DGtal::detail::AffineGeometryScalarOperations< TScalar >::isNonZero(), DGtal::AffineGeometry< TPoint >::reductionOnBasis(), and DGtal::trace.

Referenced by DGtal::AffineGeometry< TPoint >::completeBasis(), and DGtal::functions::computeIndependentVector().

independentVector() [2/2]

template<typename TPoint >

template<typename TOtherPoint >

static TOtherPoint DGtal::AffineGeometry< TPoint >::independentVector ( const Points &  basis, const double  tolerance = 1e-12  )

inlinestatic

Given a partial basis of vectors, returns a new vector that is independent.

Template Parameters

TOtherPoint

any type of point

Parameters

[in]	basis	a range of independent vectors that defines a partial basis of the space.
[in]	tolerance	the accepted oo-norm below which the vector is null (used only for points with float/double coordinates).

Returns

a canonic unit vector independent of all vectors of basis, or the null vector if the basis was not partial.

Definition at line 696 of file AffineGeometry.h.

    {
      // If basis has already d independent vectors, then there is no
      // other independent vector.
      if ( basis.size() >= dimension ) return TOtherPoint::zero;
      // At least one trivial canonic vector should be independant.
      Dimension k = 0;
      for ( ; k < dimension; k++ )
        {
          Point e_k = Point::base( k );
          Point w   = reductionOnBasis( e_k, basis, tolerance );
          Scalar sql2;
          functions::getSquaredNormL2( sql2, w );
          if ( ScalarOps::isNonZero( sql2, tolerance ) )
            return TOtherPoint::base( k ); 
        }
      trace.error() << "[AffineGeometry::independentVector]"
                    << " Unable to find independent vector." << std::endl;
      return TOtherPoint::zero;
    }

References DGtal::AffineGeometry< TPoint >::dimension, DGtal::Trace::error(), DGtal::functions::getSquaredNormL2(), DGtal::detail::AffineGeometryScalarOperations< TScalar >::isNonZero(), DGtal::AffineGeometry< TPoint >::reductionOnBasis(), and DGtal::trace.

orthogonalLatticeBasis()

template<typename TPoint >

template<typename TInputPoint >

static std::vector< Point > DGtal::AffineGeometry< TPoint >::orthogonalLatticeBasis ( const TInputPoint &  N, bool  shortened = false  )

inlinestatic

Given a primitive lattice vector N, returns a possible basis for its orthogonal d-1 dimensional lattice.

Template Parameters

TOtherPoint

any type of lattice point

Parameters

[in]	N	a non null primitive lattice vector
[in]	shortened	when 'false', the basis is in row echelon form, when 'true', the basis is shortened (with pairwise shortenings, may not be optimal, except in 3D).

Returns

the d-1 vectors forming a basis of the orthogonal lattice to N.

Definition at line 768 of file AffineGeometry.h.

    {
      std::vector< Scalar > Np( N.begin(), N.end() );
      Np.resize( Point::dimension );
      auto B = functions::computeOrthogonalLattice( Np );
      if ( shortened )
        functions::shortenBasis( B );
      std::vector< Point > R( B.size() );
      for ( std::size_t i = 0; i < B.size(); i++ )
        for ( std::size_t j = 0; j < Point::dimension; j++ )
          R[ i ][ j ] = B[ i ][ j ];
      return R;
    }

References DGtal::functions::computeOrthogonalLattice(), DGtal::R, and DGtal::functions::shortenBasis().

Referenced by DGtal::AffineBasis< TPoint >::AffineBasis(), and DGtal::functions::getOrthogonalLatticeBasis().

orthogonalVector() [1/2]

template<typename TPoint >

static Point DGtal::AffineGeometry< TPoint >::orthogonalVector ( const Points &  basis )

inlinestatic

Given d-1 independent vectors in dD, returns a vector that is orthogonal to each of them.

Note

In 3D, given two independent vectors as input, then the added vector is the (reduced) cross product of these two vectors. In nD, it is thus a kind of generalization of the cross product.

Parameters

[in]

basis

a range of independent vectors of size dimension-1.

Returns

a vector of coefficients (represented with the given number type), or the null vector if the basis is not d-1-dimensional.

Definition at line 962 of file AffineGeometry.h.

    {
      Point w;
      const std::size_t n = dimension;
      if ( ( basis.size() + 1 ) != dimension ) return w;
      const std::size_t m = basis.size();
      SimpleMatrix< Scalar, dimension-1, dimension> A;
      for ( std::size_t i = 0; i < m; ++i )
        for ( std::size_t j = 0; j < n; ++j )
          A( i, j ) = basis[ i ][ j ];
      for ( std::size_t col = 0; col < n; ++col)
        { // construct sub-matrix removing column col
          SimpleMatrix< Scalar, dimension-1, dimension-1> M;
          for ( std::size_t i = 0; i < m; ++i )
            {
              std::size_t c = 0;
              for ( std::size_t j = 0; j < n; ++j)
                if ( j != col ) M( i, c++ ) = A( i, j );
            }
          functions::getDeterminantBareiss( w[ col ], M );
          if ( (col+dimension) % 2 == 0 ) w[ col ] = -w[ col ];
        }
      return simplifiedVector( w );
    }

References DGtal::AffineGeometry< TPoint >::dimension, DGtal::functions::getDeterminantBareiss(), and DGtal::AffineGeometry< TPoint >::simplifiedVector().

Referenced by DGtal::AffineGeometry< TPoint >::completeBasis(), and DGtal::functions::computeOrthogonalVectorToBasis().

orthogonalVector() [2/2]

template<typename TPoint >

template<typename TInternalNumber >

static Point DGtal::AffineGeometry< TPoint >::orthogonalVector ( const Points &  basis )

inlinestatic

Given d-1 independent vectors in dD, returns a vector that is orthogonal to each of them.

Note

In 3D, given two independent vectors as input, then the added vector is the (reduced) cross product of these two vectors. In nD, it is thus a kind of generalization of the cross product.

Parameters

[in]

basis

a range of independent vectors of size dimension-1.

Returns

a vector of coefficients (represented with the given number type), or the null vector if the basis is not d-1-dimensional.

Definition at line 1002 of file AffineGeometry.h.

    {
      Point w;
      typedef  PointVector< dimension, TInternalNumber > InternalPoint;
      InternalPoint W;
      const std::size_t n = dimension;
      if ( ( basis.size() + 1 ) != dimension ) return w;
      const std::size_t m = basis.size();
      SimpleMatrix< Scalar, dimension-1, dimension> A;
      for ( std::size_t i = 0; i < m; ++i )
        for ( std::size_t j = 0; j < n; ++j )
          A( i, j ) = basis[ i ][ j ];
      for ( std::size_t col = 0; col < n; ++col)
        { // construct sub-matrix removing column col
          SimpleMatrix< Scalar, dimension-1, dimension-1> M;
          for ( std::size_t i = 0; i < m; ++i )
            {
              std::size_t c = 0;
              for ( std::size_t j = 0; j < n; ++j)
                if ( j != col ) M( i, c++ ) = A( i, j );
            }
          functions::getDeterminantBareiss( W[ col ], M );
          if ( (col+dimension) % 2 == 0 ) W[ col ] = -W[ col ];
        }
      W = AffineGeometry<InternalPoint>::simplifiedVector( W );
      return transform( W );
    }

References DGtal::AffineGeometry< TPoint >::dimension, DGtal::functions::getDeterminantBareiss(), DGtal::AffineGeometry< TPoint >::simplifiedVector(), DGtal::PointVector< dim, TEuclideanRing, TContainer >::size(), and DGtal::AffineGeometry< TPoint >::transform().

reduceVector() [1/2]

template<typename TPoint >

static std::pair< Scalar, Scalar > DGtal::AffineGeometry< TPoint >::reduceVector ( Point &  w, const Point &  b, const double  tolerance  )

inlinestatic

Reduces vector w by the vector b

Parameters

[in,out]	w	any vector
[in]	b	a non-null vector of the current basis.
[in]	tolerance	the accepted oo-norm below which the vector is null (used only for points with float/double coordinates).

Returns

the coefficients (alpha,beta) for reduction such that alpha * w - beta * b is the returned reduced vector, alpha >= 0.

Note

This reduction is an elementary Gauss elimination.

Definition at line 867 of file AffineGeometry.h.

    {
      Scalar mul_w = 0;
      Scalar mul_b = 0;
      Size n = w.size();
      // Find index of first non null pivot in b.
      Size lead = n;
      for ( Size j = 0; j < n; j++)
        if ( ScalarOps::isNonZero( b[j], tolerance ) ) { lead = j; break; }
      if ( lead == n ) return std::make_pair( mul_w, mul_b ); // b is null vector
 
      std::tie( mul_w, mul_b ) = ScalarOps::getMultipliers( w[ lead ], b[ lead ] );
      
      for (Size j = 0; j < n; j++) 
        w[j] = mul_w * w[j] - mul_b * b[j];
      return std::make_pair( mul_w, mul_b );
    }

References DGtal::detail::AffineGeometryScalarOperations< TScalar >::getMultipliers(), and DGtal::detail::AffineGeometryScalarOperations< TScalar >::isNonZero().

Referenced by DGtal::AffineBasis< TPoint >::decomposeVector(), DGtal::AffineBasis< TPoint >::reduceAsEchelon(), and DGtal::AffineGeometry< TPoint >::reductionOnBasis().

reduceVector() [2/2]

template<typename TPoint >

static std::pair< Scalar, Scalar > DGtal::AffineGeometry< TPoint >::reduceVector ( Point &  w, const Point &  b, Dimension  start, const double  tolerance  )

inlinestatic

Reduces vector w by the vector b

Parameters

[in,out]	w	any vector
[in]	b	a non-null vector of the current basis.
[in]	start	the starting component index.
[in]	tolerance	the accepted oo-norm below which the vector is null (used only for points with float/double coordinates).

Returns

the coefficients (alpha,beta) for reduction such that alpha * w - beta * b is the returned reduced vector, alpha >= 0.

Note

This reduction is an elementary Gauss elimination.

Definition at line 900 of file AffineGeometry.h.

    {
      Scalar mul_w = 0;
      Scalar mul_b = 0;
      Size n = w.size();
      // Find index of first non null pivot in b.
      Size lead = n;
      for ( Size j = start; j < n; j++)
        if ( ScalarOps::isNonZero( b[j], tolerance ) ) { lead = j; break; }
      if ( lead == n ) return std::make_pair( mul_w, mul_b ); // b is null vector
 
      std::tie( mul_w, mul_b ) = ScalarOps::getMultipliers( w[ lead ], b[ lead ] );
      
      for (Size j = 0; j < n; j++) 
        w[j] = mul_w * w[j] - mul_b * b[j];
      return std::make_pair( mul_w, mul_b );
    }

References DGtal::detail::AffineGeometryScalarOperations< TScalar >::getMultipliers(), and DGtal::detail::AffineGeometryScalarOperations< TScalar >::isNonZero().

reductionOnBasis()

template<typename TPoint >

static Point DGtal::AffineGeometry< TPoint >::reductionOnBasis ( const Point &  v, const Points &  basis, const double  tolerance  )

inlinestatic

Reduces the vector v on the (partial or not) basis of vectors basis.

Parameters

[in]	v	any vector
[in]	basis	a range of vectors forming a (partial or not) basis of the space.
[in]	tolerance	the accepted oo-norm below which the vector is null (used only for points with float/double coordinates).

Returns

the part of v that cannot be expressed as a linear combination of vectors of basis, and hence a null vector if v is a linear combination of the vectors of the basis.

Definition at line 804 of file AffineGeometry.h.

    {
      Point w( v );
      for ( const auto& b : basis ) reduceVector( w, b, tolerance );
      return w;
    }

References DGtal::AffineGeometry< TPoint >::reduceVector().

Referenced by DGtal::AffineGeometry< TPoint >::addIfIndependent(), and DGtal::AffineGeometry< TPoint >::independentVector().

simplifiedVector()

template<typename TPoint >

static Point DGtal::AffineGeometry< TPoint >::simplifiedVector ( Point  v )

inlinestatic

Given a vector, returns the aligned vector with its component simplified by the gcd of all components (when the components are integers) or the aligned vector with unit L2-norm (when the components are floating-point numbers).

Parameters

[in]

v

any vector.

Returns

a simplified vector aligned with v.

Definition at line 1039 of file AffineGeometry.h.

    {
      Scalar x;
      functions::getSquaredNormL2( x, v );
      PointOps::normalizeVector( v, x );
      return v;
    }

References DGtal::functions::getSquaredNormL2(), and DGtal::detail::AffineGeometryPointOperations< dim, TEuclideanRing, TContainer >::normalizeVector().

Referenced by DGtal::functions::computeSimplifiedVector(), DGtal::AffineBasis< TPoint >::normalize(), DGtal::AffineGeometry< TPoint >::orthogonalVector(), DGtal::AffineBasis< TPoint >::reduceAsEchelon(), and DGtal::AffineBasis< TPoint >::reduceAsLLL().

transform() [1/2]

template<typename TPoint >

static const Point & DGtal::AffineGeometry< TPoint >::transform ( const Point &  w )

inlinestatic

Transform a vector or point into the representation chosen for AffineGeometry class. This overloading takes care of the trivial case, where there is no need to change the representation.

Parameters

[in]

w

any vector or point

Returns

the same vector or point (does nothing).

Definition at line 929 of file AffineGeometry.h.

    {
      return w;
    }

Referenced by DGtal::AffineBasis< TPoint >::AffineBasis(), DGtal::AffineGeometry< TPoint >::affineBasis(), DGtal::AffineGeometry< TPoint >::affineBasis(), DGtal::AffineBasis< TPoint >::AffineBasis(), DGtal::AffineBasis< TPoint >::AffineBasis(), DGtal::AffineGeometry< TPoint >::affineSubset(), DGtal::AffineGeometry< TPoint >::affineSubset(), DGtal::AffineBasis< TPoint >::initBasis(), and DGtal::AffineGeometry< TPoint >::orthogonalVector().

transform() [2/2]

template<typename TPoint >

template<typename TInputPoint >

static Point DGtal::AffineGeometry< TPoint >::transform ( const TInputPoint &  w )

inlinestatic

Transform a vector or point into the representation chosen for AffineGeometry class. This overloading takes care of the generic case, where a transformation of each component is required.

Parameters

[in]

w

any vector or point

Returns

the same vector or point, but in the represention chosen for this class.

Definition at line 943 of file AffineGeometry.h.

    {
      return PointOps::cast( w );
    }

References DGtal::detail::AffineGeometryPointOperations< dim, TEuclideanRing, TContainer >::cast().

Field Documentation

dimension

template<typename TPoint >

const Size DGtal::AffineGeometry< TPoint >::dimension = Point::dimension

static

Definition at line 461 of file AffineGeometry.h.

Referenced by DGtal::AffineGeometry< TPoint >::affineBasis(), DGtal::AffineGeometry< TPoint >::affineBasis(), DGtal::AffineGeometry< TPoint >::affineSubset(), DGtal::AffineGeometry< TPoint >::affineSubset(), DGtal::AffineGeometry< TPoint >::completeBasis(), DGtal::AffineGeometry< TPoint >::independentVector(), and DGtal::AffineGeometry< TPoint >::orthogonalVector().

---

The documentation for this struct was generated from the following file:

• AffineGeometry.h