DGtal: DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate

Aim: SymmetricConvexExpander computes symmetric fully convex subsets of a given digital set. More...

#include </home/runner/work/DGtal/DGtal/examples/polyscope-examples/SymmetricConvexExpander.h>

Data Structures
struct	NodeComparator

Public Types
typedef DigitalConvexity< TKSpace >	Self

typedef TKSpace	KSpace

typedef TPointPredicate	PointPredicate

typedef KSpace::Integer	Integer

typedef KSpace::Point	Point

typedef KSpace::Vector	Vector

typedef KSpace::Space	Space

typedef std::size_t	Size

typedef DGtal::BoundedLatticePolytope< Space >	LatticePolytope

typedef DGtal::BoundedRationalPolytope< Space >	RationalPolytope

typedef std::vector< Point >	PointRange

typedef std::vector< Vector >	VectorRange

typedef std::unordered_set< Point >	PointSet

typedef std::pair< Point, Integer >	Node

typedef std::priority_queue< Node, std::vector< Node >, NodeComparator >	NodeQueue

Public Member Functions
	SymmetricConvexExpander (const PointPredicate &predicate, const Point &kcenter, const Point &lo, const Point &hi)
	Constructor from predicate and symmetry center point. More...

bool	predicate (const Point &p) const

void	init (const Point &kcenter)

bool	advance (bool enforce_full_convexity)
	Advance of one symmetric point. More...

const Node &	current () const

void	ignore ()

void	expand ()

bool	finished () const

Point	symmetric (const Point &p) const

PointRange	next (const Point &p) const

Data Fields
const PointPredicate *	myPredicate
	The predicate that every point must satisfy. More...

DigitalConvexity< KSpace >	myConvexity
	The digital convexity object. More...

Point	myKCenter
	Symmetry center (with doubled coordinates to represent half-integers). More...

PointSet	myPoints
	Symmetric range of lattice points, sorted. More...

NodeQueue	myQ

PointSet	myM
	Marked points, i.e. points already in the queue or in the object. More...

bool	myPerfectSymmetry
	True iff the set and its local complement are symmetric. More...

Integer	myPerfectSymmetryRadius
	Upper bound on the max distance of perfect symmetry. More...

Static Public Attributes
static const Dimension	dimension = KSpace::dimension

Private Member Functions
	BOOST_CONCEPT_ASSERT ((concepts::CCellularGridSpaceND< TKSpace >))

Detailed Description

template<typename TKSpace, typename TPointPredicate>
class DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >

Aim: SymmetricConvexExpander computes symmetric fully convex subsets of a given digital set.

Description of class 'SymmetricConvexExpander'

Template Parameters

TKSpace	an arbitrary model of CCellularGridSpaceND.
TPointPredicate	an arbitrary model of predicate Point -> bool

Definition at line 64 of file SymmetricConvexExpander.h.

Member Typedef Documentation

◆ Integer

template<typename TKSpace , typename TPointPredicate >

typedef KSpace::Integer DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::Integer

Definition at line 72 of file SymmetricConvexExpander.h.

◆ KSpace

template<typename TKSpace , typename TPointPredicate >

typedef TKSpace DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::KSpace

Definition at line 70 of file SymmetricConvexExpander.h.

◆ LatticePolytope

template<typename TKSpace , typename TPointPredicate >

typedef DGtal::BoundedLatticePolytope< Space > DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::LatticePolytope

Definition at line 77 of file SymmetricConvexExpander.h.

◆ Node

template<typename TKSpace , typename TPointPredicate >

typedef std::pair< Point, Integer > DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::Node

Definition at line 85 of file SymmetricConvexExpander.h.

◆ NodeQueue

template<typename TKSpace , typename TPointPredicate >

typedef std::priority_queue< Node, std::vector<Node>, NodeComparator > DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::NodeQueue

Definition at line 98 of file SymmetricConvexExpander.h.

◆ Point

template<typename TKSpace , typename TPointPredicate >

typedef KSpace::Point DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::Point

Definition at line 73 of file SymmetricConvexExpander.h.

◆ PointPredicate

template<typename TKSpace , typename TPointPredicate >

typedef TPointPredicate DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::PointPredicate

