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/AffineBasis.h>

Inheritance diagram for DGtal::AffineBasis< TPoint >:

[legend]

Public Types
enum struct	Type { INVALID = 0 , ECHELON_REDUCED , SHORTEST_ECHELON_REDUCED , LLL_REDUCED }

typedef AffineBasis< TPoint >	Self

typedef TPoint	Point

typedef Point::Coordinate	Scalar

typedef std::vector< Point >	Points

typedef AffineGeometry< Point >	Affine

Public Member Functions
standard services
	AffineBasis (const double tolerance=1e-12)

template<typename TInputPoint >
	AffineBasis (const std::vector< TInputPoint > &points, AffineBasis::Type type, const double delta=0.99, const double tolerance=1e-12)

template<typename TInputPoint >
	AffineBasis (const TInputPoint &origin, const std::vector< TInputPoint > &basis, AffineBasis::Type type, bool is_reduced=false, const double delta=0.99, const double tolerance=1e-12)

template<typename TInputPoint >
	AffineBasis (const TInputPoint &origin, const TInputPoint &normal, AffineBasis::Type type=Type::ECHELON_REDUCED, const double tolerance=1e-12)

void	reduce (AffineBasis::Type type, double delta)

Dimension	dimension () const

const Point &	origin () const

const Points &	basis () const

debug and I/O services
void	selfDisplay (std::ostream &out) const

bool	isValid () const

std::string	reductionTypeName () const

Data Fields
public data
Point	first
	the origin of the affine basis

Points	second
	the vector basis

double	epsilon {1e-12}
	the accepted value below which a floating-point number is 0.

AffineBasis::Type	_type
	the type of reduction of the basis.

Protected Member Functions
protected services
void	normalize ()

void	reduceAsEchelon (Type type)

void	orderEchelonBasis ()
	Guarantees that the basis is in echelon form.

void	reduceAsLLL (double delta, Scalar)

template<typename TInputPoint >
void	initBasis (const std::vector< TInputPoint > &basis)

void	sortBasis ()

std::size_t	findIndexWithSmallestNonNullComponent (Dimension k, std::size_t i, const std::vector< Point > &basis)

geometry services
bool	isParallel (const Self &other) const

std::pair< Scalar, Point >	rationalCoordinates (const Point &p) const

bool	isOnAffineSpace (const Point &p) const

bool	isParallel (const Point &w) const

Point	recompose (Scalar d, const Point &lambda, const Point &r=Point::zero) const

Point	recomposeVector (Scalar d, const Point &lambda, const Point &r=Point::zero) const

std::tuple< Scalar, Point, Point >	decompose (const Point &p) const

std::tuple< Scalar, Point, Point >	decomposeVector (Point w) const

template<typename ProjectedPoint >
Scalar	projectPoints (std::vector< ProjectedPoint > &result, const Points &input)

template<typename OtherPoint >
static void	transform (OtherPoint &pp, const Point &p)

template<typename OtherPoint >
static void	dilatedTransform (OtherPoint &pp, const Point &p, Scalar m)

Detailed Description

template<typename TPoint>
struct DGtal::AffineBasis< 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 'AffineBasis'

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/AffineBasis.h"
...
typedef SpaceND< 3, int >                Space;      
typedef Space::Point                     Point;
typedef AffineBasis< 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: testAffineBasis.cpp

Note: Affine basis can be computed in several forms, which are more or less suited according to the targeted use:

ECHELON_REDUCED: the basis A is in row echelon form, useful for solving systems of the form Ax=b. A drawback is that component values may increase quickly if we ask for integers.
SHORTEST_ECHELON_REDUCED: the basis A is in row echelon form, but the computation first sorts the input vector from the shortest to the longest vectors before Gauss elimination. It is useful for solving systems of the form Ax=b. A drawback is also that component values may increase quickly if we ask for integers.
LLL_REDUCED (specific to lattice vectors): the basis A is not
in row echelon form but is made of almost the shortest
possible lattice vectors. It is implemented with the LLL
algorithm (see <a
href="https://en.wikipedia.org/wiki/Lenstra–Lenstra–Lovász_lattice_basis_reduction_algorithm">
Wikipedia LLL algorithm ). It is not handy for solving
systems but the basis vectors are in general much shorter than
in row echelon form.

Definition at line 111 of file AffineBasis.h.

Member Typedef Documentation

◆ Affine

template<typename TPoint >

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

Definition at line 117 of file AffineBasis.h.

◆ Point

template<typename TPoint >

typedef TPoint DGtal::AffineBasis< TPoint >::Point

Definition at line 114 of file AffineBasis.h.

◆ Points

template<typename TPoint >

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

Definition at line 116 of file AffineBasis.h.

◆ Scalar

template<typename TPoint >

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

Definition at line 115 of file AffineBasis.h.

◆ Self

template<typename TPoint >

typedef AffineBasis<TPoint> DGtal::AffineBasis< TPoint >::Self

Definition at line 113 of file AffineBasis.h.

Member Enumeration Documentation

◆ Type

template<typename TPoint >

enum struct DGtal::AffineBasis::Type

strong

