DGtal  1.4.beta
testLatticeSetByIntervals.cpp
Go to the documentation of this file.
1 
31 #include <iostream>
32 #include <vector>
33 #include <algorithm>
34 #include "DGtal/base/Common.h"
35 #include "DGtal/helpers/StdDefs.h"
36 #include "DGtal/kernel/LatticeSetByIntervals.h"
37 #include "DGtalCatch.h"
39 
40 using namespace std;
41 using namespace DGtal;
42 
43 
45 // Functions for testing class LatticeSetByIntervals.
47 
48 SCENARIO( "LatticeSetByIntervals< int > unit tests", "[lattice_set]" )
49 {
50  typedef DGtal::Z3i::Space Space;
51  typedef Space::Point Point;
52  typedef LatticeSetByIntervals< Space > LatticeSet;
53 
54  WHEN( "Inserting many points" ) {
55  std::set< Point > S;
56  LatticeSet L;
57  unsigned int nb = 10000;
58  for ( unsigned int i = 0; i < nb; i++ )
59  {
60  Point p( rand() % 20, rand() % 20, rand() % 20 );
61  S.insert( p );
62  L.insert( p );
63  }
64  auto mem_L = L.memory_usage();
65  auto mem_S = ( L.size() * ( sizeof( Point ) + sizeof( void* ) ) );
66  auto vec_L = L.toPointRange();
67  std::sort( vec_L.begin(), vec_L.end() );
68  std::vector< Point > vec_S( S.begin(), S.end() );
69  for ( size_t i = 0; i < vec_L.size(); i++ )
70  {
71  if ( vec_L[ i ] != vec_S[ i ] )
72  std::cout << i << " " << vec_L[ i ] << " != " << vec_S[ i ]
73  << std::endl;
74  }
75  THEN( "The lattice set contains the same points as std::set< Point >" ) {
76  REQUIRE( S.size() == L.size() );
77  REQUIRE( L.size() == vec_L.size() );
78  REQUIRE( std::equal( vec_L.begin(), vec_L.end(), vec_S.begin() ) );
79  }
80  THEN( "The lattice set is less costly to store than std::set< Point >" ) {
81  REQUIRE( mem_L < mem_S );
82  }
83  THEN( "One can create directly a lattice set from a range" ) {
84  LatticeSet L2( S.begin(), S.end() );
85  REQUIRE( L2.size() == S.size() );
86  }
87  THEN( "When erasing all elements from the lattice set, it becomes empty" ) {
88  LatticeSet L2( S.begin(), S.end() );
89  for ( auto&& p : S )
90  L2.erase( p );
91  REQUIRE( L2.empty() );
92  REQUIRE( L2.data().empty() );
93  }
94  }
95 }
96 
97 SCENARIO( "LatticeSetByIntervals< int > set operations tests", "[lattice_set]" )
98 {
99  typedef DGtal::Z3i::Space Space;
100  typedef Space::Point Point;
101  typedef LatticeSetByIntervals< Space > LatticeSet;
102 
103  std::set< Point > X,Y;
104  int nb = 300000;
105  int R = 50;
106  for ( auto i = 0; i < nb; i++ )
107  {
108  Point p( rand() % R, rand() % R, rand() % R );
109  X.insert( p );
110  Point q( rand() % R, rand() % R, rand() % R );
111  Y.insert( q );
112  }
113  LatticeSet A( X.cbegin(), X.cend() );
114  LatticeSet B( Y.cbegin(), Y.cend() );
115  std::vector< Point > X_cup_Y, X_cap_Y, X_minus_Y, X_delta_Y;
116  Clock c;
117  c.startClock();
118  std::set_union( X.cbegin(), X.cend(), Y.cbegin(), Y.cend(),
119  std::back_inserter( X_cup_Y ) );
120  std::set_intersection( X.cbegin(), X.cend(), Y.cbegin(), Y.cend(),
121  std::back_inserter( X_cap_Y ) );
122  std::set_difference( X.cbegin(), X.cend(), Y.cbegin(), Y.cend(),
123  std::back_inserter( X_minus_Y ) );
124  std::set_symmetric_difference( X.cbegin(), X.cend(), Y.cbegin(), Y.cend(),
125  std::back_inserter( X_delta_Y ) );
126  auto tv = c.stopClock();
127 
128  c.startClock();
129  LatticeSet A_cup_B = A.set_union( B );
130  LatticeSet A_cap_B = A.set_intersection( B );
131  LatticeSet A_minus_B = A.set_difference( B );
132  LatticeSet A_delta_B = A.set_symmetric_difference( B );
133  auto tl = c.stopClock();
134  THEN( "Lattice sets can be constructed from sets" ) {
135  REQUIRE( X.size() == A.size() );
136  REQUIRE( Y.size() == B.size() );
137  }
138  THEN( "Set operations on lattice sets are correct" ) {
139  REQUIRE( X_cup_Y.size() == A_cup_B.size() );
140  REQUIRE( X_cap_Y.size() == A_cap_B.size() );
141  REQUIRE( X_minus_Y.size() == A_minus_B.size() );
142  REQUIRE( X_delta_Y.size() == A_delta_B.size() );
143  }
144  THEN( "Set operations on lattice sets are faster" ) {
145  REQUIRE( tl < tv );
146  }
147  THEN( "Inclusions are correct" ) {
148  REQUIRE( ! A.equals( B ) );
149  REQUIRE( A_cup_B.equals( A_cup_B ) );
150  REQUIRE( A_cup_B.includes( A_cup_B ) );
151  REQUIRE( A_cup_B.includes( A ) );
152  REQUIRE( ! A_cup_B.equals( A ) );
153  REQUIRE( ! A.includes( A_cup_B ) );
154  REQUIRE( A_cup_B.includes( B ) );
155  REQUIRE( ! B.includes( A_cup_B ) );
156  REQUIRE( ! A_cup_B.equals( B ) );
157  REQUIRE( A_cup_B.includes( A_cap_B ) );
158  REQUIRE( ! A_cap_B.includes( A_cup_B ) );
159  REQUIRE( A.includes( A_minus_B ) );
160  REQUIRE( ! A_minus_B.includes( A ) );
161  REQUIRE( A_cup_B.includes( A_delta_B ) );
162  REQUIRE( ! A_delta_B.includes( A_cup_B ) );
163  REQUIRE( ! A.includes( A_delta_B ) );
164  REQUIRE( ! B.includes( A_delta_B ) );
165  }
166 }
167 
168 SCENARIO( "LatticeSetByIntervals< int > 3d topology operations tests", "[lattice_set][3d]" )
169 {
170  typedef DGtal::Z3i::Space Space;
171  typedef Space::Point Point;
172  typedef LatticeSetByIntervals< Space > LatticeSet;
173  WHEN( "Computing the star of n isolated points, the number of cells is 27*n, and taking its skel brings back the n points" ) {
174  std::vector< Point > X { {0,0,0}, {10,0,0}, {5,5,0}, {0,0,8} };
175  LatticeSet P( X.cbegin(), X.cend() );
176  auto StarP = P.starOfPoints();
177  auto SkelStarP = StarP.skeletonOfCells();
178  REQUIRE( P.size() == X.size() );
179  REQUIRE( StarP.size() == 27 * X.size() );
180  REQUIRE( SkelStarP.size() == X.size() );
181  }
182  WHEN( "Computing the star of n points consecutive along space diagonal, the number of cells is 26*n+1, and taking its skel brings back the n points" ) {
183  std::vector< Point > X { {0,0,0}, {1,1,1}, {2,2,2}, {3,3,3} };
184  LatticeSet P( X.cbegin(), X.cend() );
185  auto StarP = P.starOfPoints();
186  auto SkelStarP = StarP.skeletonOfCells();
187  REQUIRE( P.size() == X.size() );
188  REQUIRE( StarP.size() == ( 26 * X.size() + 1 ) );
189  REQUIRE( SkelStarP.size() == X.size() );
190  }
191  WHEN( "Computing the star of n points consecutive along any axis, the number of cells is 18*n+9, and taking its skel brings back the n points" ) {
192  std::vector< Point > X { {0,0,0}, {1,0,0}, {2,0,0}, {3,0,0} };
193  for ( Dimension a = 0; a < 3; a++ )
194  {
195  LatticeSet P( X.cbegin(), X.cend(), a );
196  auto StarP = P.starOfPoints();
197  auto SkelStarP = StarP.skeletonOfCells();
198  CAPTURE( StarP.toPointRange() );
199  CAPTURE( SkelStarP.toPointRange() );
200  CAPTURE( a );
201  REQUIRE( P.size() == X.size() );
202  REQUIRE( StarP.size() == ( 18 * X.size() + 9 ) );
203  REQUIRE( SkelStarP.size() == X.size() );
204  }
205  }
206  WHEN( "Computing the skeleton of the star of a random set of points X, Skel(Star(X)) = X" ) {
207  std::vector< Point > X;
208  for ( int i = 0; i < 1000; i++ )
209  X.push_back( Point( rand() % 10, rand() % 10, rand() % 10 ) );
210  for ( Dimension a = 0; a < 3; a++ )
211  {
212  LatticeSet P( X.cbegin(), X.cend(), a );
213  auto StarP = P.starOfPoints();
214  auto SkelStarP = StarP.skeletonOfCells();
215  REQUIRE( SkelStarP.size() == P.size() );
216  }
217  }
218  WHEN( "Computing the skeleton of an open random set of cells O, O = Star(O), Skel(O) subset O and O = Star(Skel(O))" ) {
219  std::vector< Point > X;
220  for ( int i = 0; i < 50; i++ )
221  X.push_back( Point( rand() % 5, rand() % 5, rand() % 5 ) );
222  for ( Dimension a = 0; a < 3; a++ )
223  {
224  LatticeSet C( X.cbegin(), X.cend(), a );
225  auto O = C.starOfCells();
226  auto StarO = O.starOfCells();
227  auto SkelO = O.skeletonOfCells();
228  auto StarSkelO = SkelO.starOfCells();
229  CAPTURE( O.axis() );
230  CAPTURE( O.size() );
231  CAPTURE( SkelO.size() );
232  CAPTURE( StarSkelO.size() );
233  CAPTURE( StarO.size() );
234  REQUIRE( O.includes( SkelO ) );
235  REQUIRE( StarSkelO.equals( O ) );
236  REQUIRE( StarO.equals( O ) );
237  }
238  }
239  WHEN( "Computing the skeleton of a random set of cells C, C subset Star(C), Skel(C) subset C, C subset Star(Skel(C)), Star(C) = Star(Skel(Star(C)))" ) {
240  std::vector< Point > X;
241  for ( int i = 0; i < 50; i++ )
242  X.push_back( Point( rand() % 5, rand() % 5, rand() % 5 ) );
243  for ( Dimension a = 0; a < 3; a++ )
244  {
245  LatticeSet C( X.cbegin(), X.cend(), a );
246  auto StarC = C.starOfCells();
247  auto SkelC = C.skeletonOfCells();
248  auto StarSkelC = SkelC.starOfCells();
249  auto StarSkelStarC = StarC.skeletonOfCells().starOfCells();
250  CAPTURE( C.axis() );
251  CAPTURE( C.size() );
252  CAPTURE( SkelC.size() );
253  CAPTURE( StarSkelC.size() );
254  CAPTURE( StarC.size() );
255  CAPTURE( StarSkelStarC.size() );
256  REQUIRE( StarC.includes( C ) );
257  REQUIRE( C.includes( SkelC) );
258  REQUIRE( StarSkelC.includes( C ) );
259  REQUIRE( StarSkelStarC.equals( StarC ) );
260  }
261  }
262 }
263 
264 SCENARIO( "LatticeSetByIntervals< int > 2d topology operations tests", "[lattice_set][2d]" )
265 {
266  typedef DGtal::Z2i::Space Space;
267  typedef Space::Point Point;
268  typedef LatticeSetByIntervals< Space > LatticeSet;
269  WHEN( "Computing the skeleton of an open random set of cells O, O = Star(O), Skel(O) subset O and O = Star(Skel(O))" ) {
270  std::vector< Point > X;
271  for ( int i = 0; i < 30; i++ )
272  X.push_back( Point( rand() % 10, rand() % 10 ) );
273  for ( Dimension a = 0; a < 2; a++ )
274  {
275  LatticeSet C( X.cbegin(), X.cend(), a );
276  auto O = C.starOfCells();
277  auto StarO = O.starOfCells();
278  auto SkelO = O.skeletonOfCells();
279  auto StarSkelO = SkelO.starOfCells();
280  auto debug = StarO.set_symmetric_difference( O );
281  CAPTURE( O.axis() );
282  CAPTURE( O.size() );
283  CAPTURE( StarO.size() );
284  CAPTURE( SkelO.size() );
285  CAPTURE( StarSkelO.size() );
286  CAPTURE( O.toPointRange() );
287  CAPTURE( StarO.toPointRange() );
288  CAPTURE( SkelO.toPointRange() );
289  CAPTURE( StarSkelO.toPointRange() );
290  CAPTURE( debug.toPointRange() );
291  REQUIRE( O.includes( SkelO ) );
292  REQUIRE( StarSkelO.equals( O ) );
293  REQUIRE( StarO.equals( O ) );
294  }
295  }
296  WHEN( "Computing the skeleton of a random set of cells C, C subset Star(C), Skel(C) subset C, C subset Star(Skel(C)), Star(C) = Star(Skel(Star(C)))" ) {
297  std::vector< Point > X;
298  for ( int i = 0; i < 10; i++ )
299  X.push_back( Point( rand() % 10, rand() % 10 ) );
300  for ( Dimension a = 0; a < 2; a++ )
301  {
302  LatticeSet C( X.cbegin(), X.cend(), a );
303  auto StarC = C.starOfCells();
304  auto SkelC = C.skeletonOfCells();
305  auto StarSkelC = SkelC.starOfCells();
306  auto StarSkelStarC = StarC.skeletonOfCells().starOfCells();
307  CAPTURE( C.axis() );
308  CAPTURE( C.size() );
309  CAPTURE( SkelC.size() );
310  CAPTURE( StarSkelC.size() );
311  CAPTURE( StarC.size() );
312  CAPTURE( StarSkelStarC.size() );
313  REQUIRE( StarC.includes( C ) );
314  REQUIRE( C.includes( SkelC) );
315  REQUIRE( StarSkelC.includes( C ) );
316  REQUIRE( StarSkelStarC.equals( StarC ) );
317  }
318  WHEN( "Computing the extrema of a set of cells C, extremas are correct" ) {
319  std::vector< Point > XX;
320  XX.push_back( Point(10,-2) );
321  XX.push_back( Point(5,5) );
322  XX.push_back( Point(4,5) );
323  XX.push_back( Point(3,5) );
324  XX.push_back( Point(2,1) );
325  XX.push_back( Point(2,3) );
326  XX.push_back( Point(1,1) );
327  XX.push_back( Point(-2,3) );
328  XX.push_back( Point(-3,2) );
329  LatticeSet C( XX.cbegin(), XX.cend(), 0 );
330  auto ExtrC = C.extremaOfCells();
331  CAPTURE( C.toPointRange() );
332  CAPTURE( ExtrC );
333  REQUIRE( ExtrC.size() == 14 );
334  }
335  }
336 }
DGtal::Clock::startClock
void startClock()
DGtal
DGtal is the top-level namespace which contains all DGtal functions and types.
DGtal::Dimension
DGtal::uint32_t Dimension
Definition: Common.h:136
Point
MyPointD Point
Definition: testClone2.cpp:383
CAPTURE
CAPTURE(thicknessHV)
SCENARIO
SCENARIO("LatticeSetByIntervals< int > unit tests", "[lattice_set]")
Definition: testLatticeSetByIntervals.cpp:48
REQUIRE
REQUIRE(domain.isInside(aPoint))