DGtal 1.4.0
Loading...
Searching...
No Matches
Functions
testQuickHull.cpp File Reference
DGtal Test Files
#include <iostream>
#include <vector>
#include <algorithm>
#include "DGtal/base/Common.h"
#include "DGtal/kernel/SpaceND.h"
#include "DGtal/geometry/tools/QuickHull.h"
#include "DGtalCatch.h"
Include dependency graph for testQuickHull.cpp:

Go to the source code of this file.

Functions

template<typename Point >
std::vector< Point > randomPointsInBall (int nb, int R)
 
 SCENARIO ("QuickHull< ConvexHullIntegralKernel< 2 > > unit tests", "[quickhull][integral_kernel][2d]")
 
 SCENARIO ("QuickHull< ConvexHullIntegralKernel< 3 > > unit tests", "[quickhull][integral_kernel][3d]")
 
 SCENARIO ("QuickHull< ConvexHullIntegralKernel< 4 > > unit tests", "[quickhull][integral_kernel][4d]")
 

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
2020/02/01

Functions for testing class QuickHull.

This file is part of the DGtal library.

Definition in file testQuickHull.cpp.

Function Documentation

◆ randomPointsInBall()

template<typename Point >
std::vector< Point > randomPointsInBall ( int nb,
int R )
Examples
geometry/tools/checkLatticeBallQuickHull.cpp.

Definition at line 45 of file testQuickHull.cpp.

46{
47 std::vector< Point > V;
48 Point c = Point::diagonal( R );
49 double R2 = (double) R * (double) R;
50 for ( int i = 0; i < nb; ) {
51 Point p;
52 for ( DGtal::Dimension k = 0; k < Point::dimension; ++k )
53 p[ k ] = rand() % (2*R);
54 if ( ( p - c ).squaredNorm() < R2 ) { V.push_back( p ); i++; }
55 }
56 return V;
57}
DGtal::Dimension
DGtal::uint32_t Dimension
Definition Common.h:136
Point
MyPointD Point
Definition testClone2.cpp:383

References DGtal::R.

Referenced by SCENARIO(), SCENARIO(), and SCENARIO().

◆ SCENARIO() [1/3]

SCENARIO ( "QuickHull< ConvexHullIntegralKernel< 2 > > unit tests" ,
"" [quickhull][integral_kernel][2d] )

Definition at line 63 of file testQuickHull.cpp.

64{
65 typedef ConvexHullIntegralKernel< 2 > QHKernel;
66 typedef QuickHull< QHKernel > QHull;
67 typedef SpaceND< 2, int > Space;
68 typedef Space::Point Point;
69 typedef QHull::Index Index;
70 typedef QHull::IndexRange IndexRange;
71
72
73 GIVEN( "Given a star { (0,0), (-4,-1), (-3,5), (7,3), (5, -2) } " ) {
74 std::vector<Point> V
75 = { Point(0,0), Point(-4,-1), Point(-3,5), Point(7,3), Point(5, -2) };
76 QHull hull;
77 hull.setInput( V, false );
78 hull.computeConvexHull();
79 THEN( "The convex hull is valid and contains every point" ) {
80 REQUIRE( hull.check() );
81 }
82 THEN( "Its convex hull has 4 vertices" ) {
83 REQUIRE( hull.nbVertices() == 4 );
84 }
85 THEN( "Its convex hull has 4 facets" ) {
86 REQUIRE( hull.nbFacets() == 4 );
87 }
88 THEN( "Its facets form a linked list" ) {
89 std::vector< IndexRange > facets;
90 hull.getFacetVertices( facets );
91 std::vector< Index > next( hull.nbVertices(), (Index) -1 );
92 Index nb_zero_next = hull.nbVertices();
93 Index nb_two_next = 0;
94 for ( auto f : facets ) {
95 if ( next[ f[ 0 ] ] != (Index) -1 ) nb_two_next += 1;
96 else {
97 next[ f[ 0 ] ] = f[ 1 ];
98 nb_zero_next -= 1;
99 }
100 }
101 REQUIRE( nb_zero_next == 0 );
102 REQUIRE( nb_two_next == 0 );
103 }
104 }
105 GIVEN( "Given 100 random point in a ball of radius 50 " ) {
106 std::vector<Point> V = randomPointsInBall< Point >( 100, 50 );
107 QHull hull;
108 hull.setInput( V, false );
109 hull.computeConvexHull();
110 THEN( "The convex hull is valid and contains every point" ) {
111 REQUIRE( hull.check() );
112 }
113 THEN( "Its convex hull has the same number of vertices and facets" ) {
114 REQUIRE( hull.nbVertices() == hull.nbFacets() );
115 }
116 THEN( "Its convex hull has much fewer vertices than input points" ) {
117 REQUIRE( 2*hull.nbVertices() <= hull.nbPoints() );
118 }
119 THEN( "Its facets form a linked list" ) {
120 std::vector< IndexRange > facets;
121 hull.getFacetVertices( facets );
122 std::vector< Index > next( hull.nbVertices(), (Index) -1 );
123 Index nb_zero_next = hull.nbVertices();
124 Index nb_two_next = 0;
125 for ( auto f : facets ) {
126 if ( next[ f[ 0 ] ] != (Index) -1 ) nb_two_next += 1;
127 else {
128 next[ f[ 0 ] ] = f[ 1 ];
129 nb_zero_next -= 1;
130 }
131 }
132 REQUIRE( nb_zero_next == 0 );
133 REQUIRE( nb_two_next == 0 );
134 }
135 }
136}
Index
SMesh::Index Index
Definition fullConvexitySphereGeodesics.cpp:117
DGtal::ConvexHullIntegralKernel
Aim: a geometric kernel to compute the convex hull of digital points with integer-only arithmetic.
Definition QuickHullKernels.h:377
DGtal::QuickHull
Aim: Implements the quickhull algorithm by Barber et al. barber1996, a famous arbitrary dimensional c...
Definition QuickHull.h:140
GIVEN
GIVEN("A cubical complex with random 3-cells")
Definition testCubicalComplex.cpp:70
randomPointsInBall
std::vector< Point > randomPointsInBall(int nb, int R)
Definition testQuickHull.cpp:45
REQUIRE
REQUIRE(domain.isInside(aPoint))