Enumerator
INVALID	invalid basis
ECHELON_REDUCED	echelon matrix
SHORTEST_ECHELON_REDUCED	echelon matrix starting from shortest vectors
LLL_REDUCED	delta-LLL reduced matrix

Definition at line 119 of file AffineBasis.h.

                     {
      INVALID = 0,     
      ECHELON_REDUCED, 
      SHORTEST_ECHELON_REDUCED, 
      LLL_REDUCED      
    };

Constructor & Destructor Documentation

◆ AffineBasis() [1/4]

template<typename TPoint >

DGtal::AffineBasis< TPoint >::AffineBasis ( const double tolerance = 1e-12 )

inline

Default constructor. This create the identity basis of the space.

Parameters

[in] tolerance the accepted oo-norm below which the vector is null (used only for points with float/double coordinates).

Definition at line 137 of file AffineBasis.h.

      : epsilon( tolerance )
    {
      first  = Point::zero;
      second.resize( Point::dimension );
      for ( auto k = 0; k < Point::dimension; k++ )
        second[ k ] = Point::base( k );
      _type = Type::SHORTEST_ECHELON_REDUCED;
    }

References DGtal::AffineBasis< TPoint >::_type, DGtal::AffineBasis< TPoint >::first, DGtal::AffineBasis< TPoint >::second, and DGtal::AffineBasis< TPoint >::SHORTEST_ECHELON_REDUCED.

◆ AffineBasis() [2/4]

template<typename TPoint >

template<typename TInputPoint >

DGtal::AffineBasis< TPoint >::AffineBasis	(	const std::vector< TInputPoint > &	points,
		AffineBasis< TPoint >::Type	type,
		const double	delta = `0.99`,
		const double	tolerance = `1e-12`
	)

inline

Constructor from points.

Parameters

[in]	points	the range of points belonging to the affine space.
[in]	type	if Type::ECHELON_REDUCED or Type::SHORTEST_ECHELON_REDUCED, reduces the basis so that it forms a echelon matrix, otherwise computes its delta-LLL-lattice.
[in]	delta	the parameter \( \delta \) of LLL-algorithm, which should be between 0.25 and 1 (value 0.99 is default in sagemath).
[in]	tolerance	the accepted oo-norm below which the vector is null (used only for points with float/double coordinates).

Definition at line 164 of file AffineBasis.h.

      : epsilon( tolerance )
    {
      if ( points.size() == 0 ) return;
      first  = Affine::transform( points[ 0 ] );
      std::vector< TInputPoint > basis( points.size() - 1 );
      for ( std::size_t i = 0; i < basis.size(); i++ )
        basis[ i ] = ( points[ i+1 ] - first );
      initBasis( basis );
      reduce( type, delta );
    }

References DGtal::AffineBasis< TPoint >::basis(), DGtal::AffineBasis< TPoint >::first, DGtal::AffineBasis< TPoint >::initBasis(), DGtal::AffineBasis< TPoint >::reduce(), and DGtal::AffineGeometry< TPoint >::transform().

◆ AffineBasis() [3/4]

template<typename TPoint >

template<typename TInputPoint >

DGtal::AffineBasis< TPoint >::AffineBasis	(	const TInputPoint &	origin,
		const std::vector< TInputPoint > &	basis,
		AffineBasis< TPoint >::Type	type,
		bool	is_reduced = `false`,
		const double	delta = `0.99`,
		const double	tolerance = `1e-12`
	)

inline

Constructor from origin and basis.

Parameters

[in]	origin	the origin of the affine basis
[in]	basis	the range of vectors forming the basis
[in]	type	if Type::ECHELON_REDUCED or Type::SHORTEST_ECHELON_REDUCED, reduces the basis so that it forms a echelon matrix, otherwise computes its delta-LLL-lattice.
[in]	is_reduced	when 'true', assumes that the given basis is already reduced, otherwise it forces the reduction of the basis.
[in]	delta	the parameter \( \delta \) of LLL-algorithm, which should be between 0.25 and 1 (value 0.99 is default in sagemath).
[in]	tolerance	the accepted oo-norm below which the vector is null (used only for points with float/double coordinates).

Definition at line 201 of file AffineBasis.h.

      : epsilon( tolerance )
    {
      first = Affine::transform( origin );
      initBasis( basis );
      if ( ! is_reduced ) reduce( type, delta );
      else _type = type;
    }

References DGtal::AffineBasis< TPoint >::_type, DGtal::AffineBasis< TPoint >::basis(), DGtal::AffineBasis< TPoint >::first, DGtal::AffineBasis< TPoint >::initBasis(), DGtal::AffineBasis< TPoint >::origin(), DGtal::AffineBasis< TPoint >::reduce(), and DGtal::AffineGeometry< TPoint >::transform().

◆ AffineBasis() [4/4]

template<typename TPoint >

template<typename TInputPoint >

DGtal::AffineBasis< TPoint >::AffineBasis	(	const TInputPoint &	origin,
		const TInputPoint &	normal,
		AffineBasis< TPoint >::Type	type = `Type::ECHELON_REDUCED`,
		const double	tolerance = `1e-12`
	)

inline

Creates an affine basis going through origin and orthogonal to the lattice vector normal.

Parameters

