34#include "DGtal/base/Common.h"
35#include "DGtal/kernel/SpaceND.h"
36#include "DGtal/geometry/volumes/ConvexityHelper.h"
37#include "DGtal/shapes/SurfaceMesh.h"
38#include "DGtalCatch.h"
50 "[convexity_helper][lattice_polytope][2d]" )
53 typedef Helper::Point
Point;
55 GIVEN(
"Given a star { (0,0), (-4,-1), (-3,5), (7,3), (5, -2) } " ) {
58 WHEN(
"Computing its lattice polytope" ){
59 const auto P = Helper::computeLatticePolytope( V,
false,
true );
61 THEN(
"The polytope is valid and has 4 non trivial facets" ) {
62 REQUIRE( P.nbHalfSpaces() - 4 == 4 );
64 THEN(
"The polytope is Minkowski summable" ) {
67 THEN(
"The polytope contains the input points" ) {
68 REQUIRE( P.isInside( V[ 0 ] ) );
69 REQUIRE( P.isInside( V[ 1 ] ) );
70 REQUIRE( P.isInside( V[ 2 ] ) );
71 REQUIRE( P.isInside( V[ 3 ] ) );
72 REQUIRE( P.isInside( V[ 4 ] ) );
74 THEN(
"The polytope contains 58 points" ) {
77 THEN(
"The interior of the polytope contains 53 points" ) {
78 REQUIRE( P.countInterior() == 53 );
80 THEN(
"The boundary of the polytope contains 5 points" ) {
81 REQUIRE( P.countBoundary() == 5 );
85 GIVEN(
"Given a square with an additional outside vertex " ) {
89 WHEN(
"Computing its Delaunay cell complex" ){
90 CvxCellComplex complex;
91 bool ok = Helper::computeDelaunayCellComplex( complex, V,
false );
93 THEN(
"The complex has 2 cells, 6 faces, 5 vertices" ) {
95 REQUIRE( complex.nbCells() == 2 );
96 REQUIRE( complex.nbFaces() == 6 );
97 REQUIRE( complex.nbVertices() == 5 );
99 THEN(
"The faces of cells are finite" ) {
100 bool ok_finite =
true;
101 for (
auto c = 0; c < complex.nbCells(); ++c ) {
102 const auto faces = complex.cellFaces( c );
103 for (
auto f : faces )
104 ok_finite = ok_finite && ! complex.isInfinite( complex.faceCell( f ) );
108 THEN(
"The opposite of faces of cells are infinite except two" ) {
110 for (
auto c = 0; c < complex.nbCells(); ++c ) {
111 const auto faces = complex.cellFaces( c );
112 for (
auto f : faces ) {
113 const auto opp_f = complex.opposite( f );
114 nb_finite += complex.isInfinite( complex.faceCell( opp_f ) ) ? 0 : 1;
121 GIVEN(
"Given a degenerated polytope { (0,0), (3,-1), (9,-3), (-6,2) } " ) {
124 WHEN(
"Computing its lattice polytope" ){
125 const auto P = Helper::computeLatticePolytope( V,
false,
true );
127 THEN(
"The polytope is valid and has 2 non trivial facets" ) {
128 REQUIRE( P.nbHalfSpaces() - 4 == 2 );
130 THEN(
"The polytope contains 6 points" ) {
133 THEN(
"The polytope contains no interior points" ) {
134 REQUIRE( P.countInterior() == 0 );
137 WHEN(
"Computing the vertices of its convex hull" ){
138 auto X = Helper::computeConvexHullVertices( V,
false );
139 std::sort( X.begin(), X.end() );
141 THEN(
"The polytope is a segment defined by two points" ) {
148 GIVEN(
"Given a degenerated simplex { (4,0), (7,2), (-5,-6) } " ) {
151 WHEN(
"Computing its lattice polytope" ){
152 const auto P = Helper::computeLatticePolytope( V,
false,
true );
154 THEN(
"The polytope is valid and has 2 non trivial facets" ) {
155 REQUIRE( P.nbHalfSpaces() - 4 == 2 );
157 THEN(
"The polytope contains 5 points" ) {
160 THEN(
"The polytope contains no interior points" ) {
161 REQUIRE( P.countInterior() == 0 );
164 WHEN(
"Computing the vertices of its convex hull" ){
165 auto X = Helper::computeConvexHullVertices( V,
false );
166 std::sort( X.begin(), X.end() );
168 THEN(
"The polytope is a segment defined by two points" ) {
182 "[convexity_helper][3d]" )
185 typedef Helper::Point
Point;
191 GIVEN(
"Given an octahedron star { (0,0,0), (-2,0,0), (2,0,0), (0,-2,0), (0,2,0), (0,0,-2), (0,0,2) } " ) {
193 = {
Point(0,0,0),
Point(-2,0,0),
Point(2,0,0),
Point(0,-2,0),
Point(0,2,0),
195 WHEN(
"Computing its lattice polytope" ){
196 const auto P = Helper::computeLatticePolytope( V,
false,
true );
198 THEN(
"The polytope is valid and has 8 non trivial facets plus 12 edge constraints" ) {
199 REQUIRE( P.nbHalfSpaces() - 6 == 20 );
201 THEN(
"The polytope is Minkowski summable" ) {
204 THEN(
"The polytope contains the input points" ) {
205 REQUIRE( P.isInside( V[ 0 ] ) );
206 REQUIRE( P.isInside( V[ 1 ] ) );
207 REQUIRE( P.isInside( V[ 2 ] ) );
208 REQUIRE( P.isInside( V[ 3 ] ) );
209 REQUIRE( P.isInside( V[ 4 ] ) );
210 REQUIRE( P.isInside( V[ 5 ] ) );
211 REQUIRE( P.isInside( V[ 6 ] ) );
213 THEN(
"The polytope contains 25 points" ) {
216 THEN(
"The interior of the polytope contains 7 points" ) {
217 REQUIRE( P.countInterior() == 7 );
219 THEN(
"The boundary of the polytope contains 18 points" ) {
220 REQUIRE( P.countBoundary() == 18 );
223 WHEN(
"Computing the boundary of its convex hull as a SurfaceMesh" ){
225 bool ok = Helper::computeConvexHullBoundary( smesh, V,
false );
227 THEN(
"The surface mesh is valid and has 6 vertices, 12 edges and 8 faces" ) {
233 THEN(
"The surface mesh has the topology of a sphere" ) {
239 WHEN(
"Computing the boundary of its convex hull as a lattice PolygonalSurface" ){
240 LatticePolySurf lpsurf;
241 bool ok = Helper::computeConvexHullBoundary( lpsurf, V,
false );
243 THEN(
"The polygonal surface is valid and has 6 vertices, 12 edges and 8 faces" ) {
245 REQUIRE( lpsurf.nbVertices() == 6 );
246 REQUIRE( lpsurf.nbEdges() == 12 );
247 REQUIRE( lpsurf.nbFaces() == 8 );
248 REQUIRE( lpsurf.nbArcs() == 24 );
250 THEN(
"The polygonal surface has the topology of a sphere and no boundary" ) {
251 REQUIRE( lpsurf.Euler() == 2 );
252 REQUIRE( lpsurf.allBoundaryArcs().size() == 0 );
253 REQUIRE( lpsurf.allBoundaryVertices().size() == 0 );
256 WHEN(
"Computing its convex hull as a ConvexCellComplex" ){
257 CvxCellComplex complex;
258 bool ok = Helper::computeConvexHullCellComplex( complex, V,
false );
260 THEN(
"The convex cell complex is valid and has 6 vertices, 8 faces and 1 finite cell" ) {
262 REQUIRE( complex.nbVertices() == 6 );
263 REQUIRE( complex.nbFaces() == 8 );
264 REQUIRE( complex.nbCells() == 1 );
267 WHEN(
"Computing the vertices of its convex hull" ){
268 const auto X = Helper::computeConvexHullVertices( V,
false );
270 THEN(
"The polytope has 6 vertices" ) {
275 GIVEN(
"Given a cube with an additional outside vertex " ) {
277 = {
Point(-10,-10,-10),
Point(10,-10,-10),
Point(-10,10,-10),
Point(10,10,-10),
278 Point(-10,-10,10),
Point(10,-10,10),
Point(-10,10,10),
Point(10,10,10),
280 WHEN(
"Computing its Delaunay cell complex" ){
281 CvxCellComplex complex;
282 bool ok = Helper::computeDelaunayCellComplex( complex, V,
false );
284 THEN(
"The complex has 2 cells, 10 faces, 9 vertices" ) {
286 REQUIRE( complex.nbCells() == 2 );
287 REQUIRE( complex.nbFaces() == 10 );
288 REQUIRE( complex.nbVertices() == 9 );
290 THEN(
"The faces of cells are finite" ) {
291 bool ok_finite =
true;
292 for (
auto c = 0; c < complex.nbCells(); ++c ) {
293 const auto faces = complex.cellFaces( c );
294 for (
auto f : faces )
295 ok_finite = ok_finite && ! complex.isInfinite( complex.faceCell( f ) );
299 THEN(
"The opposite of faces of cells are infinite except two" ) {
301 for (
auto c = 0; c < complex.nbCells(); ++c ) {
302 const auto faces = complex.cellFaces( c );
303 for (
auto f : faces ) {
304 const auto opp_f = complex.opposite( f );
305 nb_finite += complex.isInfinite( complex.faceCell( opp_f ) ) ? 0 : 1;
311 WHEN(
"Computing the vertices of its convex hull" ){
312 const auto X = Helper::computeConvexHullVertices( V,
false );
314 THEN(
"The polytope has 9 vertices" ) {
319 GIVEN(
"Given a degenerated 1d polytope { (0,0,1), (3,-1,2), (9,-3,4), (-6,2,-1) } " ) {
321 = {
Point(0,0,1),
Point(3,-1,2),
Point(9,-3,4),
Point(-6,2,-1) };
322 WHEN(
"Computing its lattice polytope" ){
323 const auto P = Helper::computeLatticePolytope( V,
false,
true );
325 THEN(
"The polytope is valid and has 6 non trivial facets" ) {
326 REQUIRE( P.nbHalfSpaces() - 6 == 6 );
328 THEN(
"The polytope contains 6 points" ) {
331 THEN(
"The polytope contains no interior points" ) {
332 REQUIRE( P.countInterior() == 0 );
335 WHEN(
"Computing the vertices of its convex hull" ){
336 auto X = Helper::computeConvexHullVertices( V,
false );
337 std::sort( X.begin(), X.end() );
339 THEN(
"The polytope is a segment defined by two points" ) {
346 GIVEN(
"Given a degenerated 1d simplex { (1,0,-1), Point(4,-1,-2), Point(10,-3,-4) } " ) {
349 WHEN(
"Computing its lattice polytope" ){
350 const auto P = Helper::computeLatticePolytope( V,
false,
true );
352 THEN(
"The polytope is valid and has 6 non trivial facets" ) {
353 REQUIRE( P.nbHalfSpaces() - 6 == 6 );
355 THEN(
"The polytope contains 4 points" ) {
358 THEN(
"The polytope contains no interior points" ) {
359 REQUIRE( P.countInterior() == 0 );
362 WHEN(
"Computing the vertices of its convex hull" ){
363 auto X = Helper::computeConvexHullVertices( V,
false );
364 std::sort( X.begin(), X.end() );
366 THEN(
"The polytope is a segment defined by two points" ) {
373 GIVEN(
"Given a degenerated 2d polytope { (2,1,0), (1,0,1), (1,2,1), (0,1,2), (0,3,2) } " ) {
375 = {
Point(2,1,0),
Point(1,0,1),
Point(1,2,1),
Point(0,1,2),
Point(0,3,2) };
376 WHEN(
"Computing its lattice polytope" ){
377 const auto P = Helper::computeLatticePolytope( V,
false,
true );
379 THEN(
"The polytope is valid and has more than 6 non trivial facets" ) {
380 REQUIRE( P.nbHalfSpaces() - 6 == 6 );
382 THEN(
"The polytope contains 7 points" ) {
385 THEN(
"The polytope contains no interior points" ) {
386 REQUIRE( P.countInterior() == 0 );
389 WHEN(
"Computing the vertices of its convex hull" ){
390 auto X = Helper::computeConvexHullVertices( V,
false );
391 std::sort( X.begin(), X.end() );
393 THEN(
"The polytope is a quad" ) {
402 GIVEN(
"Given a degenerated 2d simplex { (2,1,0), (1,0,1), (1,5,1), (0,3,2) } " ) {
404 = {
Point(2,1,0),
Point(1,0,1),
Point(1,5,1),
Point(0,3,2) };
405 WHEN(
"Computing its lattice polytope" ){
406 const auto P = Helper::computeLatticePolytope( V,
false,
true );
408 THEN(
"The polytope is valid and has more than 6 non trivial facets" ) {
409 REQUIRE( P.nbHalfSpaces() - 6 == 6 );
411 THEN(
"The polytope contains 8 points" ) {
414 THEN(
"The polytope contains no interior points" ) {
415 REQUIRE( P.countInterior() == 0 );
418 WHEN(
"Computing the vertices of its convex hull" ){
419 auto X = Helper::computeConvexHullVertices( V,
false );
420 std::sort( X.begin(), X.end() );
422 THEN(
"The polytope is a quad" ) {
Aim: Implements basic operations that will be used in Point and Vector classes.
Aim: Represents a polygon mesh, i.e. a 2-dimensional combinatorial surface whose faces are (topologic...
SurfaceMesh< RealPoint, RealVector > SMesh
DGtal is the top-level namespace which contains all DGtal functions and types.
Aim: represents a d-dimensional complex in a d-dimensional space with the following properties and re...
Aim: Provides a set of functions to facilitate the computation of convex hulls and polytopes,...
Aim: Represents an embedded mesh as faces and a list of vertices. Vertices may be shared among faces ...
Edges computeManifoldBoundaryEdges() const
Edges computeNonManifoldEdges() const
GIVEN("A cubical complex with random 3-cells")
REQUIRE(domain.isInside(aPoint))
SCENARIO("UnorderedSetByBlock< PointVector< 2, int > unit tests with 32 bits blocks", "[unorderedsetbyblock][2d]")