DGtal  1.0.0
IndexedDigitalSurface.ih
1 /**
2  * This program is free software: you can redistribute it and/or modify
3  * it under the terms of the GNU Lesser General Public License as
4  * published by the Free Software Foundation, either version 3 of the
5  * License, or (at your option) any later version.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * along with this program. If not, see <http://www.gnu.org/licenses/>.
14  *
15  **/
16 
17 /**
18  * @file IndexedDigitalSurface.ih
19  * @author Jacques-Olivier Lachaud (\c jacques-olivier.lachaud@univ-savoie.fr )
20  * Laboratory of Mathematics (CNRS, UMR 5127), University of Savoie, France
21  *
22  * @date 2017/02/05
23  *
24  * Implementation of inline methods defined in IndexedDigitalSurface.h
25  *
26  * This file is part of the DGtal library.
27  */
28 
29 
30 //////////////////////////////////////////////////////////////////////////////
31 #include <cstdlib>
32 #include <algorithm>
33 #include "DGtal/topology/DigitalSurface.h"
34 #include "DGtal/topology/CanonicSCellEmbedder.h"
35 //////////////////////////////////////////////////////////////////////////////
36 
37 ///////////////////////////////////////////////////////////////////////////////
38 // IMPLEMENTATION of inline methods.
39 ///////////////////////////////////////////////////////////////////////////////
40 
41 ///////////////////////////////////////////////////////////////////////////////
42 // ----------------------- Standard services ------------------------------
43 
44 //-----------------------------------------------------------------------------
45 template <typename TDigitalSurfaceContainer>
46 inline
47 bool
48 DGtal::IndexedDigitalSurface<TDigitalSurfaceContainer>::build
49 ( ConstAlias< DigitalSurfaceContainer > surfContainer )
50 {
51  if ( isHEDSValid ) {
52  trace.warning() << "[DGtal::IndexedDigitalSurface<TDigitalSurfaceContainer>::build()]"
53  << " attempting to rebuild a polygonal surface." << std::endl;
54  return false;
55  }
56  myContainer = CountedConstPtrOrConstPtr< DigitalSurfaceContainer >( surfContainer );
57  DigitalSurface< DigitalSurfaceContainer > surface( *myContainer );
58  CanonicSCellEmbedder< KSpace > embedder( myContainer->space() );
59  // Numbering surfels / vertices
60  VertexIndex i = 0;
61  for ( SCell aSurfel : surface )
62  {
63  myPositions.push_back( embedder( aSurfel ) );
64  mySurfel2VertexIndex[ aSurfel ] = i++;
65  }
66  // Numbering pointels / faces
67  FaceIndex j = 0;
68  auto faces = surface.allClosedFaces();
69  for ( auto aFace : faces )
70  {
71  auto vtcs = surface.verticesAroundFace( aFace );
72  PolygonalFace idx_face( vtcs.size() );
73  std::transform( vtcs.cbegin(), vtcs.cend(), idx_face.begin(),
74  [&]
75  ( const SCell& v ) { return mySurfel2VertexIndex[ v ]; } );
76  myPolygonalFaces.push_back( idx_face );
77  myPointel2FaceIndex[ surface.pivot( aFace ) ] = j++;
78  }
79  isHEDSValid = myHEDS.build( myPolygonalFaces );
80  if ( myHEDS.nbVertices() != myPositions.size() ) {
81  trace.warning() << "[DGtal::IndexedDigitalSurface<TDigitalSurfaceContainer>::build()]"
82  << " the size of vertex data array (s1) and the number of vertices (s2) in the polygonal surface does not match:"
83  << " s1=" << myPositions.size()
84  << " s2=" << myHEDS.nbVertices() << std::endl;
85  isHEDSValid = false;
86  }
87  else
88  { // We build the mapping for vertices and faces
89  myVertexIndex2Surfel.resize( nbVertices() );
90  myFaceIndex2Pointel .resize( nbFaces() );
91  myArc2Linel .resize( nbArcs() );
92  for ( auto p : mySurfel2VertexIndex )
93  myVertexIndex2Surfel[ p.second ] = p.first;
94  for ( auto p : myPointel2FaceIndex )
95  myFaceIndex2Pointel [ p.second ] = p.first;
96  // We build the mapping for arcs
97  // Visiting arcs
98  for ( Arc fi = 0; fi < myArc2Linel.size(); ++fi )
99  {
100  auto vi_vj = myHEDS.arcFromHalfEdgeIndex( fi );
101  SCell surfi = myVertexIndex2Surfel[ vi_vj.first ];
102  SCell surfj = myVertexIndex2Surfel[ vi_vj.second ];
103  SCell lnl = surface.separator( surface.arc( surfi, surfj ) );
104  myLinel2Arc[ lnl ] = fi;
105  myArc2Linel[ fi ] = lnl;
106  // trace.info() << "- Arc " << fi
107  // << " (" << vi_vj.first << "," << vi_vj.second << ") "
108  // << " (" << surfi << "," << surfj << ") "
109  // << " lnl=" << lnl << space().sDim( lnl ) << std::endl;
110  }
111  }
112  return isHEDSValid;
113 }
114 
115 //-----------------------------------------------------------------------------
116 template <typename TDigitalSurfaceContainer>
117 inline
118 void
119 DGtal::IndexedDigitalSurface<TDigitalSurfaceContainer>::clear()
120 {
121  isHEDSValid = false;
122  myHEDS.clear();
123  myContainer = 0;
124  myPositions.clear();
125  myPolygonalFaces.clear();
126  mySurfel2VertexIndex.clear();
127  myLinel2Arc.clear();
128  myPointel2FaceIndex.clear();
129  myVertexIndex2Surfel.clear();
130  myArc2Linel.clear();
131  myFaceIndex2Pointel.clear();
132 }
133 
134 //-----------------------------------------------------------------------------
135 template <typename TDigitalSurfaceContainer>
136 inline
137 typename DGtal::IndexedDigitalSurface<TDigitalSurfaceContainer>::RealPoint&
138 DGtal::IndexedDigitalSurface<TDigitalSurfaceContainer>::position( Vertex v )
139 {
140  ASSERT( 0 <= v && v < myPositions.size() );
141  return myPositions[ v ];
142 }
143 //-----------------------------------------------------------------------------
144 template <typename TDigitalSurfaceContainer>
145 inline
146 const typename DGtal::IndexedDigitalSurface<TDigitalSurfaceContainer>::RealPoint&
147 DGtal::IndexedDigitalSurface<TDigitalSurfaceContainer>::position( Vertex v ) const
148 {
149  ASSERT( 0 <= v && v < myPositions.size() );
150  return myPositions[ v ];
151 }
152 //-----------------------------------------------------------------------------
153 template <typename TDigitalSurfaceContainer>
154 inline
155 typename DGtal::IndexedDigitalSurface<TDigitalSurfaceContainer>::Size
156 DGtal::IndexedDigitalSurface<TDigitalSurfaceContainer>::size() const
157 {
158  return myPositions.size();
159 }
160 //-----------------------------------------------------------------------------
161 template <typename TDigitalSurfaceContainer>
162 inline
163 typename DGtal::IndexedDigitalSurface<TDigitalSurfaceContainer>::Size
164 DGtal::IndexedDigitalSurface<TDigitalSurfaceContainer>::bestCapacity() const
165 {
166  return 4;
167 }
168 //-----------------------------------------------------------------------------
169 template <typename TDigitalSurfaceContainer>
170 inline
171 typename DGtal::IndexedDigitalSurface<TDigitalSurfaceContainer>::Size
172 DGtal::IndexedDigitalSurface<TDigitalSurfaceContainer>::degree( const Vertex & v ) const
173 {
174  ASSERT( isValid() );
175  return myHEDS.nbNeighboringVertices( v );
176 }
177 
178 //-----------------------------------------------------------------------------
179 template <typename TDigitalSurfaceContainer>
180 template <typename OutputIterator>
181 inline
182 void
183 DGtal::IndexedDigitalSurface<TDigitalSurfaceContainer>::writeNeighbors
184 ( OutputIterator &it, const Vertex & v ) const
185 {
186  ASSERT( isValid() );
187  typedef HalfEdgeDataStructure::VertexIndexRange VertexIndexRange;
188  VertexIndexRange neighbors;
189  myHEDS.getNeighboringVertices( v, neighbors );
190  for ( Vertex nv : neighbors ) *it++ = nv;
191 }
192 
193 //-----------------------------------------------------------------------------
194 template <typename TDigitalSurfaceContainer>
195 template <typename OutputIterator, typename VertexPredicate>
196 inline
197 void
198 DGtal::IndexedDigitalSurface<TDigitalSurfaceContainer>::writeNeighbors
199 ( OutputIterator &it, const Vertex & v, const VertexPredicate & pred) const
200 {
201  ASSERT( isValid() );
202  typedef HalfEdgeDataStructure::VertexIndexRange VertexIndexRange;
203  VertexIndexRange neighbors;
204  myHEDS.getNeighboringVertices( v, neighbors );
205  for ( Vertex nv : neighbors ) if ( pred( nv ) ) *it++ = nv;
206 }
207 
208 //-----------------------------------------------------------------------------
209 template <typename TDigitalSurfaceContainer>
210 inline
211 typename DGtal::IndexedDigitalSurface<TDigitalSurfaceContainer>::ArcRange
212 DGtal::IndexedDigitalSurface<TDigitalSurfaceContainer>::outArcs( const Vertex & v ) const
213 {
214  ArcRange result;
215  const Index start_hei = myHEDS.halfEdgeIndexFromVertexIndex( v );
216  Index hei = start_hei;
217  do
218  {
219  const HalfEdge& he = myHEDS.halfEdge( hei );
220  if( INVALID_FACE != he.face ) result.push_back( hei );
221  hei = myHEDS.halfEdge( he.opposite ).next;
222  }
223  while ( hei != start_hei );
224  return result;
225 }
226 
227 //-----------------------------------------------------------------------------
228 template <typename TDigitalSurfaceContainer>
229 inline
230 typename DGtal::IndexedDigitalSurface<TDigitalSurfaceContainer>::ArcRange
231 DGtal::IndexedDigitalSurface<TDigitalSurfaceContainer>::inArcs( const Vertex & v ) const
232 {
233  ArcRange result;
234  const Index start_hei = myHEDS.halfEdgeIndexFromVertexIndex( v );
235  Index hei = start_hei;
236  do
237  {
238  const HalfEdge& he = myHEDS.halfEdge( hei );
239  if( INVALID_FACE != he.face ) result.push_back( he.opposite );
240  hei = myHEDS.halfEdge( he.opposite ).next;
241  }
242  while ( hei != start_hei );
243  return result;
244 }
245 
246 //-----------------------------------------------------------------------------
247 template <typename TDigitalSurfaceContainer>
248 inline
249 typename DGtal::IndexedDigitalSurface<TDigitalSurfaceContainer>::FaceRange
250 DGtal::IndexedDigitalSurface<TDigitalSurfaceContainer>::facesAroundVertex( const Vertex & v ) const
251 {
252  FaceRange result;
253  const Index start_hei = myHEDS.halfEdgeIndexFromVertexIndex( v );
254  Index hei = start_hei;
255  do
256  {
257  const HalfEdge& he = myHEDS.halfEdge( hei );
258  if( INVALID_FACE != he.face ) result.push_back( he.face );
259  hei = myHEDS.halfEdge( he.opposite ).next;
260  }
261  while ( hei != start_hei );
262  return result;
263 }
264 
265 //-----------------------------------------------------------------------------
266 template <typename TDigitalSurfaceContainer>
267 inline
268 typename DGtal::IndexedDigitalSurface<TDigitalSurfaceContainer>::Vertex
269 DGtal::IndexedDigitalSurface<TDigitalSurfaceContainer>::head( const Arc & a ) const
270 {
271  return myHEDS.halfEdge( a ).toVertex;
272 }
273 
274 //-----------------------------------------------------------------------------
275 template <typename TDigitalSurfaceContainer>
276 inline
277 typename DGtal::IndexedDigitalSurface<TDigitalSurfaceContainer>::Vertex
278 DGtal::IndexedDigitalSurface<TDigitalSurfaceContainer>::tail( const Arc & a ) const
279 {
280  return head( opposite( a ) );
281 }
282 
283 //-----------------------------------------------------------------------------
284 template <typename TDigitalSurfaceContainer>
285 inline
286 typename DGtal::IndexedDigitalSurface<TDigitalSurfaceContainer>::Arc
287 DGtal::IndexedDigitalSurface<TDigitalSurfaceContainer>::opposite( const Arc & a ) const
288 {
289  return myHEDS.halfEdge( a ).opposite;
290 }
291 
292 //-----------------------------------------------------------------------------
293 template <typename TDigitalSurfaceContainer>
294 inline
295 typename DGtal::IndexedDigitalSurface<TDigitalSurfaceContainer>::Arc
296 DGtal::IndexedDigitalSurface<TDigitalSurfaceContainer>::next( const Arc & a ) const
297 {
298  return myHEDS.halfEdge( a ).next;
299 }
300 //-----------------------------------------------------------------------------
301 template <typename TDigitalSurfaceContainer>
302 inline
303 typename DGtal::IndexedDigitalSurface<TDigitalSurfaceContainer>::Arc
304 DGtal::IndexedDigitalSurface<TDigitalSurfaceContainer>::arc
305 ( const Vertex & t, const Vertex & h ) const
306 {
307  return myHEDS.halfEdgeIndexFromArc( t, h );
308 }
309 
310 //-----------------------------------------------------------------------------
311 template <typename TDigitalSurfaceContainer>
312 inline
313 typename DGtal::IndexedDigitalSurface<TDigitalSurfaceContainer>::Face
314 DGtal::IndexedDigitalSurface<TDigitalSurfaceContainer>::faceAroundArc( const Arc & a ) const
315 {
316  return myHEDS.halfEdge( a ).face;
317 }
318 //-----------------------------------------------------------------------------
319 template <typename TDigitalSurfaceContainer>
320 inline
321 typename DGtal::IndexedDigitalSurface<TDigitalSurfaceContainer>::FaceRange
322 DGtal::IndexedDigitalSurface<TDigitalSurfaceContainer>::facesAroundArc( const Arc & a ) const
323 {
324  FaceRange result;
325  Face f = faceAroundArc( a );
326  if ( f != INVALID_FACE ) result.push_back( f );
327  return result;
328 }
329 
330 //-----------------------------------------------------------------------------
331 template <typename TDigitalSurfaceContainer>
332 inline
333 typename DGtal::IndexedDigitalSurface<TDigitalSurfaceContainer>::VertexRange
334 DGtal::IndexedDigitalSurface<TDigitalSurfaceContainer>::verticesAroundFace( const Face & f ) const
335 {
336  VertexRange result;
337  const Index start_hei = myHEDS.halfEdgeIndexFromFaceIndex( f );
338  Index hei = start_hei;
339  do {
340  const HalfEdge& he = myHEDS.halfEdge( hei );
341  ASSERT( ( he.face == f )
342  && "[IndexedDigitalSurface::verticesAroundFace] invalid face." );
343  result.push_back( he.toVertex );
344  hei = he.next;
345  } while ( hei != start_hei );
346  ASSERT( result.size() >= 3 );
347  return result;
348 }
349 
350 //-----------------------------------------------------------------------------
351 template <typename TDigitalSurfaceContainer>
352 inline
353 bool
354 DGtal::IndexedDigitalSurface<TDigitalSurfaceContainer>::isVertexBoundary( const Vertex& v ) const
355 {
356  return myHEDS.isVertexBoundary( v );
357 }
358 
359 //-----------------------------------------------------------------------------
360 template <typename TDigitalSurfaceContainer>
361 inline
362 bool
363 DGtal::IndexedDigitalSurface<TDigitalSurfaceContainer>::isArcBoundary( const Arc& v ) const
364 {
365  return INVALID_FACE == myHEDS.halfEdge( v ).face;
366 }
367 
368 //-----------------------------------------------------------------------------
369 template <typename TDigitalSurfaceContainer>
370 inline
371 typename DGtal::IndexedDigitalSurface<TDigitalSurfaceContainer>::FaceRange
372 DGtal::IndexedDigitalSurface<TDigitalSurfaceContainer>::allFaces() const
373 {
374  FaceRange result( nbFaces() );
375  for ( Face fi = 0; fi < result.size(); ++fi )
376  result[ fi ] = fi;
377  return result;
378 }
379 //-----------------------------------------------------------------------------
380 template <typename TDigitalSurfaceContainer>
381 inline
382 typename DGtal::IndexedDigitalSurface<TDigitalSurfaceContainer>::ArcRange
383 DGtal::IndexedDigitalSurface<TDigitalSurfaceContainer>::allArcs() const
384 {
385  ArcRange result( nbArcs() );
386  for ( Arc fi = 0; fi < result.size(); ++fi )
387  result[ fi ] = fi;
388  return result;
389 }
390 //-----------------------------------------------------------------------------
391 template <typename TDigitalSurfaceContainer>
392 inline
393 typename DGtal::IndexedDigitalSurface<TDigitalSurfaceContainer>::VertexRange
394 DGtal::IndexedDigitalSurface<TDigitalSurfaceContainer>::allVertices() const
395 {
396  VertexRange result( nbVertices() );
397  for ( Vertex fi = 0; fi < result.size(); ++fi )
398  result[ fi ] = fi;
399  return result;
400 }
401 
402 //-----------------------------------------------------------------------------
403 template <typename TDigitalSurfaceContainer>
404 inline
405 typename DGtal::IndexedDigitalSurface<TDigitalSurfaceContainer>::ArcRange
406 DGtal::IndexedDigitalSurface<TDigitalSurfaceContainer>::allBoundaryArcs() const
407 {
408  return myHEDS.boundaryHalfEdgeIndices();
409 }
410 
411 //-----------------------------------------------------------------------------
412 template <typename TDigitalSurfaceContainer>
413 inline
414 typename DGtal::IndexedDigitalSurface<TDigitalSurfaceContainer>::VertexRange
415 DGtal::IndexedDigitalSurface<TDigitalSurfaceContainer>::allBoundaryVertices() const
416 {
417  return myHEDS.boundaryVertices();
418 }
419 
420 
421 ///////////////////////////////////////////////////////////////////////////////
422 // Interface - public :
423 
424 /**
425  * Writes/Displays the object on an output stream.
426  * @param out the output stream where the object is written.
427  */
428 template <typename TDigitalSurfaceContainer>
429 inline
430 void
431 DGtal::IndexedDigitalSurface<TDigitalSurfaceContainer>::selfDisplay ( std::ostream & out ) const
432 {
433  out << "[IndexedDigitalSurface #V=" << myHEDS.nbVertices()
434  << " #E=" << myHEDS.nbEdges() << " #F=" << myHEDS.nbFaces()
435  << " Chi=" << Euler() << "]";
436 }
437 
438 /**
439  * Checks the validity/consistency of the object.
440  * @return 'true' if the object is valid, 'false' otherwise.
441  */
442 template <typename TDigitalSurfaceContainer>
443 inline
444 bool
445 DGtal::IndexedDigitalSurface<TDigitalSurfaceContainer>::isValid() const
446 {
447  return isHEDSValid;
448 }
449 
450 
451 
452 ///////////////////////////////////////////////////////////////////////////////
453 // Implementation of inline functions //
454 
455 template <typename TDigitalSurfaceContainer>
456 inline
457 std::ostream&
458 DGtal::operator<< ( std::ostream & out,
459  const IndexedDigitalSurface<TDigitalSurfaceContainer> & object )
460 {
461  object.selfDisplay( out );
462  return out;
463 }
464 
465 // //
466 ///////////////////////////////////////////////////////////////////////////////
467 
468