DGtal  1.5.beta
checkFullConvexityTheorems.cpp File Reference
#include <iostream>
#include <queue>
#include "DGtal/base/Common.h"
#include "DGtal/helpers/StdDefs.h"
#include "DGtal/geometry/volumes/DigitalConvexity.h"
Include dependency graph for checkFullConvexityTheorems.cpp:

Go to the source code of this file.

Functions

template<typename Point >
void makeRandom (Point &p, int width)
 
template<typename Point >
void makeRandomRange (std::vector< Point > &X, int nb, int width)
 
template<typename ProjectedPoint , typename Point >
void project (ProjectedPoint &pp, const Point &p, Dimension a)
 
template<typename ProjectedPoint , typename Point >
void projectRange (std::vector< ProjectedPoint > &pp, const std::vector< Point > &p, Dimension a)
 
template<typename Space >
bool checkSkelStarCvxHFullConvexity (int width)
 
template<typename Space >
bool checkCvxHPlusHypercubeFullConvexity (int width)
 
template<typename Space >
bool checkProjectionFullConvexity (int width)
 
template<typename Point >
void displayPointRange2D (const std::vector< Point > &X)
 
template<typename Space >
bool checkFullConvexityCharacterization (int width)
 
int main (int argc, char *argv[])
 

Detailed Description

This program is free software: you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program. If not, see http://www.gnu.org/licenses/.

Author
Jacques-Olivier Lachaud (jacqu.nosp@m.es-o.nosp@m.livie.nosp@m.r.la.nosp@m.chaud.nosp@m.@uni.nosp@m.v-sav.nosp@m.oie..nosp@m.fr ) Laboratory of Mathematics (CNRS, UMR 5127), University of Savoie, France
Date
2021/06/20

An example file named checkFullConvexityTheorems

This file is part of the DGtal library.

Definition in file checkFullConvexityTheorems.cpp.

Function Documentation

◆ checkCvxHPlusHypercubeFullConvexity()

template<typename Space >
bool checkCvxHPlusHypercubeFullConvexity ( int  width)
Examples
geometry/volumes/checkFullConvexityTheorems.cpp.

Definition at line 135 of file checkFullConvexityTheorems.cpp.

136 {
137  typedef typename Space::Integer Integer;
139  typedef DGtal::DigitalConvexity< KSpace > DConvexity;
140  typedef typename KSpace::Point Point;
141  typedef std::vector<Point> PointRange;
142 
143  // Generate a random polytope in the specified domain
144  Point lo = Point::zero;
145  Point hi = Point::diagonal( width );
146  DConvexity dconv( lo, hi );
147  std::vector< Point > X, XpH, Y;
148  int nb = Space::dimension + rand() % 7;
149  makeRandomRange( X, nb, width );
150  std::sort( X.begin(), X.end() );
151  XpH = X;
152  for ( Dimension k = 0; k < Space::dimension; k++ )
153  XpH = dconv.U( k, XpH );
154  auto P = dconv.makePolytope( XpH );
155  P.getPoints( Y );
156  auto E = dconv.envelope( X );
157  bool ok1 = dconv.isFullyConvex( E );
158  if ( ! ok1 )
159  trace.warning() << "FC*(X) is not fully convex !" << std::endl;
160  bool ok2 = dconv.isFullyConvex( Y );
161  if ( ! ok2 )
162  {
163  trace.warning() << "CvxH(X+H) cap Z^d is not fully convex !" << std::endl;
164  for ( auto p : Y ) std::cout << " " << p;
165  trace.warning() << std::endl;
166  }
167  bool ok3 = std::includes( Y.cbegin(), Y.cend(), E.cbegin(), E.cend() );
168  trace.info() << "#X=" << X.size()
169  << " #CvxH(X+H) cap Z^d=" << Y.size()
170  << ( ok2 ? "/FC" : "/ERROR" )
171  << " #FC*(X)=" << E.size() << ( ok1 ? "/FC" : "/ERROR" )
172  << ( ok3 ? " FC*(X) subset CvxH(X+H) cap Z^d"
173  : " FC*(X) not subset CvxH(X+H) cap Z^d" )
174  << std::endl;
175  return ok1 && ok2;
176 }
void makeRandomRange(std::vector< Point > &X, int nb, int width)
void getPoints(std::vector< Point > &pts) const
PointRange U(Dimension i, const PointRange &X) const
bool isFullyConvex(const PointRange &X, bool convex0=false) const
PointRange envelope(const PointRange &Z, EnvelopeAlgorithm algo=EnvelopeAlgorithm::DIRECT) const
LatticePolytope makePolytope(const PointRange &X, bool make_minkowski_summable=false) const
Aim: This class is a model of CCellularGridSpaceND. It represents the cubical grid as a cell complex,...
TInteger Integer
Arithmetic ring induced by (+,-,*) and Integer numbers.
Definition: SpaceND.h:102
std::ostream & info()
std::ostream & warning()
std::vector< Point > PointRange
DGtal::uint32_t Dimension
Definition: Common.h:136
Trace trace
Definition: Common.h:153
MyPointD Point
Definition: testClone2.cpp:383