[in]	origin	the origin of the affine basis
[in]	normal	the lattice normal vector.
[in]	type	if Type::ECHELON_REDUCED or Type::SHORTEST_ECHELON_REDUCED, then the basis will be in echelon form, otherwise it will make the vectors as short as possible, but the matrix won't be in echelon form.
[in]	tolerance	the accepted oo-norm below which the vector is null (used only for points with float/double coordinates).

Definition at line 230 of file AffineBasis.h.

      : epsilon( tolerance )
    {
      first = Affine::transform( origin );
      // basis is shortened is type is LLL.
      second = Affine::orthogonalLatticeBasis( normal, type == Type::LLL_REDUCED );
      _type = ( type == Type::LLL_REDUCED )
        ? Type::LLL_REDUCED : Type::ECHELON_REDUCED;
    }

References DGtal::AffineBasis< TPoint >::_type, DGtal::AffineBasis< TPoint >::ECHELON_REDUCED, DGtal::AffineBasis< TPoint >::first, DGtal::AffineBasis< TPoint >::LLL_REDUCED, DGtal::AffineBasis< TPoint >::origin(), DGtal::AffineGeometry< TPoint >::orthogonalLatticeBasis(), DGtal::AffineBasis< TPoint >::second, and DGtal::AffineGeometry< TPoint >::transform().

Member Function Documentation

◆ basis()

template<typename TPoint >

const Points & DGtal::AffineBasis< TPoint >::basis ( ) const

inline

Returns: the vectors spanning the vector space of this affine basis.

Definition at line 284 of file AffineBasis.h.

    {
      return second;
    }

References DGtal::AffineBasis< TPoint >::second.

Referenced by DGtal::AffineBasis< TPoint >::AffineBasis(), DGtal::AffineBasis< TPoint >::AffineBasis(), DGtal::AffineBasis< TPoint >::findIndexWithSmallestNonNullComponent(), and DGtal::AffineBasis< TPoint >::initBasis().

◆ decompose()

template<typename TPoint >

std::tuple< Scalar, Point, Point > DGtal::AffineBasis< TPoint >::decompose ( const Point & p ) const

inline

Decompose p as d * (p - o) = l[0]b[0] + ... l[i]b[i] + r, where r is independent from this basis B=(b[0],...,b[i]).

Parameters

[in] p any point.

Returns: (d,l,r) where d is a scalar, l/d are the rational coordinates of (p-o) in the basis, r is the remainer vector if p does not belong to the affine space.

Definition at line 401 of file AffineBasis.h.

    {
      return decomposeVector( p - first );
    }

References DGtal::AffineBasis< TPoint >::decomposeVector(), and DGtal::AffineBasis< TPoint >::first.

Referenced by DGtal::AffineBasis< TPoint >::isOnAffineSpace(), DGtal::AffineBasis< TPoint >::projectPoints(), and DGtal::AffineBasis< TPoint >::rationalCoordinates().

◆ decomposeVector()

template<typename TPoint >

std::tuple< Scalar, Point, Point > DGtal::AffineBasis< TPoint >::decomposeVector ( Point w ) const

inline

Decompose w as d * w = l[0]b[0] + ... l[i]b[i] + r, where r is independent from B=(b[0],...,b[i]).

Parameters

[in] w any vector.

Returns: (d,l,r) where d is a scalar, l/d are the rational coordinates of w in the basis, r is the remainer vector if w does not belong to the affine space.

Definition at line 414 of file AffineBasis.h.

    {
      Point r;
      Scalar alphas = 1;
      for ( auto i = 0; i < second.size(); i++ )
        {
          std::pair< Scalar, Scalar > c
            = Affine::reduceVector( w, second[ i ], i, epsilon );
          for ( auto j = 0; j < i; j++ )
            r[ j ] *= c.first;
          r[ i ]  = c.second;
          alphas *= c.first;
        }
      return alphas >= 0
        ? std::make_tuple(  alphas,  r,  w )
        : std::make_tuple( -alphas, -r, -w );
    }

References DGtal::AffineBasis< TPoint >::epsilon, DGtal::AffineGeometry< TPoint >::reduceVector(), and DGtal::AffineBasis< TPoint >::second.

Referenced by DGtal::AffineBasis< TPoint >::decompose(), and DGtal::AffineBasis< TPoint >::isParallel().

◆ dilatedTransform()

template<typename TPoint >

template<typename OtherPoint >

static void DGtal::AffineBasis< TPoint >::dilatedTransform	(	OtherPoint &	pp,
		const Point &	p,
		Scalar	m
	)

inlinestatic

Transforms the type of an input point into another one, while dilating it by a factor m.

Template Parameters

OtherPoint a type of point of dimension at most Point::dimension.

Parameters

[out]	pp	the output restricted point.
[in]	p	the input point.
[in]	m	the dilation factor.

Definition at line 492 of file AffineBasis.h.

    {
      BOOST_STATIC_ASSERT( OtherPoint::dimension <= Point::dimension );
      for ( std::size_t i = 0; i < pp.dimension; ++i )
        pp[ i ] = m * Scalar( p[ i ] );
    }

Referenced by DGtal::AffineBasis< TPoint >::projectPoints().

◆ dimension()

template<typename TPoint >

Dimension DGtal::AffineBasis< TPoint >::dimension ( ) const