References GIVEN(), randomPointsInBall(), and REQUIRE().

◆ SCENARIO() [2/3]

SCENARIO ( "QuickHull< ConvexHullIntegralKernel< 3 > > unit tests" ,
"" [quickhull][integral_kernel][3d] )

Definition at line 143 of file testQuickHull.cpp.

144{
145 typedef ConvexHullIntegralKernel< 3 > QHKernel;
146 typedef QuickHull< QHKernel > QHull;
147 typedef SpaceND< 3, int > Space;
148 typedef Space::Point Point;
149 typedef QHull::IndexRange IndexRange;
150
151
152 GIVEN( "Given an octahedron" ) {
153 const int R = 5;
154 std::vector<Point> V = { Point( 0,0,0 ) };
155 for ( Dimension k = 0; k < 3; ++k ) {
156 V.push_back( Point::base( k, R ) );
157 V.push_back( Point::base( k, -R ) );
158 }
159 QHull hull;
160 hull.setInput( V, false );
161 hull.setInitialSimplex( IndexRange { 0, 1, 3, 5 } );
162 hull.computeConvexHull();
163 THEN( "The convex hull is valid and contains every point" ) {
164 REQUIRE( hull.check() );
165 }
166 THEN( "Its convex hull has 6 vertices" ) {
167 REQUIRE( hull.nbVertices() == 6 );
168 }
169 THEN( "Its convex hull has 8 facets" ) {
170 REQUIRE( hull.nbFacets() == 8 );
171 }
172 }
173 GIVEN( "Given 100 random point in a ball of radius 50 " ) {
174 std::vector<Point> V = randomPointsInBall< Point >( 100, 50 );
175 QHull hull;
176 hull.setInput( V, false );
177 hull.computeConvexHull();
178 THEN( "The convex hull is valid and contains every point" ) {
179 REQUIRE( hull.check() );
180 }
181 THEN( "Its convex hull has more facets than vertices" ) {
182 REQUIRE( hull.nbVertices() < hull.nbFacets() );
183 }
184 THEN( "Its convex hull has fewer vertices than input points" ) {
185 REQUIRE( hull.nbVertices() < hull.nbPoints() );
186 }
187 }
188}

References GIVEN(), DGtal::R, randomPointsInBall(), and REQUIRE().

◆ SCENARIO() [3/3]

SCENARIO ( "QuickHull< ConvexHullIntegralKernel< 4 > > unit tests" ,
"" [quickhull][integral_kernel][4d] )

Definition at line 195 of file testQuickHull.cpp.

196{
197 typedef ConvexHullIntegralKernel< 4 > QHKernel;
198 typedef QuickHull< QHKernel > QHull;
199 typedef SpaceND< 4, int > Space;
200 typedef Space::Point Point;
201
202
203 GIVEN( "Given an octahedron" ) {
204 const int R = 5;
205 std::vector<Point> V = { Point( 0,0,0,0 ) };
206 for ( Dimension k = 0; k < 4; ++k ) {
207 V.push_back( Point::base( k, R ) );
208 V.push_back( Point::base( k, -R ) );
209 }
210 QHull hull;
211 hull.setInput( V, false );
212 hull.computeConvexHull();
213 THEN( "The convex hull is valid and contains every point" ) {
214 REQUIRE( hull.check() );
215 }
216 THEN( "Its convex hull has 8 vertices" ) {
217 REQUIRE( hull.nbVertices() == 8 );
218 }
219 THEN( "Its convex hull has 16 facets" ) {
220 REQUIRE( hull.nbFacets() == 16 );
221 }
222 }
223 GIVEN( "Given 100 random point in a ball of radius 50 " ) {
224 std::vector<Point> V = randomPointsInBall< Point >( 100, 50 );
225 QHull hull;
226 hull.setInput( V, false );
227 hull.computeConvexHull();
228 THEN( "The convex hull is valid and contains every point" ) {
229 REQUIRE( hull.check() );
230 }
231 THEN( "Its convex hull has fewer vertices than input points" ) {
232 REQUIRE( hull.nbVertices() < hull.nbPoints() );
233 }
234 }
235}

References GIVEN(), DGtal::R, randomPointsInBall(), and REQUIRE().