Definition at line 71 of file SymmetricConvexExpander.h.

◆ PointRange

template<typename TKSpace , typename TPointPredicate >

typedef std::vector<Point> DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::PointRange

Definition at line 79 of file SymmetricConvexExpander.h.

◆ PointSet

template<typename TKSpace , typename TPointPredicate >

typedef std::unordered_set<Point> DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::PointSet

Definition at line 81 of file SymmetricConvexExpander.h.

◆ RationalPolytope

template<typename TKSpace , typename TPointPredicate >

typedef DGtal::BoundedRationalPolytope< Space > DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::RationalPolytope

Definition at line 78 of file SymmetricConvexExpander.h.

◆ Self

template<typename TKSpace , typename TPointPredicate >

typedef DigitalConvexity<TKSpace> DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::Self

Definition at line 69 of file SymmetricConvexExpander.h.

◆ Size

template<typename TKSpace , typename TPointPredicate >

typedef std::size_t DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::Size

Definition at line 76 of file SymmetricConvexExpander.h.

◆ Space

template<typename TKSpace , typename TPointPredicate >

typedef KSpace::Space DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::Space

Definition at line 75 of file SymmetricConvexExpander.h.

◆ Vector

template<typename TKSpace , typename TPointPredicate >

typedef KSpace::Vector DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::Vector

Definition at line 74 of file SymmetricConvexExpander.h.

◆ VectorRange

template<typename TKSpace , typename TPointPredicate >

typedef std::vector<Vector> DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::VectorRange

Definition at line 80 of file SymmetricConvexExpander.h.

Constructor & Destructor Documentation

◆ SymmetricConvexExpander()

template<typename TKSpace , typename TPointPredicate >

DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::SymmetricConvexExpander	(	const PointPredicate &	predicate,
		const Point &	kcenter,
		const Point &	lo,
		const Point &	hi
	)

inline

Constructor from predicate and symmetry center point.

Definition at line 101 of file SymmetricConvexExpander.h.

       : myPredicate( &predicate ), myConvexity( lo, hi )
     {
       init( kcenter );
     }

References DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::init().

Member Function Documentation

◆ advance()

template<typename TKSpace , typename TPointPredicate >

bool DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::advance ( bool enforce_full_convexity )

inline

Advance of one symmetric point.

Definition at line 173 of file SymmetricConvexExpander.h.

     {
       while ( ! finished() )
         {
           const auto p = current().first;
           //NOT USED const auto d = current().second; // current ring distance
           const auto sp = symmetric( p );
           myPoints.insert( p );
           myPoints.insert( sp );
           PointRange X( myPoints.cbegin(), myPoints.cend() );
           if ( enforce_full_convexity && ! myConvexity.isFullyConvex( X ) )
             {
               myPoints.erase( p );
               myPoints.erase( sp );
               ignore();
             }
           else
             {
               expand();
               return true;
             }
         }
       return false;
     }

References DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::current(), DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::expand(), DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::finished(), DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::ignore(), DGtal::DigitalConvexity< TKSpace >::isFullyConvex(), DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::myConvexity, DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::myPoints, and DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::symmetric().

◆ BOOST_CONCEPT_ASSERT()

template<typename TKSpace , typename TPointPredicate >

DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::BOOST_CONCEPT_ASSERT ( (concepts::CCellularGridSpaceND< TKSpace >) )

private

◆ current()

template<typename TKSpace , typename TPointPredicate >

const Node& DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::current ( ) const

inline

Returns: a const reference on the current visited vertex. The node is a pair <Vertex,Data> where the second term is the topological distance to the start vertex or set.

NB: valid only if not 'finished()'.

Definition at line 205 of file SymmetricConvexExpander.h.

     {
       return myQ.top();
     }

References DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::myQ.

Referenced by DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::advance(), and DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::expand().

◆ expand()

template<typename TKSpace , typename TPointPredicate >

void DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::expand ( )

inline

Goes to the next vertex and take into account the current vertex for determining the future visited vertices. NB: valid only if not 'finished()'.