inline

Returns: the affine dimension of the basis

Precondition: the basis is reduced.

Definition at line 271 of file AffineBasis.h.

    {
      return second.size();
    }

References DGtal::AffineBasis< TPoint >::second.

Referenced by DGtal::AffineBasis< TPoint >::isParallel().

◆ findIndexWithSmallestNonNullComponent()

template<typename TPoint >

std::size_t DGtal::AffineBasis< TPoint >::findIndexWithSmallestNonNullComponent	(	Dimension	k,
		std::size_t	i,
		const std::vector< Point > &	basis
	)

inlineprotected

Given a range of points basis, starting from rank i, find the index of the point with lowest non null k-th coefficient in absolute value, or basis.size() if every point had its k-th component null.

Parameters

[in]	k	the component/coordinate of interest
[in]	i	the starting index
[in]	basis	a range of points/vectors

Returns: starting from rank i, the index of the point with lowest non null k-th coefficient in absolute value, or basis.size() if every point had its k-th component null.

Definition at line 708 of file AffineBasis.h.

    {
      ASSERT( ! basis.empty() );
      ASSERT( k < Point::dimension );
      std::size_t index = i;
      Scalar      v     = 0;
      for ( ; index < basis.size(); index++ )
        {
          v = abs( basis[ index ][ k ] );
          if ( Affine::ScalarOps::isNonZero( v, epsilon ) )
            break;
        }
      for ( auto j = index + 1; j < basis.size(); j++ )
        {
          Scalar vj = abs( basis[ j ][ k ] );
          if ( vj != 0 && vj < v )
            {
              index = j;
              v     = vj;
            }
        }
      return index;
    }

References DGtal::AffineBasis< TPoint >::basis(), DGtal::AffineBasis< TPoint >::epsilon, and index().

Referenced by DGtal::AffineBasis< TPoint >::reduceAsEchelon().

◆ initBasis()

template<typename TPoint >

template<typename TInputPoint >

void DGtal::AffineBasis< TPoint >::initBasis ( const std::vector< TInputPoint > & basis )

inlineprotected

Removes null vectors from input set of vectors and sets the initial basis.

Template Parameters

TInputPoint the type of input points

Parameters

[in] basis a set of arbitrary vectors

Definition at line 660 of file AffineBasis.h.

    {
      second.reserve( basis.size() );
      for ( auto i = 0; i < basis.size(); i++ )
        {
          Point b = Affine::transform( basis[ i ] );
          if ( b != Point::zero ) second.push_back( b );
        }
    }

References DGtal::AffineBasis< TPoint >::basis(), DGtal::AffineBasis< TPoint >::second, and DGtal::AffineGeometry< TPoint >::transform().

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

◆ isOnAffineSpace()

template<typename TPoint >

bool DGtal::AffineBasis< TPoint >::isOnAffineSpace ( const Point & p ) const

inline

Parameters

[in] p any lattice point

Returns: 'true' if and only if the point belongs to the affine space spanned by 'this'.

Definition at line 326 of file AffineBasis.h.

    {
      const auto [d, lambda, r] = decompose( p );
      return ! Affine::ScalarOps::isNonZero( r.normInfinity(), epsilon );
    }

References DGtal::AffineBasis< TPoint >::decompose(), and DGtal::AffineBasis< TPoint >::epsilon.

◆ isParallel() [1/2]

template<typename TPoint >

bool DGtal::AffineBasis< TPoint >::isParallel ( const Point & w ) const

inline

Parameters

[in] w any lattice vector

Returns: 'true' if and only if the vector w is parallel to the affine space spanned by 'this'.

Definition at line 336 of file AffineBasis.h.

    {
      const auto [d, lambda, r] = decomposeVector( w );
      return ! Affine::ScalarOps::isNonZero( r.normInfinity(), epsilon );
    }

References DGtal::AffineBasis< TPoint >::decomposeVector(), and DGtal::AffineBasis< TPoint >::epsilon.

◆ isParallel() [2/2]

template<typename TPoint >

bool DGtal::AffineBasis< TPoint >::isParallel ( const Self & other ) const

inline

Parameters

[in] other an other affine basis

Returns: 'true' if and only if every vector of 'this' basis is parallel to every vector of the other given basis.

Definition at line 299 of file AffineBasis.h.

    {
      if ( dimension() != other.dimension() ) return false;
      if ( ( _type != Type::ECHELON_REDUCED )
           && ( _type != Type::SHORTEST_ECHELON_REDUCED ) )
        trace.error() << "[AffineBasis::isParallel] Requires type=*_ECHELON_REDUCED\n"
                      << " type=" << reductionTypeName() << "\n" ;
      for ( const auto& b : other.second )
        if ( ! isParallel( b ) ) return false;
      return true;
    }

References DGtal::AffineBasis< TPoint >::_type, DGtal::AffineBasis< TPoint >::dimension(), DGtal::AffineBasis< TPoint >::ECHELON_REDUCED, DGtal::Trace::error(), DGtal::AffineBasis< TPoint >::isParallel(), DGtal::AffineBasis< TPoint >::reductionTypeName(), DGtal::AffineBasis< TPoint >::second, DGtal::AffineBasis< TPoint >::SHORTEST_ECHELON_REDUCED, and DGtal::trace.

