DGtal 2.2.0
Loading...
Searching...
No Matches
testShortestPaths.cpp File Reference
DGtal Test Files
#include <iostream>
#include <vector>
#include <algorithm>
#include "DGtal/base/Common.h"
#include "DGtal/helpers/StdDefs.h"
#include "DGtal/helpers/Shortcuts.h"
#include "DGtal/geometry/volumes/TangencyComputer.h"
#include "DGtalCatch.h"
Include dependency graph for testShortestPaths.cpp:

Go to the source code of this file.

Functions

 SCENARIO ("TangencyComputer::ShortestPaths 3D tests", "[shortest_paths][3d][tangency]")
 SCENARIO ("TangencyComputer 3D tests", "[3d][tangency]")

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
2022/05/09

Functions for testing shortest paths.

This file is part of the DGtal library.

Definition in file testShortestPaths.cpp.

Function Documentation

◆ SCENARIO() [1/2]

SCENARIO ( "TangencyComputer 3D tests" ,
"" [3d][tangency] )

Definition at line 196 of file testShortestPaths.cpp.

197{
198 typedef Z3i::Space Space;
199 typedef Z3i::KSpace KSpace;
200 typedef Shortcuts< KSpace > SH3;
201 typedef Space::Point Point;
202 typedef std::size_t Index;
203
204 SECTION( "Computing shortest paths on a 3D unit sphere digitized at gridstep 0.125" )
205 {
206 // Make digital sphere
207 const double h = 0.125;
208 auto params = SH3::defaultParameters();
209 params( "polynomial", "sphere1" )( "gridstep", h );
210 params( "minAABB", -2)( "maxAABB", 2)( "offset", 1.0 )( "closed", 1 );
211 auto implicit_shape = SH3::makeImplicitShape3D ( params );
212 auto digitized_shape = SH3::makeDigitizedImplicitShape3D( implicit_shape, params );
213 auto K = SH3::getKSpace( params );
214 auto binary_image = SH3::makeBinaryImage(digitized_shape,
215 SH3::Domain(K.lowerBound(),K.upperBound()),
216 params );
217 auto surface = SH3::makeDigitalSurface( binary_image, K, params );
218 std::vector< Point > lattice_points;
219 auto pointels = SH3::getPointelRange( surface );
220 for ( auto p : pointels ) lattice_points.push_back( K.uCoords( p ) );
221 // Find lowest and uppest point.
222 const Index nb = lattice_points.size();
223 Index lowest = 0;
224 Index uppest = 0;
225 for ( Index i = 1; i < nb; i++ )
226 {
227 if ( lattice_points[ i ] < lattice_points[ lowest ] ) lowest = i;
228 if ( lattice_points[ uppest ] < lattice_points[ i ] ) uppest = i;
229 }
230 // Compute shortest paths
231 TangencyComputer< KSpace > TC( K );
232 TC.init( lattice_points.cbegin(), lattice_points.cend() );
233 const Point a = TC.point( lowest );
234 std::vector< Index > V1 = TC.getCotangentPoints( a, 5.0 );
235 std::vector< Index > V2 = TC.getCotangentPoints( a, 10.0 );
236 std::vector< Index > V3 = TC.getCotangentPoints( a, 15.0 );
237 std::sort( V1.begin(), V1.end() );
238 std::sort( V2.begin(), V2.end() );
239 std::sort( V3.begin(), V3.end() );
240 REQUIRE( 0 < V1.size() );
241 REQUIRE( V1.size() < V2.size() );
242 REQUIRE( V2.size() <= V3.size() );
243 REQUIRE( V3.size() < pointels.size()/2 );
244 REQUIRE( std::includes( V2.begin(), V2.end(), V1.begin(), V1.end() ) );
245 REQUIRE( std::includes( V3.begin(), V3.end(), V2.begin(), V2.end() ) );
246 double md1 = 0.0;
247 double md2 = 0.0;
248 double md3 = 0.0;
249 for ( auto i : V1 ) md1 = std::max( md1, (TC.point( i ) - a).norm() );
250 for ( auto i : V2 ) md2 = std::max( md2, (TC.point( i ) - a).norm() );
251 for ( auto i : V3 ) md3 = std::max( md3, (TC.point( i ) - a).norm() );
252 REQUIRE( md1 <= 5.0 );
253 REQUIRE( md2 <= 10.0 );
254 REQUIRE( md3 <= 15.0 );
255 }
256}
DGtal::KhalimskySpaceND::lowerBound
const Point & lowerBound() const
Return the lower bound for digital points in this space.
DGtal::KhalimskySpaceND::upperBound
const Point & upperBound() const
Return the upper bound for digital points in this space.
DGtal::KhalimskySpaceND::uCoords
Point uCoords(const Cell &c) const
Return its digital coordinates.
DGtal::Shortcuts< Z3i::KSpace >::getKSpace
static KSpace getKSpace(const Point &low, const Point &up, Parameters params=parametersKSpace())
Definition Shortcuts.h:329
DGtal::Shortcuts< Z3i::KSpace >::makeDigitizedImplicitShape3D
static CountedPtr< DigitizedImplicitShape3D > makeDigitizedImplicitShape3D(CountedPtr< ImplicitShape3D > shape, Parameters params=parametersDigitizedImplicitShape3D())
Definition Shortcuts.h:520
DGtal::Shortcuts< Z3i::KSpace >::getPointelRange
static PointelRange getPointelRange(Cell2Index &c2i, CountedPtr< ::DGtal::DigitalSurface< TDigitalSurfaceContainer > > surface)
Definition Shortcuts.h:1730
DGtal::Shortcuts< Z3i::KSpace >::makeDigitalSurface
static CountedPtr< DigitalSurface > makeDigitalSurface(CountedPtr< TPointPredicate > bimage, const KSpace &K, const Parameters &params=parametersDigitalSurface())
Definition Shortcuts.h:1470
DGtal::Shortcuts< Z3i::KSpace >::defaultParameters
static Parameters defaultParameters()
Definition Shortcuts.h:200
DGtal::Shortcuts< Z3i::KSpace >::Domain
HyperRectDomain< Space > Domain
Definition Shortcuts.h:124
DGtal::Shortcuts< Z3i::KSpace >::makeBinaryImage
static CountedPtr< BinaryImage > makeBinaryImage(Domain shapeDomain)
Definition Shortcuts.h:558
DGtal::Shortcuts< Z3i::KSpace >::makeImplicitShape3D
static CountedPtr< ImplicitShape3D > makeImplicitShape3D(const Parameters &params=parametersImplicitShape3D())
Definition Shortcuts.h:279
DGtal::SpaceND< 3, Integer >::Point
PointVector< dim, Integer > Point
Definition SpaceND.h:110
DGtal::TangencyComputer
Aim: A class that computes tangency to a given digital set. It provides services to compute all the c...
Definition TangencyComputer.h:74
surface
CountedPtr< SH3::DigitalSurface > surface
Definition dgtalCalculus-geodesic.cpp:66
binary_image
CountedPtr< SH3::BinaryImage > binary_image
Definition dgtalCalculus-geodesic.cpp:65
Index
SMesh::Index Index
Definition fullConvexitySphereGeodesics.cpp:117
DGtal::Z3i::Space
SpaceND< 3, Integer > Space
Definition StdDefs.h:144
DGtal::Z3i::KSpace
KhalimskySpaceND< 3, Integer > KSpace
Definition StdDefs.h:146
K
KSpace K
Definition testCubicalComplex.cpp:62
SECTION
SECTION("Testing constant forward iterators")
Definition testSimpleRandomAccessRangeFromPoint.cpp:66
REQUIRE
REQUIRE(domain.isInside(aPoint))