References DGtal::DigitalConvexity< TKSpace >::envelope(), DGtal::BoundedLatticePolytope< TSpace >::getPoints(), DGtal::Trace::info(), DGtal::DigitalConvexity< TKSpace >::isFullyConvex(), DGtal::DigitalConvexity< TKSpace >::makePolytope(), makeRandomRange(), DGtal::trace, DGtal::DigitalConvexity< TKSpace >::U(), and DGtal::Trace::warning().

◆ checkFullConvexityCharacterization()

template<typename Space >
bool checkFullConvexityCharacterization ( int  width)
Examples
geometry/volumes/checkFullConvexityTheorems.cpp.

Definition at line 244 of file checkFullConvexityTheorems.cpp.

245 {
246  typedef typename Space::Integer Integer;
248  typedef DGtal::DigitalConvexity< KSpace > DConvexity;
249  typedef typename KSpace::Point Point;
250  typedef std::vector<Point> PointRange;
251  typedef DGtal::KhalimskySpaceND< Space::dimension-1, Integer > ProjKSpace;
252  typedef DGtal::DigitalConvexity< ProjKSpace > ProjDConvexity;
253  typedef typename ProjKSpace::Point ProjPoint;
254  typedef std::vector<ProjPoint> ProjPointRange;
255 
256  // Generate a random polytope in the specified domain
257  Point lo = Point::zero;
258  Point hi = Point::diagonal( width );
259  DConvexity dconv( lo, hi );
260  std::vector< Point > X, Y;
261  int n = Space::dimension + rand() % 17;
262  makeRandomRange( X, n, width );
263  auto P = dconv.makePolytope( X );
264  P.getPoints( Y );
265  const bool cvx = dconv.is0Convex( Y );
266  const bool fc = dconv.isFullyConvex( Y );
267  bool proj_fc = true;
268  std::cout << "#X=" << Y.size()
269  << " " << ( cvx ? "X C" : "X NC" )
270  << "/" << ( fc ? "X FC" : "X NFC" );
271  for ( Dimension a = 0; a < Space::dimension; a++ )
272  {
273  ProjPoint plo, phi;
274  project( plo, lo, a );
275  project( phi, hi, a );
276  ProjDConvexity pdconv( plo, phi );
277  std::vector< ProjPoint > PE;
278  projectRange( PE, Y, a );
279  if ( Space::dimension == 3 )
280  {
281  std::cout << std::endl;
282  displayPointRange2D( PE );
283  }
284  bool ok = pdconv.isFullyConvex( PE );
285  bool ok0 = pdconv.is0Convex( PE );
286  std::cout << "/" << a << ( ok0 ? ( ok ? "FC" : "NFC" ) : "NC" );
287  proj_fc = proj_fc && ok;
288  if ( fc && !ok )
289  trace.warning() << "Projection is not fully convex !" << std::endl;
290  }
291  if ( fc != proj_fc )
292  trace.warning() << "X is " << ( fc ? "FCvx" : "not FCvx" )
293  << "proj(X) " << ( proj_fc ? "FCvx" : "not FCvx" )
294  << std::endl;
295  else std::cout << ( fc ? " => FC ok" : " => Not FC ok" ) << std::endl;
296  return fc == proj_fc;
297 }
void projectRange(std::vector< ProjectedPoint > &pp, const std::vector< Point > &p, Dimension a)
void project(ProjectedPoint &pp, const Point &p, Dimension a)
void displayPointRange2D(const std::vector< Point > &X)
bool is0Convex(const PointRange &X) const
PolygonalCalculus< SH3::RealPoint, SH3::RealVector >::Vector phi(const Face f)

References displayPointRange2D(), DGtal::BoundedLatticePolytope< TSpace >::getPoints(), DGtal::DigitalConvexity< TKSpace >::is0Convex(), DGtal::DigitalConvexity< TKSpace >::isFullyConvex(), DGtal::DigitalConvexity< TKSpace >::makePolytope(), makeRandomRange(), phi(), project(), projectRange(), DGtal::trace, and DGtal::Trace::warning().