Referenced by DGtal::AffineBasis< TPoint >::isParallel().

◆ isValid()

template<typename TPoint >

bool DGtal::AffineBasis< TPoint >::isValid ( ) const

inline

Returns: 'true' if and only if this object is in a consistent state. Here it means that the matrix is echelon or LLL-reduced.

Definition at line 520 of file AffineBasis.h.

    {
      return _type != Type::INVALID;
    }  

References DGtal::AffineBasis< TPoint >::_type, and DGtal::AffineBasis< TPoint >::INVALID.

◆ normalize()

template<typename TPoint >

void DGtal::AffineBasis< TPoint >::normalize ( )

inlineprotected

If the basis is an integer lattice, reduces the basis vectors by their gcd, otherwise normalize vectors to have 1 L2-norm.

Definition at line 554 of file AffineBasis.h.

    {
      for ( auto& v : second )
        v = Affine::simplifiedVector( v );
    }

References DGtal::AffineBasis< TPoint >::second, and DGtal::AffineGeometry< TPoint >::simplifiedVector().

Referenced by DGtal::AffineBasis< TPoint >::sortBasis().

◆ orderEchelonBasis()

template<typename TPoint >

void DGtal::AffineBasis< TPoint >::orderEchelonBasis ( )

inlineprotected

Guarantees that the basis is in echelon form.

Definition at line 596 of file AffineBasis.h.

    {
      auto compare = [this] ( const Point& v, const Point& w ) -> bool
      {
        // Note: curiously std::sort sometimes test v against itself
        // and must return false in this case.
        for ( auto k = 0; k < Point::dimension; ++k )
          {
            bool v_non_null = Affine::ScalarOps::isNonZero( v[ k ], epsilon );
            bool w_non_null = Affine::ScalarOps::isNonZero( w[ k ], epsilon );
            if ( v_non_null && ! w_non_null )      return true;
            else if ( ! v_non_null && w_non_null ) return false;
            else if ( v_non_null && w_non_null )   return false; // ==
          }
        return false; // 0 == 0
      };
      std::sort( second.begin(), second.end(), compare );
    }

References compare(), DGtal::AffineBasis< TPoint >::epsilon, and DGtal::AffineBasis< TPoint >::second.

Referenced by DGtal::AffineBasis< TPoint >::reduceAsEchelon().

◆ origin()

template<typename TPoint >

const Point & DGtal::AffineBasis< TPoint >::origin ( ) const

inline

Returns: the origin of this affine basis.

Definition at line 277 of file AffineBasis.h.

    {
      return first;
    }

References DGtal::AffineBasis< TPoint >::first.

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

◆ projectPoints()

template<typename TPoint >

template<typename ProjectedPoint >

Scalar DGtal::AffineBasis< TPoint >::projectPoints	(	std::vector< ProjectedPoint > &	result,
		const Points &	input
	)

inline

Projects the range of points input onto the affine basis and outputs it in result. A consistent choice for ProjectedPoint is to match the affine dimension.

Template Parameters

ProjectedPoint a type of point that matches the affine dimension.

Parameters

[out]	result	the range of projected points.
[in]	input	the range of input points

Returns: the maximum dilation of projected rational coordinates that was used to create integer coordinates.

Definition at line 444 of file AffineBasis.h.

    {
      Scalar lcm = 1;
      std::vector< Scalar > denoms ( input.size() );
      std::vector< Point >  lambdas( input.size() );
      Point  r;
      // get points rational coordinates.
      for ( std::size_t i = 0; i < input.size(); i++ )
        std::tie( denoms[ i ], lambdas[ i ], r ) = decompose( input[ i ] );
      // compute ppcm
      for ( std::size_t i = 0; i < denoms.size(); i++ )
        {
          const Scalar d = denoms[ i ];
          if ( d == 1 ) continue;
          lcm = Affine::ScalarOps::lcmPositive( lcm, d );
        }
      // project points
      result.resize( input.size() );
      for ( std::size_t i = 0; i < input.size(); i++ )
        dilatedTransform( result[ i ], lambdas[ i ], lcm / denoms[ i ] );
      return lcm;
    }

References DGtal::AffineBasis< TPoint >::decompose(), and DGtal::AffineBasis< TPoint >::dilatedTransform().

◆ rationalCoordinates()

template<typename TPoint >

std::pair< Scalar, Point > DGtal::AffineBasis< TPoint >::rationalCoordinates ( const Point & p ) const

inline

Parameters

[in] p any lattice point

Returns: its rational coordinates L/d as a pair (d, L) in this affine basis, where L is a lattice vector and d is the common denominator for the components of L.

Definition at line 316 of file AffineBasis.h.

    {
      const auto [d, lambda, remainder] = decompose( p );
      return std::make_pair( d, lambda );
    }

References DGtal::AffineBasis< TPoint >::decompose().

◆ recompose()

template<typename TPoint >

Point DGtal::AffineBasis< TPoint >::recompose	(	Scalar	d,
		const Point &	lambda,
		const Point &	r = `Point::zero`
	)		const

inline

