DGtal  1.1.0
TriangulatedSurface.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 TriangulatedSurface.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 TriangulatedSurface.h
25  *
26  * This file is part of the DGtal library.
27  */
28 
29 
30 //////////////////////////////////////////////////////////////////////////////
31 #include <cstdlib>
32 //////////////////////////////////////////////////////////////////////////////
33 
34 ///////////////////////////////////////////////////////////////////////////////
35 // IMPLEMENTATION of inline methods.
36 ///////////////////////////////////////////////////////////////////////////////
37 
38 ///////////////////////////////////////////////////////////////////////////////
39 // ----------------------- Standard services ------------------------------
40 
41 //-----------------------------------------------------------------------------
42 template <typename TPoint>
43 inline
44 bool
45 DGtal::TriangulatedSurface<TPoint>::build()
46 {
47  if ( isHEDSValid ) {
48  trace.warning() << "[DGtal::TriangulatedSurface<TPoint>::build()]"
49  << " attempting to rebuild a triangulated surface." << std::endl;
50  return false;
51  }
52  isHEDSValid = myHEDS.build( myTriangles );
53  if ( myHEDS.nbVertices() != myPositions.size() ) {
54  trace.warning() << "[DGtal::TriangulatedSurface<TPoint>::build()]"
55  << " the size of vertex data array (s1) and the number of vertices (s2) in the triangulated surface does not match:"
56  << " s1=" << myPositions.size()
57  << " s2=" << myHEDS.nbVertices() << std::endl;
58  isHEDSValid = false;
59  }
60  return isHEDSValid;
61 }
62 
63 //-----------------------------------------------------------------------------
64 template <typename TPoint>
65 inline
66 void
67 DGtal::TriangulatedSurface<TPoint>::clear()
68 {
69  isHEDSValid = false;
70  myHEDS.clear();
71  myPositions.clear();
72  myTriangles.clear();
73 
74 }
75 //-----------------------------------------------------------------------------
76 template <typename TPoint>
77 inline
78 typename DGtal::TriangulatedSurface<TPoint>::VertexIndex
79 DGtal::TriangulatedSurface<TPoint>::addVertex( const Point& vdata )
80 {
81  VertexIndex vi = myPositions.size();
82  myPositions.push_back( vdata );
83  return vi;
84 }
85 
86 //-----------------------------------------------------------------------------
87 template <typename TPoint>
88 inline
89 typename DGtal::TriangulatedSurface<TPoint>::FaceIndex
90 DGtal::TriangulatedSurface<TPoint>::addTriangle
91 ( VertexIndex v0, VertexIndex v1, VertexIndex v2 )
92 {
93  FaceIndex fi = myTriangles.size();
94  myTriangles.push_back( Triangle( v0, v1, v2 ) );
95  return fi;
96 }
97 //-----------------------------------------------------------------------------
98 template <typename TPoint>
99 inline
100 typename DGtal::TriangulatedSurface<TPoint>::Point&
101 DGtal::TriangulatedSurface<TPoint>::position( Vertex v )
102 {
103  ASSERT( 0 <= v && v < myPositions.size() );
104  return myPositions[ v ];
105 }
106 //-----------------------------------------------------------------------------
107 template <typename TPoint>
108 inline
109 const typename DGtal::TriangulatedSurface<TPoint>::Point&
110 DGtal::TriangulatedSurface<TPoint>::position( Vertex v ) const
111 {
112  ASSERT( 0 <= v && v < myPositions.size() );
113  return myPositions[ v ];
114 }
115 //-----------------------------------------------------------------------------
116 template <typename TPoint>
117 inline
118 typename DGtal::TriangulatedSurface<TPoint>::Size
119 DGtal::TriangulatedSurface<TPoint>::size() const
120 {
121  return myPositions.size();
122 }
123 //-----------------------------------------------------------------------------
124 template <typename TPoint>
125 inline
126 typename DGtal::TriangulatedSurface<TPoint>::Size
127 DGtal::TriangulatedSurface<TPoint>::bestCapacity() const
128 {
129  return 8;
130 }
131 //-----------------------------------------------------------------------------
132 template <typename TPoint>
133 inline
134 typename DGtal::TriangulatedSurface<TPoint>::Size
135 DGtal::TriangulatedSurface<TPoint>::degree( const Vertex & v ) const
136 {
137  ASSERT( isValid() );
138  return myHEDS.nbNeighboringVertices( v );
139 }
140 
141 //-----------------------------------------------------------------------------
142 template <typename TPoint>
143 template <typename OutputIterator>
144 inline
145 void
146 DGtal::TriangulatedSurface<TPoint>::writeNeighbors
147 ( OutputIterator &it, const Vertex & v ) const
148 {
149  ASSERT( isValid() );
150  typedef HalfEdgeDataStructure::VertexIndexRange VertexIndexRange;
151  VertexIndexRange neighbors;
152  myHEDS.getNeighboringVertices( v, neighbors );
153  for ( Vertex nv : neighbors ) *it++ = nv;
154 }
155 
156 //-----------------------------------------------------------------------------
157 template <typename TPoint>
158 template <typename OutputIterator, typename VertexPredicate>
159 inline
160 void
161 DGtal::TriangulatedSurface<TPoint>::writeNeighbors
162 ( OutputIterator &it, const Vertex & v, const VertexPredicate & pred) const
163 {
164  ASSERT( isValid() );
165  typedef HalfEdgeDataStructure::VertexIndexRange VertexIndexRange;
166  VertexIndexRange neighbors;
167  myHEDS.getNeighboringVertices( v, neighbors );
168  for ( Vertex nv : neighbors ) if ( pred( nv ) ) *it++ = nv;
169 }
170 
171 //-----------------------------------------------------------------------------
172 template <typename TPoint>
173 inline
174 typename DGtal::TriangulatedSurface<TPoint>::ArcRange
175 DGtal::TriangulatedSurface<TPoint>::outArcs( const Vertex & v ) const
176 {
177  ArcRange result;
178  const Index start_hei = myHEDS.halfEdgeIndexFromVertexIndex( v );
179  Index hei = start_hei;
180  do
181  {
182  const HalfEdge& he = myHEDS.halfEdge( hei );
183  if( INVALID_FACE != he.face ) result.push_back( hei );
184  hei = myHEDS.halfEdge( he.opposite ).next;
185  }
186  while ( hei != start_hei );
187  return result;
188 }
189 
190 //-----------------------------------------------------------------------------
191 template <typename TPoint>
192 inline
193 typename DGtal::TriangulatedSurface<TPoint>::ArcRange
194 DGtal::TriangulatedSurface<TPoint>::inArcs( const Vertex & v ) const
195 {
196  ArcRange result;
197  const Index start_hei = myHEDS.halfEdgeIndexFromVertexIndex( v );
198  Index hei = start_hei;
199  do
200  {
201  const HalfEdge& he = myHEDS.halfEdge( hei );
202  if( INVALID_FACE != he.face ) result.push_back( he.opposite );
203  hei = myHEDS.halfEdge( he.opposite ).next;
204  }
205  while ( hei != start_hei );
206  return result;
207 }
208 
209 //-----------------------------------------------------------------------------
210 template <typename TPoint>
211 inline
212 typename DGtal::TriangulatedSurface<TPoint>::FaceRange
213 DGtal::TriangulatedSurface<TPoint>::facesAroundVertex( const Vertex & v ) const
214 {
215  FaceRange result;
216  const Index start_hei = myHEDS.halfEdgeIndexFromVertexIndex( v );
217  Index hei = start_hei;
218  do
219  {
220  const HalfEdge& he = myHEDS.halfEdge( hei );
221  if( INVALID_FACE != he.face ) result.push_back( he.face );
222  hei = myHEDS.halfEdge( he.opposite ).next;
223  }
224  while ( hei != start_hei );
225  return result;
226 }
227 
228 //-----------------------------------------------------------------------------
229 template <typename TPoint>
230 inline
231 typename DGtal::TriangulatedSurface<TPoint>::Vertex
232 DGtal::TriangulatedSurface<TPoint>::head( const Arc & a ) const
233 {
234  return myHEDS.halfEdge( a ).toVertex;
235 }
236 
237 //-----------------------------------------------------------------------------
238 template <typename TPoint>
239 inline
240 typename DGtal::TriangulatedSurface<TPoint>::Vertex
241 DGtal::TriangulatedSurface<TPoint>::tail( const Arc & a ) const
242 {
243  return head( opposite( a ) );
244 }
245 
246 //-----------------------------------------------------------------------------
247 template <typename TPoint>
248 inline
249 typename DGtal::TriangulatedSurface<TPoint>::Arc
250 DGtal::TriangulatedSurface<TPoint>::opposite( const Arc & a ) const
251 {
252  return myHEDS.halfEdge( a ).opposite;
253 }
254 
255 //-----------------------------------------------------------------------------
256 template <typename TPoint>
257 inline
258 typename DGtal::TriangulatedSurface<TPoint>::Arc
259 DGtal::TriangulatedSurface<TPoint>::next( const Arc & a ) const
260 {
261  return myHEDS.halfEdge( a ).next;
262 }
263 //-----------------------------------------------------------------------------
264 template <typename TPoint>
265 inline
266 typename DGtal::TriangulatedSurface<TPoint>::Arc
267 DGtal::TriangulatedSurface<TPoint>::arc
268 ( const Vertex & t, const Vertex & h ) const
269 {
270  return myHEDS.findHalfEdgeIndexFromArc( t, h );
271 }
272 
273 //-----------------------------------------------------------------------------
274 template <typename TPoint>
275 inline
276 typename DGtal::TriangulatedSurface<TPoint>::Face
277 DGtal::TriangulatedSurface<TPoint>::faceAroundArc( const Arc & a ) const
278 {
279  return myHEDS.halfEdge( a ).face;
280 }
281 //-----------------------------------------------------------------------------
282 template <typename TPoint>
283 inline
284 typename DGtal::TriangulatedSurface<TPoint>::FaceRange
285 DGtal::TriangulatedSurface<TPoint>::facesAroundArc( const Arc & a ) const
286 {
287  FaceRange result;
288  Face f = faceAroundArc( a );
289  if ( f != INVALID_FACE ) result.push_back( f );
290  return result;
291 }
292 
293 //-----------------------------------------------------------------------------
294 template <typename TPoint>
295 inline
296 typename DGtal::TriangulatedSurface<TPoint>::VertexRange
297 DGtal::TriangulatedSurface<TPoint>::verticesAroundFace( const Face & f ) const
298 {
299  VertexRange result;
300  const Index start_hei = myHEDS.halfEdgeIndexFromFaceIndex( f );
301  Index hei = start_hei;
302  do {
303  const HalfEdge& he = myHEDS.halfEdge( hei );
304  ASSERT( ( he.face == f )
305  && "[TriangulatedSurface::verticesAroundFace] invalid face." );
306  result.push_back( he.toVertex );
307  hei = he.next;
308  } while ( hei != start_hei );
309  ASSERT( result.size() == 3 );
310  return result;
311 }
312 
313 //-----------------------------------------------------------------------------
314 template <typename TPoint>
315 inline
316 typename DGtal::TriangulatedSurface<TPoint>::ArcRange
317 DGtal::TriangulatedSurface<TPoint>::arcsAroundFace( const Face & f ) const
318 {
319  ArcRange result;
320  result.reserve( 3 );
321  const Index start_hei = myHEDS.halfEdgeIndexFromFaceIndex( f );
322  Index hei = start_hei;
323  do {
324  result.push_back( hei );
325  const HalfEdge& he = myHEDS.halfEdge( hei );
326  ASSERT( ( he.face == f )
327  && "[TriangulatedSurface::arcsAroundFace] invalid face." );
328  hei = he.next;
329  } while ( hei != start_hei );
330  ASSERT( result.size() == 3 );
331  return result;
332 }
333 
334 //-----------------------------------------------------------------------------
335 template <typename TPoint>
336 inline
337 bool
338 DGtal::TriangulatedSurface<TPoint>::isVertexBoundary( const Vertex& v ) const
339 {
340  return myHEDS.isVertexBoundary( v );
341 }
342 
343 //-----------------------------------------------------------------------------
344 template <typename TPoint>
345 inline
346 bool
347 DGtal::TriangulatedSurface<TPoint>::isArcBoundary( const Arc& v ) const
348 {
349  return INVALID_FACE == myHEDS.halfEdge( v ).face;
350 }
351 
352 //-----------------------------------------------------------------------------
353 template <typename TPoint>
354 inline
355 typename DGtal::TriangulatedSurface<TPoint>::VertexRange
356 DGtal::TriangulatedSurface<TPoint>::verticesOfFacesAroundArc( Arc a ) const
357 {
358  Arc a2 = opposite( a );
359  if ( isArcBoundary( a ) )
360  {
361  VertexRange V( 3 );
362  V[ 0 ] = head( a );
363  V[ 1 ] = head( a2 );
364  V[ 2 ] = head( next( a2 ) );
365  return V;
366  }
367  else if ( isArcBoundary( a2 ) )
368  {
369  VertexRange V( 3 );
370  V[ 0 ] = head( a );
371  V[ 1 ] = head( next( a ) );
372  V[ 2 ] = head( a2 );
373  return V;
374  }
375  else
376  {
377  VertexRange V( 4 );
378  V[ 0 ] = head( a );
379  V[ 1 ] = head( next( a ) );
380  V[ 2 ] = head( a2 );
381  V[ 3 ] = head( next( a2 ) );
382  return V;
383  }
384 }
385 
386 //-----------------------------------------------------------------------------
387 template <typename TPoint>
388 inline
389 typename DGtal::TriangulatedSurface<TPoint>::FaceRange
390 DGtal::TriangulatedSurface<TPoint>::allFaces() const
391 {
392  FaceRange result( nbFaces() );
393  for ( Face fi = 0; fi < result.size(); ++fi )
394  result[ fi ] = fi;
395  return result;
396 }
397 //-----------------------------------------------------------------------------
398 template <typename TPoint>
399 inline
400 typename DGtal::TriangulatedSurface<TPoint>::ArcRange
401 DGtal::TriangulatedSurface<TPoint>::allArcs() const
402 {
403  ArcRange result( nbArcs() );
404  for ( Arc fi = 0; fi < result.size(); ++fi )
405  result[ fi ] = fi;
406  return result;
407 }
408 //-----------------------------------------------------------------------------
409 template <typename TPoint>
410 inline
411 typename DGtal::TriangulatedSurface<TPoint>::VertexRange
412 DGtal::TriangulatedSurface<TPoint>::allVertices() const
413 {
414  VertexRange result( nbVertices() );
415  for ( Vertex fi = 0; fi < result.size(); ++fi )
416  result[ fi ] = fi;
417  return result;
418 }
419 
420 //-----------------------------------------------------------------------------
421 template <typename TPoint>
422 inline
423 typename DGtal::TriangulatedSurface<TPoint>::ArcRange
424 DGtal::TriangulatedSurface<TPoint>::allBoundaryArcs() const
425 {
426  return myHEDS.boundaryHalfEdgeIndices();
427 }
428 
429 //-----------------------------------------------------------------------------
430 template <typename TPoint>
431 inline
432 typename DGtal::TriangulatedSurface<TPoint>::VertexRange
433 DGtal::TriangulatedSurface<TPoint>::allBoundaryVertices() const
434 {
435  return myHEDS.boundaryVertices();
436 }
437 
438 //-----------------------------------------------------------------------------
439 template <typename TPoint>
440 inline
441 bool
442 DGtal::TriangulatedSurface<TPoint>::isFlippable( const Arc a ) const
443 {
444  if ( isArcBoundary( a ) || isArcBoundary( opposite( a ) ) ) return false;
445  const auto v1 = head( next( a ) );
446  const auto v2 = head( next( opposite( a ) ) );
447  std::vector< Index > neighbors_v1;
448  auto outIt = std::back_inserter( neighbors_v1 );
449  writeNeighbors( outIt, v1 );
450  const auto itv2 = std::find( neighbors_v1.cbegin(), neighbors_v1.cend(), v2 );
451  return itv2 == neighbors_v1.cend();
452 }
453 
454 //-----------------------------------------------------------------------------
455 template <typename TPoint>
456 inline
457 void
458 DGtal::TriangulatedSurface<TPoint>::flip( const Arc a )
459 {
460  myHEDS.flip( a, false );
461 }
462 
463 
464 //-----------------------------------------------------------------------------
465 template <typename TPoint>
466 inline
467 typename DGtal::TriangulatedSurface<TPoint>::Vertex
468 DGtal::TriangulatedSurface<TPoint>::split( const Arc a, const Point& data )
469 {
470  Vertex v = myHEDS.split( a, false );
471  ASSERT( v == myPositions.size() );
472  myPositions.push_back( data );
473  return v;
474 }
475 
476 //-----------------------------------------------------------------------------
477 template <typename TPoint>
478 inline
479 bool
480 DGtal::TriangulatedSurface<TPoint>::isMergeable( const Arc a ) const
481 {
482  const Vertex v3 = head( next( a ) );
483  if ( degree( v3 ) < 4 ) return false;
484  const Vertex v4 = head( next( opposite( a ) ) );
485  if ( degree( v4 ) < 4 ) return false;
486  auto A1 = outArcs( head( a ) );
487  auto A2 = outArcs( tail( a ) );
488  std::vector<Vertex> V1, V2;
489  for ( Arc a1 : A1 ) V1.push_back( head( a1 ) );
490  for ( Arc a2 : A2 ) V2.push_back( head( a2 ) );
491  std::sort( V1.begin(), V1.end() );
492  std::sort( V2.begin(), V2.end() );
493  std::vector<Vertex> VI( V1.size() );
494  auto it = std::set_intersection( V1.begin(), V1.end(), V2.begin(), V2.end(),
495  VI.begin() );
496  if ( ( it - VI.begin() ) != 2 ) return false;
497  return myHEDS.isMergeable( a );
498 }
499 
500 //-----------------------------------------------------------------------------
501 template <typename TPoint>
502 inline
503 typename DGtal::TriangulatedSurface<TPoint>::Vertex
504 DGtal::TriangulatedSurface<TPoint>::merge( const Arc a, const Point& data )
505 {
506  const Vertex v_sup = head( a );
507  const Vertex v = myHEDS.merge( a, false );
508  ASSERT( v < myPositions.size() );
509  myPositions[ v ] = data;
510  myPositions[ v_sup ] = myPositions.back();
511  myPositions.pop_back();
512  return v;
513 }
514 
515 ///////////////////////////////////////////////////////////////////////////////
516 // Interface - public :
517 
518 /**
519  * Writes/Displays the object on an output stream.
520  * @param out the output stream where the object is written.
521  */
522 template <typename TPoint>
523 inline
524 void
525 DGtal::TriangulatedSurface<TPoint>::selfDisplay ( std::ostream & out ) const
526 {
527  out << "[TriangulatedSurface #V=" << myHEDS.nbVertices()
528  << " #E=" << myHEDS.nbEdges() << " #F=" << myHEDS.nbFaces()
529  << " Chi=" << Euler() << "]";
530 }
531 
532 /**
533  * Checks the validity/consistency of the object.
534  * @return 'true' if the object is valid, 'false' otherwise.
535  */
536 template <typename TPoint>
537 inline
538 bool
539 DGtal::TriangulatedSurface<TPoint>::isValid() const
540 {
541  return isHEDSValid;
542 }
543 
544 
545 
546 ///////////////////////////////////////////////////////////////////////////////
547 // Implementation of inline functions //
548 
549 template <typename TPoint>
550 inline
551 std::ostream&
552 DGtal::operator<< ( std::ostream & out,
553  const TriangulatedSurface<TPoint> & object )
554 {
555  object.selfDisplay( out );
556  return out;
557 }
558 
559 // //
560 ///////////////////////////////////////////////////////////////////////////////
561 
562