◆ checkProjectionFullConvexity()

template<typename Space >
bool checkProjectionFullConvexity ( int  width)
Examples
geometry/volumes/checkFullConvexityTheorems.cpp.

Definition at line 181 of file checkFullConvexityTheorems.cpp.

182 {
183  typedef typename Space::Integer Integer;
185  typedef DGtal::DigitalConvexity< KSpace > DConvexity;
186  typedef typename KSpace::Point Point;
187  typedef std::vector<Point> PointRange;
188  typedef DGtal::KhalimskySpaceND< Space::dimension-1, Integer > ProjKSpace;
189  typedef DGtal::DigitalConvexity< ProjKSpace > ProjDConvexity;
190  typedef typename ProjKSpace::Point ProjPoint;
191  typedef std::vector<ProjPoint> ProjPointRange;
192 
193  // Generate a random polytope in the specified domain
194  Point lo = Point::zero;
195  Point hi = Point::diagonal( width );
196  DConvexity dconv( lo, hi );
197  std::vector< Point > X;
198  int n = Space::dimension + rand() % 7;
199  makeRandomRange( X, n, width );
200  auto E = dconv.envelope( X );
201  unsigned int nb = 0;
202  unsigned int nb_ok = 0;
203  for ( Dimension a = 0; a < Space::dimension; a++ )
204  {
205  ProjPoint plo, phi;
206  project( plo, lo, a );
207  project( phi, hi, a );
208  ProjDConvexity pdconv( plo, phi );
209  std::vector< ProjPoint > PE;
210  projectRange( PE, E, a );
211  bool ok = pdconv.isFullyConvex( PE );
212  if ( !ok )
213  trace.warning() << "Projection is not fully convex !" << std::endl;
214  nb_ok += ok ? 1 : 0;
215  nb += 1;
216  std::cout << "#E=" << E.size() << " #Proj(E)=" << PE.size()
217  << (ok ? "/FC" : "/ERROR" ) << std::endl;
218  }
219  return nb_ok == nb;
220 }

References DGtal::DigitalConvexity< TKSpace >::envelope(), makeRandomRange(), phi(), project(), projectRange(), DGtal::trace, and DGtal::Trace::warning().

◆ checkSkelStarCvxHFullConvexity()

template<typename Space >
bool checkSkelStarCvxHFullConvexity ( int  width)
Examples
geometry/volumes/checkFullConvexityTheorems.cpp.

Definition at line 94 of file checkFullConvexityTheorems.cpp.

95 {
96  typedef typename Space::Integer Integer;
98  typedef DGtal::DigitalConvexity< KSpace > DConvexity;
99  typedef typename KSpace::Point Point;
100  typedef std::vector<Point> PointRange;
101 
102  // Generate a random polytope in the specified domain
103  Point lo = Point::zero;
104  Point hi = Point::diagonal( width );
105  DConvexity dconv( lo, hi );
106  std::vector< Point > X;
107  int nb = Space::dimension + rand() % 7;
108  makeRandomRange( X, nb, width );
109  auto C = dconv.StarCvxH( X );
110  auto E = dconv.envelope( X );
111  auto Y = C.extremaOfCells();
112  bool ok1 = dconv.isFullyConvex( E );
113  if ( ! ok1 )
114  trace.warning() << "FC*(X) is not fully convex !" << std::endl;
115  bool ok2 = dconv.isFullyConvex( Y );
116  if ( ! ok2 )
117  {
118  trace.warning() << "Extr(Star(CvxH(X))) is not fully convex !" << std::endl;
119  for ( auto p : Y ) std::cout << " " << p;
120  trace.warning() << std::endl;
121  }
122  bool ok3 = std::includes( Y.cbegin(), Y.cend(), E.cbegin(), E.cend() );
123  trace.info() << "#X=" << X.size()
124  << " #FC*(X)=" << E.size() << ( ok1 ? "/FC" : "/ERROR" )
125  << " #Extr(Star(CvxH(X)))=" << Y.size()
126  << ( ok2 ? "/FC" : "/ERROR" )
127  << ( ok3 ? " FC*(X) subset Extr(Star(CvxH(X)))" : " Inclusion ERROR" )
128  << std::endl;
129  return ok1 && ok2 && ok3;
130 }
LatticeSet StarCvxH(const PointRange &X, Dimension axis=dimension) const

References DGtal::DigitalConvexity< TKSpace >::envelope(), DGtal::Trace::info(), DGtal::DigitalConvexity< TKSpace >::isFullyConvex(), makeRandomRange(), DGtal::DigitalConvexity< TKSpace >::StarCvxH(), DGtal::trace, and DGtal::Trace::warning().