Given (d, lambda, r), recompose the point p such that d * (p - o) = l[0]b[0] + ... l[i]b[i] + r. Given only the rational coordinates (d,lambda), the point is assumed to lie on this affine space (i.e. r == 0 ).

Parameters

[in]	d	the common denominator that defines the rational coordinates with lambda.
[in]	lambda	the numerators that defines the rational coordinates with d.
[in]	r	the remainder vector (r is independent from this basis B=(b[0],...,b[i])), which represents the displacement from p to this affine space.

Returns: the point p such that d * (p - o) = B lambda + r, for B the vectors of this basis (arranged as rows in matrix) and o its origin.

Definition at line 360 of file AffineBasis.h.

    {
      return first + recomposeVector( d, lambda, r );
    }

References DGtal::AffineBasis< TPoint >::first, and DGtal::AffineBasis< TPoint >::recomposeVector().

◆ recomposeVector()

template<typename TPoint >

Point DGtal::AffineBasis< TPoint >::recomposeVector	(	Scalar	d,
		const Point &	lambda,
		const Point &	r = `Point::zero`
	)		const

inline

Given (d, lambda, r), recompose the vector w such that d * w = l[0]b[0] + ... l[i]b[i] + r. Given only the rational coordinates (d,lambda), the vector is assumed to be parallel to this affine space (i.e. r == 0 ).

Parameters

[in]	d	the common denominator that defines the rational coordinates with lambda.
[in]	lambda	the numerators that defines the rational coordinates with d.
[in]	r	the remainder vector (r is independent from this basis B=(b[0],...,b[i])), which represents the displacement vector to this vector space.

Returns: the point p such that d * w = B lambda + r, for B the vectors of this basis (arranged as rows in matrix) and o its origin.

Definition at line 384 of file AffineBasis.h.

    {
      Point w = r;
      for ( std::size_t i = 0; i < second.size(); i++ )
        w += lambda[ i ] * second[ i ];
      return w / d;
    }

References DGtal::AffineBasis< TPoint >::second.

Referenced by DGtal::AffineBasis< TPoint >::recompose().

◆ reduce()

template<typename TPoint >

void DGtal::AffineBasis< TPoint >::reduce	(	AffineBasis< TPoint >::Type	type,
		double	delta
	)

inline

Reduces the basis into a set of a linearly independent vectors, and in the desired reduced form.

Parameters

[in]	type	the desired type of matrix reduction.
[in]	delta	the parameter \( \delta \) of LLL-algorithm, which should be between 0.25 and 1 (value 0.99 is default in sagemath).

Definition at line 252 of file AffineBasis.h.

    {
      if ( type == Type::SHORTEST_ECHELON_REDUCED )
        sortBasis();
      if ( type == Type::ECHELON_REDUCED || type == Type::SHORTEST_ECHELON_REDUCED )
        reduceAsEchelon( type );
      else if ( type == Type::LLL_REDUCED )
        {
          std::vector< Point > X( second.size()+1 );
          X[ 0 ] = first;
          for ( auto i = 0; i < second.size(); i++ )
            X[ i+1 ] = second[ i ] + first;
          std::tie( first, second ) = AffineGeometry<Point>::affineBasis( X, epsilon );
          reduceAsLLL( delta, (Scalar) 0 );
        }
    }

References DGtal::AffineGeometry< TPoint >::affineBasis(), DGtal::AffineBasis< TPoint >::ECHELON_REDUCED, DGtal::AffineBasis< TPoint >::epsilon, DGtal::AffineBasis< TPoint >::first, DGtal::AffineBasis< TPoint >::LLL_REDUCED, DGtal::AffineBasis< TPoint >::reduceAsEchelon(), DGtal::AffineBasis< TPoint >::reduceAsLLL(), DGtal::AffineBasis< TPoint >::second, DGtal::AffineBasis< TPoint >::SHORTEST_ECHELON_REDUCED, and DGtal::AffineBasis< TPoint >::sortBasis().

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

◆ reduceAsEchelon()

template<typename TPoint >

void DGtal::AffineBasis< TPoint >::reduceAsEchelon ( Type type )

inlineprotected

Reduces the basis so that each basis vector is normalized, removes linearly dependent vectors, and builds a echelon matrix.

Definition at line 562 of file AffineBasis.h.

    {
      std::vector< bool > is_independent( second.size(), false );
      std::vector< std::vector< Scalar > > U( second.size() );
      Dimension k = 0; // the current column to put in echelon form.
      for ( std::size_t i = 0; i < second.size(); i++ )
        {
          std::size_t row = findIndexWithSmallestNonNullComponent( k, i, second );
          if ( row != i && row != second.size() )
            std::swap( second[ i ], second[ row ] );            
          Point& w            = second[ i ];
          // check if this vector is independent from the previous ones
          is_independent[ i ] = true;
          for ( std::size_t j = 0; j < i; j++ )
            if ( is_independent[ j ] )
              Affine::reduceVector( w, second[ j ], epsilon );
          if ( ! Affine::ScalarOps::isNonZero( w.normInfinity(), epsilon ) )
            is_independent[ i ] = false; // not independent, forget it
          else
            { // independent, make sure it is reduced.
              w = Affine::simplifiedVector( w );
              k++;
            }
        }
      Points new_basis;
      for ( std::size_t i = 0; i < second.size(); i++ )
        if ( is_independent[ i ] )
          new_basis.push_back( second[ i ] );
      std::swap( second, new_basis );
      orderEchelonBasis();
      _type = type;
    }

