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

Definition at line 88 of file AffineBasis.h.

Member Typedef Documentation

◆ Affine

template<typename TPoint >

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

Definition at line 94 of file AffineBasis.h.

◆ Point

template<typename TPoint >

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

Definition at line 91 of file AffineBasis.h.

◆ Points

template<typename TPoint >

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

Definition at line 93 of file AffineBasis.h.

◆ Scalar

template<typename TPoint >

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

Definition at line 92 of file AffineBasis.h.

◆ Self

template<typename TPoint >

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

Definition at line 90 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 96 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 114 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 141 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 178 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 207 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 261 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 378 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 391 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 469 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 248 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 685 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 637 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 303 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 313 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 276 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 497 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 531 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 573 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 254 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 421 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 293 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 337 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 361 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 229 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 539 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 599 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 503 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 486 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 649 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 452 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 521 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 520 of file AffineBasis.h.

520{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 518 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 519 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