Definition at line 227 of file SymmetricConvexExpander.h.

     {
       const Point p = current().first;
       myQ.pop();
       myPoints.insert( p );
       myPoints.insert( symmetric( p ) );
       const auto next_points = next( p );
       for ( auto&& q : next_points )
         {
           if ( ! myM.count( q ) )
             {
               const auto  sq   = symmetric( q );
               const bool  q_in = predicate( q );
               const bool sq_in = predicate( sq );
               if ( q_in && sq_in )
                 {
                   Node n( q, (2*q - myKCenter).squaredNorm() );
                   myQ.push( n );
                   myM.insert(  q );
                   myM.insert( sq );
                   if ( myPerfectSymmetry )
                     myPerfectSymmetryRadius = std::max( myPerfectSymmetryRadius,
                                                         n.second );
                 }
               else if ( ( q_in && ! sq_in ) || ( ! q_in && sq_in ) )
                 {
                   myPerfectSymmetry = false;
                 }
             }
         }
     }

Referenced by DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::advance().

◆ finished()

template<typename TKSpace , typename TPointPredicate >

bool DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::finished ( ) const

inline

Returns: 'true' if all possible elements have been visited.

Definition at line 262 of file SymmetricConvexExpander.h.

     {
       return myQ.empty();
     }

References DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::myQ.

Referenced by DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::advance().

◆ ignore()

template<typename TKSpace , typename TPointPredicate >

void DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::ignore ( )

inline

Goes to the next vertex but ignores the current vertex for determining the future visited vertices. Otherwise said, no future visited vertex will have this vertex as a father.

NB: valid only if not 'finished()'.

Definition at line 217 of file SymmetricConvexExpander.h.

     {
       myQ.pop();
     }

References DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::myQ.

Referenced by DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::advance().

◆ init()

template<typename TKSpace , typename TPointPredicate >

void DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::init ( const Point & kcenter )

inline

Definition at line 115 of file SymmetricConvexExpander.h.

     {
       myKCenter = kcenter;
       myPoints.clear();
       myQ = NodeQueue();
       myM.clear();
       myPerfectSymmetry       = true;
       myPerfectSymmetryRadius = 0;
       // The starting points depend on the parity of the coordinates of the center.
       // There are from 1 to 2^d starting points.
       PointRange points;
       const auto x = myKCenter[ 0 ];
       if ( x % 2 == 0 )
         points.push_back( Point::base( 0, x / 2 ) );
       else
         {
           points.push_back( Point::base( 0, (x-1) / 2 ) );
           points.push_back( Point::base( 0, (x+1) / 2 ) );
         }
       for ( Dimension k = 1; k < dimension; k++ )
         {
           const auto n = points.size();
           const auto y = myKCenter[ k ];
           if ( y % 2 == 0 )
             {
               for ( auto i = 0; i < n; i++ )
                 points[ i ][ k ] = y / 2;
             }
           else
             {
               points.resize( 2*n );
               const auto z  = (y-1)/2;
               const auto z1 = z + 1;
               for ( auto i = 0; i < n; i++ )
                 {
                   points[ i ][ k ] = z;
                   Point q = points[ i ];
                   q[ k ]  = z1;
                   points[ i+n ]    = q;
                 }                  
             }
         }
       // Keep only the points that satisfy the predicate.
       for ( auto&& p : points )
         {
           const Point sp = symmetric( p );
           if ( ! myM.count( p )
                && predicate( p ) && predicate( sp ) )
             {
               Node n( p, (2*p - myKCenter).squaredNorm() );
               myQ.push( n );
               myM.insert( p );
               myM.insert( sp );
             }
         }
     }

Referenced by DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::SymmetricConvexExpander().

◆ next()

template<typename TKSpace , typename TPointPredicate >

PointRange DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::next ( const Point & p ) const

inline

Definition at line 273 of file SymmetricConvexExpander.h.

     {
       PointRange N;
       Point d = 2*p - myKCenter;
       for ( Dimension i = 0; i < dimension; i++ )
         {
           if ( d[ i ] >= 0 ) N.push_back( p + Point::base( i, 1 ) );
           if ( d[ i ] <= 0 ) N.push_back( p - Point::base( i, 1 ) );
         }
       return N;
     }

References DGtal::PointVector< dim, Integer >::base(), DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::dimension, and DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::myKCenter.

Referenced by DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::expand().

◆ predicate()

template<typename TKSpace , typename TPointPredicate >