References DGtal::AffineBasis< TPoint >::_type, DGtal::AffineBasis< TPoint >::epsilon, DGtal::AffineBasis< TPoint >::findIndexWithSmallestNonNullComponent(), DGtal::AffineBasis< TPoint >::orderEchelonBasis(), DGtal::AffineGeometry< TPoint >::reduceVector(), DGtal::AffineBasis< TPoint >::second, and DGtal::AffineGeometry< TPoint >::simplifiedVector().

Referenced by DGtal::AffineBasis< TPoint >::reduce().

◆ reduceAsLLL()

template<typename TPoint >

void DGtal::AffineBasis< TPoint >::reduceAsLLL	(	double	delta,
		Scalar
	)

inlineprotected

Reduces the basis so that each basis vector is normalized, then computes its delta-LLL-reduction lattice, and removes linearly dependent vectors.

Parameters

[in] delta the parameter \( \delta \) of LLL-algorithm, which should be between 0.25 and 1 (value 0.99 is default in sagemath).

keep only independent vectors in basis

Definition at line 622 of file AffineBasis.h.

    {
      if constexpr( std::is_floating_point< Scalar >::value == true )
        {
          trace.error() << "[AffineBasis::reduceAsLLL]"
                        << " It has no meaning to use LLL algorithm on matrix with double coefficients\n";
          _type = Type::INVALID;
          return;
        }
      for ( auto& v : second )
        v = Affine::simplifiedVector( v );
      std::vector< std::vector< Scalar > > B( second.size() );
      for ( auto i = 0; i < second.size(); i++ )
        {
          B[ i ] = std::vector< Scalar >( Point::dimension );
          for ( auto j = 0; j < Point::dimension; j++ )
            B[ i ][ j ] = second[ i ][ j ];
        }
      functions::reduceBasisWithLLL( B, delta );
      second.clear();
      for ( std::size_t i = 0; i < B.size(); i++ )
        {
          Point b;
          for ( auto j = 0; j < Point::dimension; j++ )
            b[ j ] = B[ i ][ j ];
          if ( b != Point::zero )
            second.push_back( Affine::simplifiedVector( b ) );
        }
      _type = Type::LLL_REDUCED;
    }

References DGtal::AffineBasis< TPoint >::_type, DGtal::Trace::error(), DGtal::AffineBasis< TPoint >::INVALID, DGtal::AffineBasis< TPoint >::LLL_REDUCED, DGtal::functions::reduceBasisWithLLL(), DGtal::AffineBasis< TPoint >::second, DGtal::AffineGeometry< TPoint >::simplifiedVector(), and DGtal::trace.

Referenced by DGtal::AffineBasis< TPoint >::reduce().

◆ reductionTypeName()

template<typename TPoint >

std::string DGtal::AffineBasis< TPoint >::reductionTypeName ( ) const

inline

Returns: the type of matrix as a string

Definition at line 526 of file AffineBasis.h.

    {
      if ( _type == Type::INVALID )              return "INVALID";
      else if ( _type == Type::ECHELON_REDUCED ) return "ECHELON_REDUCED";
      else if ( _type == Type::SHORTEST_ECHELON_REDUCED ) return "SHORTEST_ECHELON_REDUCED";
      else if ( _type == Type::LLL_REDUCED )     return "LLL_REDUCED";
      else return "";
    }

References DGtal::AffineBasis< TPoint >::_type, DGtal::AffineBasis< TPoint >::ECHELON_REDUCED, DGtal::AffineBasis< TPoint >::INVALID, DGtal::AffineBasis< TPoint >::LLL_REDUCED, and DGtal::AffineBasis< TPoint >::SHORTEST_ECHELON_REDUCED.

Referenced by DGtal::AffineBasis< TPoint >::isParallel(), and DGtal::AffineBasis< TPoint >::selfDisplay().

◆ selfDisplay()

template<typename TPoint >

void DGtal::AffineBasis< TPoint >::selfDisplay ( std::ostream & out ) const

inline

Displays this object on the output stream.

Parameters

[in,out] out any output stream.

Definition at line 509 of file AffineBasis.h.

    {
      out << "[ AffineBasis o=" << first
          << " type=" << reductionTypeName()
          << " B=";
      for ( auto b : second ) std::cout << "\n  " << b;
      out << " ]";
    }

References DGtal::AffineBasis< TPoint >::first, DGtal::AffineBasis< TPoint >::reductionTypeName(), and DGtal::AffineBasis< TPoint >::second.

Referenced by DGtal::operator<<().

◆ sortBasis()

template<typename TPoint >

void DGtal::AffineBasis< TPoint >::sortBasis ( )

inlineprotected

Simplifies vectors, removes duplicates and puts smallest candidate basis vectors before longest.

