DGtal  1.3.beta
testVoronoiMapComplete.cpp
Go to the documentation of this file.
1 
29 #include <limits>
31 #include <unordered_set>
32 #include "DGtal/base/Common.h"
33 #include "DGtal/helpers/StdDefs.h"
34 #include "DGtalCatch.h"
35 
36 #include "DGtal/geometry/volumes/distance/VoronoiMapComplete.h"
37 #include "DGtal/geometry/volumes/distance/VoronoiMap.h"
39 using namespace DGtal;
40 
42 typedef Z2i::Point Point;
44 
48  std::unordered_set<Z2i::Point>>
50 
52 {
53  TImageContainer * voronoi_map = new TImageContainer( set.domain() );
54  std::vector<Point> Sites;
55  // Getting all voronoi sites in one vector
56  for ( Point point : set.domain() )
57  {
58  if ( !set( point ) )
59  {
60  Sites.push_back( point );
61  }
62  }
63  std::cout << std::endl;
64 
65  for ( Point point : set.domain() )
66  {
67 
68  std::unordered_set<Point> voronoi_points;
69  double voronoi_distance =
70  std::numeric_limits<int>::max(); // maximum int value
71  for ( Point site : Sites )
72  {
73  if ( ( point - site ).norm() < voronoi_distance )
74  {
75  voronoi_points.clear();
76  voronoi_points.insert( site );
77  voronoi_distance = ( point - site ).norm();
78  }
79  else if ( ( point - site ).norm() == voronoi_distance )
80  {
81  voronoi_points.insert( site );
82  }
83  }
84  voronoi_map->setValue( point, voronoi_points );
85  }
86  return voronoi_map;
87 }
88 
90 // Functions for testing class VoronoiMapComplete
92 TEST_CASE( "Testing VoronoiMapComplete 2D" )
93 {
97  Point lowerBound( 0, 0 ), upperBound( 31, 31 );
98  Domain domain( lowerBound, upperBound );
99 
100  DigitalSet set( domain );
101  int point_setup_index = 0;
102  int x;
103  int y;
104 
105  while ( point_setup_index < 400 )
106  {
107  x = rand() % 32;
108  y = rand() % 32;
109  set.insert( Point( x, y ) );
110  point_setup_index++;
111  }
112 
116  CompleteVMap vmap( set.domain(), set, Z2i::l2Metric );
117 
121  TImageContainer * brut_force_vmap = brut_force_voronoi_map_complete( set );
122 
123  SECTION(
124  "Testing that VoronoiMapComplete class gives the right voronoi sites sets" )
125  {
126  for ( Point point : set )
127  {
128  std::unordered_set<Point> brut_force_set =
129  brut_force_vmap->operator()( point );
130  CompleteVMap::Value class_set = vmap( point );
131 
132  // Cheking that all voronoi sites from the brut force set are in the
133  // algorithm set
134  for ( Point voronoi_point : brut_force_set )
135  {
136  REQUIRE( std::find( class_set.begin(), class_set.end(),
137  voronoi_point ) != class_set.end() );
138  }
139 
140  // Cheking that all voronoi sites from the algorithm set are in the brut
141  // force set
142  for ( Point voronoi_point : class_set )
143  {
144  REQUIRE( std::find( brut_force_set.begin(), brut_force_set.end(),
145  voronoi_point ) != brut_force_set.end() );
146  }
147  }
148  }
149 
150  SECTION(
151  "Testing Complete Voronoi Map from Discrete Bisector Function paper" )
152  {
153  Point lowerBound( 0, 0 ), upperBound( 6, 7 );
154  Domain domain( lowerBound, upperBound );
155  DigitalSet set( domain );
156  for ( Point point : set.domain() )
157  {
158  if ( point != Point( 1, 0 ) && point != Point( 5, 0 ) &&
159  point != Point( 2, 2 ) && point != Point( 4, 4 ) &&
160  point != Point( 0, 6 ) && point != Point( 6, 6 ) &&
161  point != Point( 3, 7 ) )
162  set.insert( point );
163  }
164 
165  TImageContainer * brutForceVoronoiMap =
167  CompleteVMap vmap( set.domain(), set, Z2i::l2Metric );
168 
169  for ( Point point : set )
170  {
171  std::unordered_set<Point> brut_force_set =
172  brutForceVoronoiMap->operator()( point );
173  CompleteVMap::Value class_set = vmap( point );
174 
175  // Cheking that all voronoi sites from the brut force set are in the
176  // algorithm set
177  for ( Point voronoi_point : brut_force_set )
178  REQUIRE( std::find( class_set.begin(), class_set.end(),
179  voronoi_point ) != class_set.end() );
180 
181  // Cheking that all voronoi sites from the algorithm set are in the brut
182  // force set
183  for ( Point voronoi_point : class_set )
184  REQUIRE( std::find( brut_force_set.begin(), brut_force_set.end(),
185  voronoi_point ) != brut_force_set.end() );
186  }
187  }
188 }
189 
190 TEST_CASE( "No sites" )
191 {
195  Point lowerBound( 0, 0 ), upperBound( 255, 255 );
196  Domain domain( lowerBound, upperBound );
197  DigitalSet set( domain );
198 
199  trace.beginBlock( "Complete Map (no site)" );
200  CompleteVMap vmap( set.domain(), set, Z2i::l2Metric );
201  trace.endBlock();
202  trace.beginBlock( "Partial Map (no site)" );
203  VMap partialmap( set.domain(), set, Z2i::l2Metric );
204  trace.endBlock();
205 }
206 
207 TEST_CASE( "Testing Timings" )
208 {
212  Point lowerBound( 0, 0 ), upperBound( 255, 255 );
213  Domain domain( lowerBound, upperBound );
214 
215  DigitalSet set( domain );
216  int point_setup_index = 0;
217  int x;
218  int y;
219 
220  while ( point_setup_index < 5000 )
221  {
222  x = rand() % 256;
223  y = rand() % 256;
224  set.insert( Point( x, y ) );
225  point_setup_index++;
226  }
227  std::cout << std::endl;
228  trace.beginBlock( "Complete Map" );
229  CompleteVMap vmap( set.domain(), set, Z2i::l2Metric );
230  trace.endBlock();
231 
232  size_t maxsize = 0;
233  for ( auto & v : vmap.constRange() )
234  maxsize = std::max( maxsize, v.size() );
235  trace.info() << "Max number of co-cyclic points = " << maxsize << std::endl;
236 
237  trace.beginBlock( "Partial Map" );
238  VMap partialmap( set.domain(), set, Z2i::l2Metric );
239  trace.endBlock();
240 }
DGtal::VoronoiMapComplete
Aim: Implementation of the linear in time Voronoi map construction.
Definition: VoronoiMapComplete.h:135
DGtal::HyperRectDomain< Space >
DGtal::Trace::endBlock
double endBlock()
DGtal::VoronoiMap
Aim: Implementation of the linear in time Voronoi map construction.
Definition: VoronoiMap.h:126
max
int max(int a, int b)
Definition: testArithmeticalDSS.cpp:1108
DGtal::ImageContainerBySTLVector
Definition: ImageContainerBySTLVector.h:126
DGtal::VoronoiMapComplete::constRange
ConstRange constRange() const
Definition: VoronoiMapComplete.h:283
DGtal::trace
Trace trace
Definition: Common.h:154
DGtal::Trace::beginBlock
void beginBlock(const std::string &keyword="")
DGtal::ImageContainerBySTLVector::setValue
void setValue(const Point &aPoint, const Value &aValue)
REQUIRE
REQUIRE(domain.isInside(aPoint))
DGtal::Trace::info
std::ostream & info()
CompleteVMap
VoronoiMapComplete< Z2i::Space, DigitalSet, Z2i::L2Metric > CompleteVMap
Definition: testVoronoiMapComplete.cpp:45
Point
Z2i::Point Point
Definition: testVoronoiMapComplete.cpp:42
DGtal::Z2i::l2Metric
static const L2Metric l2Metric
Definition: StdDefs.h:123
Domain
Z2i::Domain Domain
Definition: testVoronoiMapComplete.cpp:43
DGtal
DGtal is the top-level namespace which contains all DGtal functions and types.
TEST_CASE
TEST_CASE("Testing VoronoiMapComplete 2D")
Definition: testVoronoiMapComplete.cpp:92
DGtal::DigitalSetByAssociativeContainer::insert
void insert(const Point &p)
VMap
VoronoiMap< Z2i::Space, DigitalSet, Z2i::L2Metric > VMap
Definition: testVoronoiMapComplete.cpp:46
brut_force_voronoi_map_complete
TImageContainer * brut_force_voronoi_map_complete(DigitalSet &set)
Definition: testVoronoiMapComplete.cpp:51
domain
Domain domain
Definition: testProjection.cpp:88
DGtal::PointVector< dim, Integer >
SECTION
SECTION("Testing constant forward iterators")
Definition: testSimpleRandomAccessRangeFromPoint.cpp:66
DGtal::DigitalSetByAssociativeContainer::domain
const Domain & domain() const
TImageContainer
ImageContainerBySTLVector< HyperRectDomain< Z2i::Space >, std::unordered_set< Z2i::Point > > TImageContainer
Definition: testVoronoiMapComplete.cpp:49
DGtal::VoronoiMapComplete::Value
OutputImage::Value Value
Definition of the image value type.
Definition: VoronoiMapComplete.h:185
Point
MyPointD Point
Definition: testClone2.cpp:383
DigitalSet
Z2i::DigitalSet DigitalSet
Definition: testVoronoiMapComplete.cpp:41
DGtal::DigitalSetByAssociativeContainer
Aim: A wrapper class around a STL associative container for storing sets of digital points within som...
Definition: DigitalSetByAssociativeContainer.h:89