◆ displayPointRange2D()

template<typename Point >
void displayPointRange2D ( const std::vector< Point > &  X)
Examples
geometry/volumes/checkFullConvexityTheorems.cpp.

Definition at line 223 of file checkFullConvexityTheorems.cpp.

224 {
225  if ( X.empty() ) return;
226  Point lo = X[ 0 ];
227  Point hi = X[ 0 ];
228  for ( auto&& p : X ) { lo = lo.inf( p ); hi = hi.sup( p ); }
229  auto w = hi[ 0 ] - lo[ 0 ] + 1;
230  auto h = hi[ 1 ] - lo[ 1 ] + 1;
231  for ( int y = 0; y < h; y++ )
232  {
233  for ( int x = 0; x < w; x++ )
234  {
235  Point q( lo[ 0 ] + x, lo[ 1 ] + y );
236  std::cout << ( std::binary_search( X.cbegin(), X.cend(), q ) ? "*" : "." );
237  }
238  std::cout << std::endl;
239  }
240 }

Referenced by checkFullConvexityCharacterization().

◆ main()

int main ( int  argc,
char *  argv[] 
)

Definition at line 299 of file checkFullConvexityTheorems.cpp.

300 {
301  int NB_TEST1 = 5;
302  int NB_TEST2 = 5;
303  int NB_TEST3 = 5;
304  int NB_TEST4 = 25;
305  {
306  trace.beginBlock( "Check SkelStarCvxH(X) full convexity 2D" );
308  unsigned int nb = 0;
309  unsigned int nb_ok = 0;
310  for ( int i = 0; i < NB_TEST1; i++ )
311  {
312  nb_ok += checkSkelStarCvxHFullConvexity< Space >( 100 ) ? 1 : 0;
313  nb += 1;
314  }
315  trace.info() << nb_ok << "/" << nb << " OK tests" << std::endl;
316  trace.endBlock();
317  }
318  {
319  trace.beginBlock( "Check SkelStarCvxH(X) full convexity 3D" );
321  unsigned int nb = 0;
322  unsigned int nb_ok = 0;
323  for ( int i = 0; i < NB_TEST1; i++ )
324  {
325  nb_ok += checkSkelStarCvxHFullConvexity< Space >( 30 ) ? 1 : 0;
326  nb += 1;
327  }
328  trace.info() << nb_ok << "/" << nb << " OK tests" << std::endl;
329  trace.endBlock();
330  }
331  {
332  trace.beginBlock( "Check SkelStarCvxH(X) full convexity 4D" );
334  unsigned int nb = 0;
335  unsigned int nb_ok = 0;
336  for ( int i = 0; i < NB_TEST1; i++ )
337  {
338  nb_ok += checkSkelStarCvxHFullConvexity< Space >( 10 ) ? 1 : 0;
339  nb += 1;
340  }
341  trace.info() << nb_ok << "/" << nb << " OK tests" << std::endl;
342  trace.endBlock();
343  }
344  {
345  trace.beginBlock( "Check Projection full convexity 3D" );
347  unsigned int nb = 0;
348  unsigned int nb_ok = 0;
349  for ( int i = 0; i < NB_TEST2; i++ )
350  {
351  nb_ok += checkProjectionFullConvexity< Space >( 30 ) ? 1 : 0;
352  nb += 1;
353  }
354  trace.info() << nb_ok << "/" << nb << " OK tests" << std::endl;
355  trace.endBlock();
356  }
357  {
358  trace.beginBlock( "Check Projection full convexity 4D" );
360  unsigned int nb = 0;
361  unsigned int nb_ok = 0;
362  for ( int i = 0; i < NB_TEST2; i++ )
363  {
364  nb_ok += checkProjectionFullConvexity< Space >( 10 ) ? 1 : 0;
365  nb += 1;
366  }
367  trace.info() << nb_ok << "/" << nb << " OK tests" << std::endl;
368  trace.endBlock();
369  }
370  {
371  trace.beginBlock( "Check CvxH plus Hypercube full convexity 2D" );
373  unsigned int nb = 0;
374  unsigned int nb_ok = 0;
375  for ( int i = 0; i < NB_TEST3; i++ )
376  {
377  nb_ok += checkCvxHPlusHypercubeFullConvexity< Space >( 100 ) ? 1 : 0;
378  nb += 1;
379  }
380  trace.info() << nb_ok << "/" << nb << " OK tests" << std::endl;
381  trace.endBlock();
382  }
383  {
384  trace.beginBlock( "Check CvxH plus Hypercube full convexity 3D" );
386  unsigned int nb = 0;
387  unsigned int nb_ok = 0;
388  for ( int i = 0; i < NB_TEST3; i++ )
389  {
390  nb_ok += checkCvxHPlusHypercubeFullConvexity< Space >( 30 ) ? 1 : 0;
391  nb += 1;
392  }
393  trace.info() << nb_ok << "/" << nb << " OK tests" << std::endl;
394  trace.endBlock();
395  }
396  {
397  trace.beginBlock( "Check CvxH plus Hypercube full convexity 4D" );
399  unsigned int nb = 0;
400  unsigned int nb_ok = 0;
401  for ( int i = 0; i < NB_TEST3; i++ )
402  {
403  nb_ok += checkCvxHPlusHypercubeFullConvexity< Space >( 10 ) ? 1 : 0;
404  nb += 1;
405  }
406  trace.info() << nb_ok << "/" << nb << " OK tests" << std::endl;
407  trace.endBlock();
408  }
409  {
410  trace.beginBlock( "Check full convexity characterization 3D" );
412  unsigned int nb = 0;
413  unsigned int nb_ok = 0;
414  for ( int i = 0; i < NB_TEST4; i++ )
415  {
416  nb_ok += checkFullConvexityCharacterization< Space >( 10 ) ? 1 : 0;
417  nb += 1;
418  }
419  trace.info() << nb_ok << "/" << nb << " OK tests" << std::endl;
420  trace.endBlock();
421  }
422  {
423  trace.beginBlock( "Check full convexity characterization 4D" );
425  unsigned int nb = 0;
426  unsigned int nb_ok = 0;
427  for ( int i = 0; i < NB_TEST4; i++ )
428  {
429  nb_ok += checkFullConvexityCharacterization< Space >( 10 ) ? 1 : 0;
430  nb += 1;
431  }
432  trace.info() << nb_ok << "/" << nb << " OK tests" << std::endl;
433  trace.endBlock();
434  }
435  return 0;
436 }
void beginBlock(const std::string &keyword="")
double endBlock()

References DGtal::Trace::beginBlock(), DGtal::Trace::endBlock(), DGtal::Trace::info(), and DGtal::trace.

◆ makeRandom()

template<typename Point >
void makeRandom ( Point p,
int  width 
)
Examples
geometry/volumes/checkFullConvexityTheorems.cpp.

Definition at line 56 of file checkFullConvexityTheorems.cpp.

57 {
58  for ( Dimension i = 0; i < Point::dimension; i++ )
59  p[ i ] = rand() % width;
60 }

Referenced by makeRandomRange().

◆ makeRandomRange()

template<typename Point >
void makeRandomRange ( std::vector< Point > &  X,
int  nb,
int  width 
)
Examples
geometry/volumes/checkFullConvexityTheorems.cpp.

Definition at line 63 of file checkFullConvexityTheorems.cpp.

64 {
65  X.resize( nb );
66  for ( int i = 0; i < nb; i++ )
67  makeRandom( X[ i ], width );
68 }
void makeRandom(Point &p, int width)

References makeRandom().

Referenced by checkCvxHPlusHypercubeFullConvexity(), checkFullConvexityCharacterization(), checkProjectionFullConvexity(), and checkSkelStarCvxHFullConvexity().

◆ project()

template<typename ProjectedPoint , typename Point >
void project ( ProjectedPoint &  pp,
const Point p,
Dimension  a 
)
Examples
geometry/volumes/checkFullConvexityTheorems.cpp.

Definition at line 71 of file checkFullConvexityTheorems.cpp.

72 {
73  Dimension j = 0;
74  for ( Dimension i = 0; i < Point::dimension; i++ )
75  if ( i != a ) pp[ j++ ] = p[ i ];
76 }

Referenced by checkFullConvexityCharacterization(), checkProjectionFullConvexity(), and projectRange().

◆ projectRange()

template<typename ProjectedPoint , typename Point >
void projectRange ( std::vector< ProjectedPoint > &  pp,
const std::vector< Point > &  p,
Dimension  a 
)
Examples
geometry/volumes/checkFullConvexityTheorems.cpp.

Definition at line 79 of file checkFullConvexityTheorems.cpp.

81 {
82  pp.resize( p.size() );
83  for ( auto i = 0; i < p.size(); i++ )
84  project( pp[ i ], p[ i ], a );
85  std::sort( pp.begin(), pp.end() );
86  auto last = std::unique( pp.begin(), pp.end() );
87  pp.erase( last, pp.end() );
88 }

References project().

Referenced by checkFullConvexityCharacterization(), and checkProjectionFullConvexity().