Definition at line 672 of file AffineBasis.h.

    {
      // Reduces all vectors
      normalize();
      // Purge duplicates
      std::sort( second.begin(), second.end() );
      second.erase( std::unique( second.begin(), second.end() ), second.end() );
      // Sort according to size of components.
      auto compare = []( const Point& u, const Point& v ) -> bool
      {
        const auto n1_u = u.norm1();
        const auto n1_v = v.norm1();
        if ( n1_u < n1_v ) return true;
        else if ( n1_v < n1_u ) return false;
        const auto noo_u = u.normInfinity();
        const auto noo_v = v.normInfinity();
        if ( noo_u < noo_v ) return true;
        else if ( noo_v < noo_u ) return false;
        return u < v;
      };
      std::sort( second.begin(), second.end(), compare );
    }

References compare(), DGtal::AffineBasis< TPoint >::normalize(), and DGtal::AffineBasis< TPoint >::second.

Referenced by DGtal::AffineBasis< TPoint >::reduce().

◆ transform()

template<typename TPoint >

template<typename OtherPoint >

static void DGtal::AffineBasis< TPoint >::transform	(	OtherPoint &	pp,
		const Point &	p
	)

inlinestatic

Transforms the type of an input point into another one.

Template Parameters

OtherPoint a type of point of dimension at most Point::dimension.

Parameters

[out]	pp	the output restricted point.
[in]	p	the input point.

Definition at line 475 of file AffineBasis.h.

    {
      BOOST_STATIC_ASSERT( OtherPoint::dimension <= Point::dimension );
      typedef typename OtherPoint::Coordinate Scalar;
      for ( std::size_t i = 0; i < pp.dimension; ++i )
        pp[ i ] = Scalar( p[ i ] );
    }

Field Documentation

◆ _type

template<typename TPoint >

AffineBasis::Type DGtal::AffineBasis< TPoint >::_type

the type of reduction of the basis.

Definition at line 544 of file AffineBasis.h.

Referenced by DGtal::AffineBasis< TPoint >::AffineBasis(), DGtal::AffineBasis< TPoint >::AffineBasis(), DGtal::AffineBasis< TPoint >::AffineBasis(), DGtal::AffineBasis< TPoint >::isParallel(), DGtal::AffineBasis< TPoint >::isValid(), DGtal::AffineBasis< TPoint >::reduceAsEchelon(), DGtal::AffineBasis< TPoint >::reduceAsLLL(), and DGtal::AffineBasis< TPoint >::reductionTypeName().

◆ epsilon

template<typename TPoint >

double DGtal::AffineBasis< TPoint >::epsilon {1e-12}

the accepted value below which a floating-point number is 0.

Definition at line 543 of file AffineBasis.h.

543{1e-12};

Referenced by DGtal::AffineBasis< TPoint >::decomposeVector(), DGtal::AffineBasis< TPoint >::findIndexWithSmallestNonNullComponent(), DGtal::AffineBasis< TPoint >::isOnAffineSpace(), DGtal::AffineBasis< TPoint >::isParallel(), DGtal::AffineBasis< TPoint >::orderEchelonBasis(), DGtal::AffineBasis< TPoint >::reduce(), and DGtal::AffineBasis< TPoint >::reduceAsEchelon().

◆ first

template<typename TPoint >

Point DGtal::AffineBasis< TPoint >::first

the origin of the affine basis

Definition at line 541 of file AffineBasis.h.

Referenced by DGtal::AffineBasis< TPoint >::AffineBasis(), DGtal::AffineBasis< TPoint >::AffineBasis(), DGtal::AffineBasis< TPoint >::AffineBasis(), DGtal::AffineBasis< TPoint >::AffineBasis(), DGtal::AffineBasis< TPoint >::decompose(), DGtal::AffineBasis< TPoint >::origin(), DGtal::AffineBasis< TPoint >::recompose(), DGtal::AffineBasis< TPoint >::reduce(), and DGtal::AffineBasis< TPoint >::selfDisplay().

◆ second

template<typename TPoint >

Points DGtal::AffineBasis< TPoint >::second

the vector basis

Definition at line 542 of file AffineBasis.h.

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

AffineBasis.h

Public Types

Public Member Functions

Data Fields

Protected Member Functions

geometry services

Detailed Description

Member Typedef Documentation

◆ Affine

◆ Point

◆ Points

◆ Scalar

◆ Self

Member Enumeration Documentation

◆ Type

Constructor & Destructor Documentation

◆ AffineBasis() [1/4]

◆ AffineBasis() [2/4]

◆ AffineBasis() [3/4]

◆ AffineBasis() [4/4]

Member Function Documentation

◆ basis()

◆ decompose()

◆ decomposeVector()

◆ dilatedTransform()

◆ dimension()

◆ findIndexWithSmallestNonNullComponent()

◆ initBasis()

◆ isOnAffineSpace()

◆ isParallel() [1/2]

◆ isParallel() [2/2]

◆ isValid()

◆ normalize()

◆ orderEchelonBasis()

◆ origin()

◆ projectPoints()

◆ rationalCoordinates()

◆ recompose()

◆ recomposeVector()

◆ reduce()

◆ reduceAsEchelon()

◆ reduceAsLLL()

◆ reductionTypeName()

◆ selfDisplay()

◆ sortBasis()

◆ transform()

Field Documentation

◆ _type

◆ epsilon

◆ first

◆ second