34 #include "DGtal/base/Common.h"
35 #include "DGtal/kernel/SpaceND.h"
36 #include "DGtal/topology/KhalimskySpaceND.h"
37 #include "DGtal/geometry/volumes/CellGeometry.h"
38 #include "DGtal/geometry/volumes/DigitalConvexity.h"
39 #include "DGtalCatch.h"
43 using namespace DGtal;
50 SCENARIO(
"DigitalConvexity< Z2 > unit tests",
"[digital_convexity][2d]" )
56 DConvexity dconv(
Point( -5, -5 ),
Point( 10, 10 ) );
58 GIVEN(
"Given a fat simplex { (0,0), (4,-1), (2,5) } " ) {
60 auto vertex_cover = dconv.makeCellCover( V.begin(), V.end() );
61 auto fat_simplex = dconv.makeSimplex ( V.begin(), V.end() );
62 auto inside_pts = dconv.insidePoints ( fat_simplex );
63 auto simplex_cover = dconv.makeCellCover( fat_simplex );
64 auto point_cover = dconv.makeCellCover( inside_pts.begin(), inside_pts.end() );
65 THEN(
"The fat simplex is not degenerated." ) {
66 REQUIRE( dconv.isSimplexFullDimensional( V.begin(), V.end() ) );
68 THEN(
"Its vertex cover contains 3 0-cells, 12 1-cells, 12 2-cells" ) {
69 REQUIRE( vertex_cover.computeNbCells( 0 ) == 3 );
70 REQUIRE( vertex_cover.computeNbCells( 1 ) == 12 );
71 REQUIRE( vertex_cover.computeNbCells( 2 ) == 12 );
73 THEN(
"Its vertex cover is a subset of its point cover" ) {
74 REQUIRE( vertex_cover.subset( point_cover ) );
76 THEN(
"Its point cover is a subset of its simplex cover" ) {
77 REQUIRE( point_cover.subset( simplex_cover ) );
79 THEN(
"Being fat, its simplex cover is equal to its point cover" ) {
80 REQUIRE( simplex_cover.subset( point_cover ) );
83 GIVEN(
"Given a thin simplex { (0,0), (4,3), (7,5) } " ) {
85 auto vertex_cover = dconv.makeCellCover( V.begin(), V.end() );
86 auto thin_simplex = dconv.makeSimplex ( V.begin(), V.end() );
87 auto inside_pts = dconv.insidePoints ( thin_simplex );
88 auto simplex_cover = dconv.makeCellCover( thin_simplex );
89 auto point_cover = dconv.makeCellCover( inside_pts.begin(), inside_pts.end() );
90 THEN(
"The thin simplex is not degenerated." ) {
91 REQUIRE( dconv.isSimplexFullDimensional( V.begin(), V.end() ) );
93 THEN(
"Its vertex cover contains 3 0-cells, 12 1-cells, 12 2-cells" ) {
94 REQUIRE( vertex_cover.computeNbCells( 0 ) == 3 );
95 REQUIRE( vertex_cover.computeNbCells( 1 ) == 12 );
96 REQUIRE( vertex_cover.computeNbCells( 2 ) == 12 );
98 THEN(
"Its vertex cover is a subset of its point cover" ) {
99 REQUIRE( vertex_cover.subset( point_cover ) );
101 THEN(
"Its point cover is a subset of its simplex cover" ) {
102 REQUIRE( point_cover.subset( simplex_cover ) );
104 THEN(
"Being thin, its simplex cover is not equal to its point cover for 1<=dim<=2" ) {
105 REQUIRE( ! simplex_cover.subset( point_cover ) );
106 REQUIRE( simplex_cover.subset( point_cover, 0 ) );
107 REQUIRE( ! simplex_cover.subset( point_cover, 1 ) );
108 REQUIRE( ! simplex_cover.subset( point_cover, 2 ) );
113 SCENARIO(
"DigitalConvexity< Z2 > fully convex triangles",
"[convex_simplices][2d]" )
122 DConvexity dconv(
Point( -1, -1 ),
Point( 5, 5 ) );
124 WHEN(
"Computing all triangles in domain (0,0)-(4,4)." ) {
125 unsigned int nb_notsimplex = 0;
126 unsigned int nb_invalid = 0;
127 unsigned int nb_degenerated= 0;
128 unsigned int nb_common = 0;
129 unsigned int nb_unitary = 0;
134 nb_notsimplex += ! dconv.isSimplexFullDimensional( { a, b, c } ) ? 1 : 0;
135 auto tri_type = dconv.simplexType( { a, b, c } );
136 nb_degenerated += tri_type == DConvexity::SimplexType::DEGENERATED ? 1 : 0;
137 nb_invalid += tri_type == DConvexity::SimplexType::INVALID ? 1 : 0;
138 nb_unitary += tri_type == DConvexity::SimplexType::UNITARY ? 1 : 0;
139 nb_common += tri_type == DConvexity::SimplexType::COMMON ? 1 : 0;
141 THEN(
"All 2737 invalid triangles are degenerated " ) {
143 REQUIRE( nb_notsimplex == nb_degenerated );
144 REQUIRE( nb_degenerated == 2737 );
146 THEN(
"There are 12888 valid triangles" ) {
147 REQUIRE( nb_unitary + nb_common == 12888 );
149 THEN(
"There are fewer (1920) unitary triangles than common triangles (10968)" ) {
152 REQUIRE( nb_unitary < nb_common );
154 THEN(
"The total number of triangles (unitary, common, degenerated) is (domain size)^3, i.e. 5^6" ) {
155 REQUIRE( nb_unitary + nb_common + nb_degenerated == 5*5*5*5*5*5 );
158 WHEN(
"Computing all triangles in domain (0,0)-(4,4)." ) {
159 unsigned int nbsimplex= 0;
160 unsigned int nb0 = 0;
161 unsigned int nb1 = 0;
162 unsigned int nb2 = 0;
163 unsigned int nb01_not2 = 0;
168 if ( ! ( ( a < b ) && ( b < c ) ) )
continue;
169 if ( ! dconv.isSimplexFullDimensional( { a, b, c } ) )
continue;
170 auto triangle = dconv.makeSimplex( { a, b, c } );
171 bool cvx0 = dconv.isKConvex( triangle, 0 );
172 bool cvx1 = dconv.isKConvex( triangle, 1 );
173 bool cvx2 = dconv.isKConvex( triangle, 2 );
178 nb01_not2 += ( cvx0 && cvx1 && ! cvx2 ) ? 1 : 0;
180 THEN(
"All valid triangles are 0-convex." ) {
183 THEN(
"There are less 1-convex and 2-convex than 0-convex." ) {
187 THEN(
"When the triangle is 0-convex and 1-convex, then it is 2-convex." ) {
193 SCENARIO(
"DigitalConvexity< Z3 > fully convex tetrahedra",
"[convex_simplices][3d]" )
202 DConvexity dconv(
Point( -1, -1, -1 ),
Point( 4, 4, 4 ) );
204 WHEN(
"Computing all lexicographically ordered tetrahedra anchored at (0,0,0) in domain (0,0,0)-(3,3,3)." ) {
205 unsigned int nb_notsimplex = 0;
206 unsigned int nb_invalid = 0;
207 unsigned int nb_degenerated= 0;
208 unsigned int nb_common = 0;
209 unsigned int nb_unitary = 0;
215 if ( ! ( ( a < b ) && ( b < c ) && ( c < d ) ) )
continue;
216 nb_notsimplex += ! dconv.isSimplexFullDimensional( {a,b,c,d} ) ? 1 : 0;
217 auto tri_type = dconv.simplexType( { a, b, c, d } );
218 nb_degenerated += tri_type == DConvexity::SimplexType::DEGENERATED ? 1 : 0;
219 nb_invalid += tri_type == DConvexity::SimplexType::INVALID ? 1 : 0;
220 nb_unitary += tri_type == DConvexity::SimplexType::UNITARY ? 1 : 0;
221 nb_common += tri_type == DConvexity::SimplexType::COMMON ? 1 : 0;
223 THEN(
"All 4228 invalid tetrahedra are degenerated " ) {
225 REQUIRE( nb_notsimplex == nb_degenerated );
226 REQUIRE( nb_degenerated == 4228 );
228 THEN(
"There are 35483 valid tetrahedra" ) {
229 REQUIRE( nb_unitary + nb_common == 35483 );
231 THEN(
"There are fewer (2515) unitary triangles than common triangles (32968)" ) {
234 REQUIRE( nb_unitary < nb_common );
236 THEN(
"The total number of triangles (unitary, common, degenerated) is 39711" ) {
237 REQUIRE( nb_unitary + nb_common + nb_degenerated == 39711 );
240 WHEN(
"Computing many tetrahedra in domain (0,0,0)-(4,4,4)." ) {
241 const unsigned int nb = 100;
242 unsigned int nbsimplex= 0;
243 unsigned int nb0 = 0;
244 unsigned int nb1 = 0;
245 unsigned int nb2 = 0;
246 unsigned int nb3 = 0;
247 unsigned int nb012_not3 = 0;
248 unsigned int nbf = 0;
249 unsigned int nb0123 = 0;
250 for (
unsigned int i = 0; i < nb; ++i )
252 Point a( rand() % 5, rand() % 5, rand() % 5 );
253 Point b( rand() % 5, rand() % 5, rand() % 5 );
254 Point c( rand() % 5, rand() % 5, rand() % 5 );
255 Point d( rand() % 5, rand() % 5, rand() % 5 );
256 if ( ! dconv.isSimplexFullDimensional( { a, b, c, d } ) )
continue;
257 auto tetra = dconv.makeSimplex( { a, b, c, d } );
258 bool cvx0 = dconv.isKConvex( tetra, 0 );
259 bool cvx1 = dconv.isKConvex( tetra, 1 );
260 bool cvx2 = dconv.isKConvex( tetra, 2 );
261 bool cvx3 = dconv.isKConvex( tetra, 3 );
262 bool cvxf = dconv.isFullyConvex( tetra );
269 nb0123 += ( cvx0 && cvx1 && cvx2 && cvx3 ) ? 1 : 0;
270 nb012_not3+= ( cvx0 && cvx1 && cvx2 && ! cvx3 ) ? 1 : 0;
272 THEN(
"All valid tetrahedra are 0-convex." ) {
275 THEN(
"There are less 1-convex, 2-convex and 3-convex than 0-convex." ) {
280 THEN(
"When the tetrahedron is 0-convex, 1-convex and 2-convex, then it is 3-convex." ) {
289 SCENARIO(
"DigitalConvexity< Z3 > rational fully convex tetrahedra",
"[convex_simplices][3d][rational]" )
296 DConvexity dconv(
Point( -1, -1, -1 ),
Point( 10, 10, 10 ) );
297 WHEN(
"Computing many tetrahedra in domain (0,0,0)-(4,4,4)." ) {
298 const unsigned int nb = 100;
299 unsigned int nbsimplex= 0;
300 unsigned int nb0 = 0;
301 unsigned int nb1 = 0;
302 unsigned int nb2 = 0;
303 unsigned int nb3 = 0;
304 unsigned int nb012_not3 = 0;
305 unsigned int nbf = 0;
306 unsigned int nb0123 = 0;
307 for (
unsigned int i = 0; i < nb; ++i )
309 Point a( 2*(rand() % 10), rand() % 20, 2*(rand() % 10) );
310 Point b( rand() % 20, 2*(rand() % 10), 2*(rand() % 10) );
311 Point c( 2*(rand() % 10), 2*(rand() % 10), rand() % 20 );
312 Point d( 2*(rand() % 10), 2*(rand() % 10), 2*(rand() % 10) );
313 if ( ! dconv.isSimplexFullDimensional( { a, b, c, d } ) )
continue;
314 auto tetra = dconv.makeRationalSimplex( {
Point(2,2,2), a, b, c, d } );
315 bool cvx0 = dconv.isKConvex( tetra, 0 );
316 bool cvx1 = dconv.isKConvex( tetra, 1 );
317 bool cvx2 = dconv.isKConvex( tetra, 2 );
318 bool cvx3 = dconv.isKConvex( tetra, 3 );
319 bool cvxf = dconv.isFullyConvex( tetra );
326 nb0123 += ( cvx0 && cvx1 && cvx2 && cvx3 ) ? 1 : 0;
327 nb012_not3+= ( cvx0 && cvx1 && cvx2 && ! cvx3 ) ? 1 : 0;
329 THEN(
"All valid tetrahedra are 0-convex." ) {
332 THEN(
"There are less 1-convex, 2-convex and 3-convex than 0-convex." ) {
337 THEN(
"When the tetrahedron is 0-convex, 1-convex and 2-convex, then it is 3-convex." ) {
352 SCENARIO(
"DigitalConvexity< Z2 > rational fully convex tetrahedra",
"[convex_simplices][2d][rational]" )
359 DConvexity dconv(
Point( -1, -1 ),
Point( 10, 10 ) );
360 WHEN(
"Computing many triangle in domain (0,0)-(9,9)." ) {
361 const unsigned int nb = 100;
362 unsigned int nbsimplex= 0;
363 unsigned int nb0 = 0;
364 unsigned int nb1 = 0;
365 unsigned int nb2 = 0;
366 unsigned int nb01_not2 = 0;
367 unsigned int nbf = 0;
368 unsigned int nb012 = 0;
369 for (
unsigned int i = 0; i < nb; ++i )
371 Point a( 2*(rand() % 10), rand() % 20 );
372 Point b( rand() % 20 , 2*(rand() % 10) );
373 Point c( 2*(rand() % 10), 2*(rand() % 10) );
374 if ( ! dconv.isSimplexFullDimensional( { a, b, c } ) )
continue;
375 auto tetra = dconv.makeRationalSimplex( {
Point(2,2), a, b, c } );
376 bool cvx0 = dconv.isKConvex( tetra, 0 );
377 bool cvx1 = dconv.isKConvex( tetra, 1 );
378 bool cvx2 = dconv.isKConvex( tetra, 2 );
379 bool cvxf = dconv.isFullyConvex( tetra );
385 nb012 += ( cvx0 && cvx1 && cvx2 ) ? 1 : 0;
386 nb01_not2 += ( cvx0 && cvx1 && ! cvx2 ) ? 1 : 0;
388 THEN(
"All valid tetrahedra are 0-convex." ) {
391 THEN(
"There are less 1-convex, 2-convex than 0-convex." ) {
395 THEN(
"When the tetrahedron is 0-convex, and 1-convex, then it is 2-convex." ) {
408 SCENARIO(
"DigitalConvexity< Z3 > full subconvexity of segments and triangles",
"[subconvexity][3d]" )
417 DConvexity dconv(
Point( -6, -6, -6 ),
Point( 6, 6, 6 ) );
419 WHEN(
"Computing many tetrahedra" ) {
420 const unsigned int nb = 100;
421 unsigned int nb_fulldim = 0;
422 unsigned int nb_ok_seg = 0;
423 unsigned int nb_ok_tri = 0;
424 for (
unsigned int l = 0; l < nb; ++l )
426 const Point a { (rand() % 10 - 5), (rand() % 10 - 5), (rand() % 10 - 5) };
427 const Point b { (rand() % 10 - 5), (rand() % 10 - 5), (rand() % 10 - 5) };
428 const Point c { (rand() % 10 - 5), (rand() % 10 - 5), (rand() % 10 - 5) };
429 const Point d { (rand() % 10 - 5), (rand() % 10 - 5), (rand() % 10 - 5) };
430 const std::vector<Point> pts = { a, b, c, d };
431 const bool fulldim = dconv.isSimplexFullDimensional(pts.cbegin(), pts.cend());
432 nb_fulldim += fulldim ? 1 : 0;
433 if ( ! fulldim )
continue;
434 auto simplex = dconv.makeSimplex( pts.cbegin(), pts.cend() );
435 auto cover = dconv.makeCellCover( simplex, 0, 3 );
437 unsigned int nb_subconvex = 0;
438 unsigned int nb_total = 0;
439 for (
unsigned int i = 0; i < 4; i++ )
440 for (
unsigned int j = i+1; j < 4; j++ )
442 auto segment = dconv.makeSimplex( { pts[ i ], pts[ j ] } );
443 bool ok = dconv.isFullySubconvex( segment, cover );
444 nb_subconvex += ok ? 1 : 0;
447 trace.
info() <<
"****** SEGMENT NOT SUBCONVEX ******" << std::endl;
448 trace.
info() <<
"splx v =" << a << b << c << d << std::endl;
449 trace.
info() <<
"simplex=" << simplex << std::endl;
450 trace.
info() <<
"seg v =" << pts[ i ] << pts[ j ] << std::endl;
451 trace.
info() <<
"segment=" << segment << std::endl;
454 nb_ok_seg += ( nb_subconvex == nb_total ) ? 1 : 0;
457 unsigned int nb_subconvex = 0;
458 unsigned int nb_total = 0;
459 for (
unsigned int i = 0; i < 4; i++ )
460 for (
unsigned int j = i+1; j < 4; j++ )
461 for (
unsigned int k = j+1; k < 4; k++ )
463 auto triangle = dconv.makeSimplex({ pts[ i ], pts[ j ], pts[ k ] });
464 bool ok = dconv.isFullySubconvex( triangle, cover );
465 nb_subconvex += ok ? 1 : 0;
468 trace.
info() <<
"****** TRIANGLE NOT SUBCONVEX ****" << std::endl;
469 trace.
info() <<
"splx v =" << a << b << c << d << std::endl;
470 trace.
info() <<
"simplex=" << simplex << std::endl;
471 trace.
info() <<
"tri v =" << pts[ i ] << pts[ j ]
472 << pts[ k ] << std::endl;
473 trace.
info() <<
"triangle=" << triangle << std::endl;
476 nb_ok_tri += ( nb_subconvex == nb_total ) ? 1 : 0;
479 THEN(
"At least half the tetrahedra are full dimensional." ) {
480 REQUIRE( nb_fulldim >= nb / 2 );
482 THEN(
"All segments of a tetrahedron should be subconvex to it." ) {
483 REQUIRE( nb_ok_seg == nb_fulldim );
485 THEN(
"All triangles of a tetrahedron should be subconvex to it." ) {
486 REQUIRE( nb_ok_tri == nb_fulldim );
Aim: A helper class to build polytopes from digital sets and to check digital k-convexity.
Aim: This class is a model of CCellularGridSpaceND. It represents the cubical grid as a cell complex,...
DGtal is the top-level namespace which contains all DGtal functions and types.
GIVEN("A cubical complex with random 3-cells")
SCENARIO("DigitalConvexity< Z2 > unit tests", "[digital_convexity][2d]")
HyperRectDomain< Space > Domain
REQUIRE(domain.isInside(aPoint))