DGtal  1.5.beta
testShortestPaths.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/helpers/Shortcuts.h"
37 #include "DGtal/geometry/volumes/TangencyComputer.h"
38 #include "DGtalCatch.h"
40 
41 using namespace std;
42 using namespace DGtal;
43 
44 
46 // Functions for testing class TangencyComputer::ShortestPaths
48 
49 SCENARIO( "TangencyComputer::ShortestPaths 3D tests", "[shortest_paths][3d][tangency]" )
50 {
51  typedef Z3i::Space Space;
52  typedef Z3i::KSpace KSpace;
53  typedef Shortcuts< KSpace > SH3;
54  typedef Space::Point Point;
55  typedef std::size_t Index;
56 
57  SECTION( "Computing shortest paths on a 3D unit sphere digitized at gridstep 0.25" )
58  {
59  // Make digital sphere
60  const double h = 0.25;
61  auto params = SH3::defaultParameters();
62  params( "polynomial", "sphere1" )( "gridstep", h );
63  params( "minAABB", -2)( "maxAABB", 2)( "offset", 1.0 )( "closed", 1 );
64  auto implicit_shape = SH3::makeImplicitShape3D ( params );
65  auto digitized_shape = SH3::makeDigitizedImplicitShape3D( implicit_shape, params );
66  auto K = SH3::getKSpace( params );
67  auto binary_image = SH3::makeBinaryImage(digitized_shape,
69  params );
70  auto surface = SH3::makeDigitalSurface( binary_image, K, params );
71  std::vector< Point > lattice_points;
72  auto pointels = SH3::getPointelRange( surface );
73  for ( auto p : pointels ) lattice_points.push_back( K.uCoords( p ) );
74  REQUIRE( pointels.size() == 296 );
75  // Find lowest and uppest point.
76  const Index nb = lattice_points.size();
77  Index lowest = 0;
78  Index uppest = 0;
79  for ( Index i = 1; i < nb; i++ )
80  {
81  if ( lattice_points[ i ] < lattice_points[ lowest ] ) lowest = i;
82  if ( lattice_points[ uppest ] < lattice_points[ i ] ) uppest = i;
83  }
84  // Compute shortest paths
85  typedef TangencyComputer< KSpace >::Index _Index;
87  TC.init( lattice_points.cbegin(), lattice_points.cend() );
88  auto SP = TC.makeShortestPaths( sqrt(3.0) );
89  SP.init( lowest ); //< set source
90  double last_distance = 0.0;
91  _Index last = 0;
92  double prev_distance = 0.0;
93  std::set< _Index > V;
94  unsigned int nb_multiple_pops = 0;
95  unsigned int nb_decreasing_distance = 0;
96  while ( ! SP.finished() )
97  {
98  last = std::get<0>( SP.current() );
99  last_distance = std::get<2>( SP.current() );
100  if ( V.count( last ) ) nb_multiple_pops += 1;
101  V.insert( last );
102  SP.expand();
103  if ( last_distance < prev_distance ) nb_decreasing_distance += 1;
104  prev_distance = last_distance;
105  }
106  // THEN( "No point is popped several times" )
107  REQUIRE( nb_multiple_pops == 0 );
108  // AND_THEN( "The sequence of popped points has non decreasing distances" )
109  REQUIRE( nb_decreasing_distance == 0 );
110  // AND_THEN( "The furthest point is also the antipodal point" )
111  REQUIRE( last == uppest );
112  // AND_THEN( "The furthest point is at distance close but lower than pi" )
113  REQUIRE( last_distance*h >= 2.8 );
114  REQUIRE( last_distance*h <= 3.14159265358979323844 );
115  // Compute approximate shortest paths
116  SP = TC.makeShortestPaths( 0 );
117  SP.init( uppest ); //< set source
118  double last_distance_opt = 0.0;
119  while ( ! SP.finished() )
120  {
121  last = std::get<0>( SP.current() );
122  last_distance_opt = std::get<2>( SP.current() );
123  SP.expand();
124  }
125  // THEN( "The furthest point is also the antipodal point" )
126  REQUIRE( last == lowest );
127  // AND_THEN( "The furthest point is at distance close but lower than pi" )
128  REQUIRE( last_distance_opt*h >= 2.8 );
129  REQUIRE( last_distance_opt*h <= 3.14159265358979323844 );
130  // AND_THEN( "This distance is greater or equal to the exacts shortest path" )
131  REQUIRE( last_distance_opt*h >= last_distance*h );
132  }
133 }
134 
Aim: This class is a model of CCellularGridSpaceND. It represents the cubical grid as a cell complex,...
const Point & lowerBound() const
Return the lower bound for digital points in this space.
Point uCoords(const Cell &c) const
Return its digital coordinates.
const Point & upperBound() const
Return the upper bound for digital points in this space.
Aim: This class is used to simplify shape and surface creation. With it, you can create new shapes an...
Definition: Shortcuts.h:105
Aim: A class that computes tangency to a given digital set. It provides services to compute all the c...
CountedPtr< SH3::DigitalSurface > surface
CountedPtr< SH3::BinaryImage > binary_image
SMesh::Index Index
DGtal is the top-level namespace which contains all DGtal functions and types.
Shortcuts< KSpace > SH3
MyPointD Point
Definition: testClone2.cpp:383
KSpace K
SCENARIO("TangencyComputer::ShortestPaths 3D tests", "[shortest_paths][3d][tangency]")
SECTION("Testing constant forward iterators")
REQUIRE(domain.isInside(aPoint))