bool DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::predicate ( const Point & p ) const

inline

Definition at line 110 of file SymmetricConvexExpander.h.

     {
       return (*myPredicate)( p );
     }

References DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::myPredicate.

Referenced by DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::expand(), and DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::init().

◆ symmetric()

template<typename TKSpace , typename TPointPredicate >

Point DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::symmetric ( const Point & p ) const

inline

Definition at line 268 of file SymmetricConvexExpander.h.

     {
       return myKCenter - p;
     }

References DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::myKCenter.

Referenced by DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::advance(), DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::expand(), and DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::init().

Field Documentation

◆ dimension

template<typename TKSpace , typename TPointPredicate >

const Dimension DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::dimension = KSpace::dimension

static

Definition at line 83 of file SymmetricConvexExpander.h.

Referenced by DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::init(), and DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::next().

◆ myConvexity

template<typename TKSpace , typename TPointPredicate >

DigitalConvexity< KSpace > DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::myConvexity

The digital convexity object.

Definition at line 289 of file SymmetricConvexExpander.h.

Referenced by DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::advance().

◆ myKCenter

template<typename TKSpace , typename TPointPredicate >

Point DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::myKCenter

Symmetry center (with doubled coordinates to represent half-integers).

Definition at line 292 of file SymmetricConvexExpander.h.

Referenced by DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::expand(), DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::init(), DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::next(), and DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::symmetric().

◆ myM

template<typename TKSpace , typename TPointPredicate >

PointSet DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::myM

Marked points, i.e. points already in the queue or in the object.

Definition at line 301 of file SymmetricConvexExpander.h.

Referenced by DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::expand(), and DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::init().

◆ myPerfectSymmetry

template<typename TKSpace , typename TPointPredicate >

bool DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::myPerfectSymmetry

True iff the set and its local complement are symmetric.

Definition at line 304 of file SymmetricConvexExpander.h.

Referenced by DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::expand(), and DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::init().

◆ myPerfectSymmetryRadius

template<typename TKSpace , typename TPointPredicate >

Integer DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::myPerfectSymmetryRadius

Upper bound on the max distance of perfect symmetry.

Definition at line 306 of file SymmetricConvexExpander.h.

Referenced by DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::expand(), and DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::init().

◆ myPoints

template<typename TKSpace , typename TPointPredicate >

PointSet DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::myPoints

Symmetric range of lattice points, sorted.

Definition at line 295 of file SymmetricConvexExpander.h.

◆ myPredicate

template<typename TKSpace , typename TPointPredicate >

const PointPredicate* DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::myPredicate

The predicate that every point must satisfy.

Definition at line 286 of file SymmetricConvexExpander.h.

Referenced by DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::predicate().

◆ myQ

template<typename TKSpace , typename TPointPredicate >

NodeQueue DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::myQ

Queue of points (only one point is inserted in the queue for a symmetric pair of point).

Definition at line 299 of file SymmetricConvexExpander.h.

Referenced by DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::current(), DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::expand(), DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::finished(), DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::ignore(), and DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::init().

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

SymmetricConvexExpander.h

Data Structures

Public Types

Public Member Functions

Data Fields

Static Public Attributes

Private Member Functions

Detailed Description

template<typename TKSpace, typename TPointPredicate> class DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >

Member Typedef Documentation

◆ Integer

◆ KSpace

◆ LatticePolytope

◆ Node

◆ NodeQueue

◆ Point

◆ PointPredicate

◆ PointRange

◆ PointSet

◆ RationalPolytope

◆ Self

◆ Size

◆ Space

◆ Vector

◆ VectorRange

Constructor & Destructor Documentation

◆ SymmetricConvexExpander()

Member Function Documentation

◆ advance()

◆ BOOST_CONCEPT_ASSERT()

◆ current()

◆ expand()

◆ finished()

◆ ignore()

◆ init()

◆ next()

◆ predicate()

◆ symmetric()

Field Documentation

◆ dimension

◆ myConvexity

◆ myKCenter

◆ myM

◆ myPerfectSymmetry

◆ myPerfectSymmetryRadius

◆ myPoints

◆ myPredicate

◆ myQ

template<typename TKSpace, typename TPointPredicate>
class DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >