DGtal  1.5.beta
DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate > Class Template Reference

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< SpaceLatticePolytope
 
typedef DGtal::BoundedRationalPolytope< SpaceRationalPolytope
 
typedef std::vector< PointPointRange
 
typedef std::vector< VectorVectorRange
 
typedef std::unordered_set< PointPointSet
 
typedef std::pair< Point, IntegerNode
 
typedef std::priority_queue< Node, std::vector< Node >, NodeComparatorNodeQueue
 

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 Nodecurrent () const
 
void ignore ()
 
void expand ()
 
bool finished () const
 
Point symmetric (const Point &p) const
 
PointRange next (const Point &p) const
 

Data Fields

const PointPredicatemyPredicate
 The predicate that every point must satisfy. More...
 
DigitalConvexity< KSpacemyConvexity
 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
TKSpacean arbitrary model of CCellularGridSpaceND.
TPointPredicatean 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.

105  : myPredicate( &predicate ), myConvexity( lo, hi )
106  {
107  init( kcenter );
108  }
const PointPredicate * myPredicate
The predicate that every point must satisfy.
bool predicate(const Point &p) const
DigitalConvexity< KSpace > myConvexity
The digital convexity object.

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.

174  {
175  while ( ! finished() )
176  {
177  const auto p = current().first;
178  //NOT USED const auto d = current().second; // current ring distance
179  const auto sp = symmetric( p );
180  myPoints.insert( p );
181  myPoints.insert( sp );
182  PointRange X( myPoints.cbegin(), myPoints.cend() );
183  if ( enforce_full_convexity && ! myConvexity.isFullyConvex( X ) )
184  {
185  myPoints.erase( p );
186  myPoints.erase( sp );
187  ignore();
188  }
189  else
190  {
191  expand();
192  return true;
193  }
194  }
195  return false;
196  }
bool isFullyConvex(const PointRange &X, bool convex0=false) const
Point symmetric(const Point &p) const
PointSet myPoints
Symmetric range of lattice points, sorted.
std::vector< Point > PointRange

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.

206  {
207  return myQ.top();
208  }

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.

228  {
229  const Point p = current().first;
230  myQ.pop();
231  myPoints.insert( p );
232  myPoints.insert( symmetric( p ) );
233  const auto next_points = next( p );
234  for ( auto&& q : next_points )
235  {
236  if ( ! myM.count( q ) )
237  {
238  const auto sq = symmetric( q );
239  const bool q_in = predicate( q );
240  const bool sq_in = predicate( sq );
241  if ( q_in && sq_in )
242  {
243  Node n( q, (2*q - myKCenter).squaredNorm() );
244  myQ.push( n );
245  myM.insert( q );
246  myM.insert( sq );
247  if ( myPerfectSymmetry )
249  n.second );
250  }
251  else if ( ( q_in && ! sq_in ) || ( ! q_in && sq_in ) )
252  {
253  myPerfectSymmetry = false;
254  }
255  }
256  }
257  }
PointRange next(const Point &p) const
std::pair< Point, Integer > Node
PointSet myM
Marked points, i.e. points already in the queue or in the object.
Point myKCenter
Symmetry center (with doubled coordinates to represent half-integers).
bool myPerfectSymmetry
True iff the set and its local complement are symmetric.
Integer myPerfectSymmetryRadius
Upper bound on the max distance of perfect symmetry.
Point::Coordinate squaredNorm(Point const &aPoint)
int max(int a, int b)
MyPointD Point
Definition: testClone2.cpp:383

References DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::current(), max(), DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::myKCenter, DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::myM, DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::myPerfectSymmetry, DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::myPerfectSymmetryRadius, DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::myPoints, DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::myQ, DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::next(), DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::predicate(), and DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::symmetric().

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.

263  {
264  return myQ.empty();
265  }

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.

218  {
219  myQ.pop();
220  }

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.

116  {
117  myKCenter = kcenter;
118  myPoints.clear();
119  myQ = NodeQueue();
120  myM.clear();
121  myPerfectSymmetry = true;
123  // The starting points depend on the parity of the coordinates of the center.
124  // There are from 1 to 2^d starting points.
125  PointRange points;
126  const auto x = myKCenter[ 0 ];
127  if ( x % 2 == 0 )
128  points.push_back( Point::base( 0, x / 2 ) );
129  else
130  {
131  points.push_back( Point::base( 0, (x-1) / 2 ) );
132  points.push_back( Point::base( 0, (x+1) / 2 ) );
133  }
134  for ( Dimension k = 1; k < dimension; k++ )
135  {
136  const auto n = points.size();
137  const auto y = myKCenter[ k ];
138  if ( y % 2 == 0 )
139  {
140  for ( auto i = 0; i < n; i++ )
141  points[ i ][ k ] = y / 2;
142  }
143  else
144  {
145  points.resize( 2*n );
146  const auto z = (y-1)/2;
147  const auto z1 = z + 1;
148  for ( auto i = 0; i < n; i++ )
149  {
150  points[ i ][ k ] = z;
151  Point q = points[ i ];
152  q[ k ] = z1;
153  points[ i+n ] = q;
154  }
155  }
156  }
157  // Keep only the points that satisfy the predicate.
158  for ( auto&& p : points )
159  {
160  const Point sp = symmetric( p );
161  if ( ! myM.count( p )
162  && predicate( p ) && predicate( sp ) )
163  {
164  Node n( p, (2*p - myKCenter).squaredNorm() );
165  myQ.push( n );
166  myM.insert( p );
167  myM.insert( sp );
168  }
169  }
170  }
static Self base(Dimension k, Component val=1)
static Dimension size()
std::priority_queue< Node, std::vector< Node >, NodeComparator > NodeQueue
DGtal::uint32_t Dimension
Definition: Common.h:136

References DGtal::PointVector< dim, Integer >::base(), DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::dimension, DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::myKCenter, DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::myM, DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::myPerfectSymmetry, DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::myPerfectSymmetryRadius, DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::myPoints, DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::myQ, DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::predicate(), DGtal::PointVector< dim, TEuclideanRing, TContainer >::size(), and DGtal::SymmetricConvexExpander< TKSpace, TPointPredicate >::symmetric().

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.

274  {
275  PointRange N;
276  Point d = 2*p - myKCenter;
277  for ( Dimension i = 0; i < dimension; i++ )
278  {
279  if ( d[ i ] >= 0 ) N.push_back( p + Point::base( i, 1 ) );
280  if ( d[ i ] <= 0 ) N.push_back( p - Point::base( i, 1 ) );
281  }
282  return N;
283  }

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

◆ symmetric()

Field Documentation

◆ dimension

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

◆ 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

◆ 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

◆ myPoints

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

◆ 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


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