References binary_image, DGtal::Shortcuts< Z3i::KSpace >::defaultParameters(), DGtal::Shortcuts< Z3i::KSpace >::getKSpace(), DGtal::Shortcuts< Z3i::KSpace >::getPointelRange(), K, DGtal::KhalimskySpaceND< dim, TInteger >::lowerBound(), DGtal::Shortcuts< Z3i::KSpace >::makeBinaryImage(), DGtal::Shortcuts< Z3i::KSpace >::makeDigitalSurface(), DGtal::Shortcuts< Z3i::KSpace >::makeDigitizedImplicitShape3D(), DGtal::Shortcuts< Z3i::KSpace >::makeImplicitShape3D(), REQUIRE(), SCENARIO(), SECTION(), surface, DGtal::KhalimskySpaceND< dim, TInteger >::uCoords(), and DGtal::KhalimskySpaceND< dim, TInteger >::upperBound().

◆ SCENARIO() [2/2]

SCENARIO ( "TangencyComputer::ShortestPaths 3D tests" ,
"" [shortest_paths][3d][tangency] )

Definition at line 49 of file testShortestPaths.cpp.

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,
68 SH3::Domain(K.lowerBound(),K.upperBound()),
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;
86 TangencyComputer< KSpace > TC( K );
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 SECTION( "Computing different shortest paths on a 3D unit sphere digitized at gridstep 0.125" )
135 {
136 // Make digital sphere
137 const double h = 0.125;
138 auto params = SH3::defaultParameters();
139 params( "polynomial", "sphere1" )( "gridstep", h );
140 params( "minAABB", -2)( "maxAABB", 2)( "offset", 1.0 )( "closed", 1 );
141 auto implicit_shape = SH3::makeImplicitShape3D ( params );
142 auto digitized_shape = SH3::makeDigitizedImplicitShape3D( implicit_shape, params );
143 auto K = SH3::getKSpace( params );
144 auto binary_image = SH3::makeBinaryImage(digitized_shape,
145 SH3::Domain(K.lowerBound(),K.upperBound()),
146 params );
147 auto surface = SH3::makeDigitalSurface( binary_image, K, params );
148 std::vector< Point > lattice_points;
149 auto pointels = SH3::getPointelRange( surface );
150 for ( auto p : pointels ) lattice_points.push_back( K.uCoords( p ) );
151 // Find lowest and uppest point.
152 const Index nb = lattice_points.size();
153 Index lowest = 0;
154 Index uppest = 0;
155 for ( Index i = 1; i < nb; i++ )
156 {
157 if ( lattice_points[ i ] < lattice_points[ lowest ] ) lowest = i;
158 if ( lattice_points[ uppest ] < lattice_points[ i ] ) uppest = i;
159 }
160 // Compute shortest paths
161 TangencyComputer< KSpace > TC( K );
162 TC.init( lattice_points.cbegin(), lattice_points.cend() );
163 auto SP = TC.makeShortestPaths( sqrt(3.0) );
164
165 const double max_discrete_distance = 5.0;
166 const int step = lattice_points.size() / 8;
167 std::size_t sum_nb_visited = 0;
168 std::size_t min_nb_visited = 100000;
169 std::size_t max_nb_visited = 0;
170 int n = 0;
171 for ( auto i = 0; i < lattice_points.size(); i += step, n += 1 )
172 {
173 SP.init( i );
174 std::vector< std::size_t > visited;
175 while ( ! SP.finished() )
176 {
177 auto last = std::get<0>( SP.current() );
178 auto last_distance = std::get<2>( SP.current() );
179 visited.push_back( last );
180 if ( last_distance >= max_discrete_distance ) break;
181 SP.expand();
182 }
183 SP.clearVisited( visited );
184 sum_nb_visited += visited.size();
185 min_nb_visited = std::min( min_nb_visited, visited.size() );
186 max_nb_visited = std::max( max_nb_visited, visited.size() );
187 }
188 double average = sum_nb_visited / (double) n;
189 // Shortest paths from sources on a digital sphere should be of
190 // approximately the same cardinal.
191 REQUIRE( ( average - min_nb_visited ) / average < 0.2 );
192 REQUIRE( ( max_nb_visited - average ) / average < 0.2 );
193 }
194}

References binary_image, DGtal::Shortcuts< Z3i::KSpace >::defaultParameters(), DGtal::Shortcuts< Z3i::KSpace >::getKSpace(), DGtal::Shortcuts< Z3i::KSpace >::getPointelRange(), K, DGtal::KhalimskySpaceND< dim, TInteger >::lowerBound(), DGtal::Shortcuts< Z3i::KSpace >::makeBinaryImage(), DGtal::Shortcuts< Z3i::KSpace >::makeDigitalSurface(), DGtal::Shortcuts< Z3i::KSpace >::makeDigitizedImplicitShape3D(), DGtal::Shortcuts< Z3i::KSpace >::makeImplicitShape3D(), REQUIRE(), SCENARIO(), SECTION(), surface, DGtal::KhalimskySpaceND< dim, TInteger >::uCoords(), and DGtal::KhalimskySpaceND< dim, TInteger >::upperBound().