DGtal 1.3.0
Loading...
Searching...
No Matches
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//-----------------------------------------------------------------------------
42template <typename TPoint>
43inline
44bool
45DGtal::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//-----------------------------------------------------------------------------
64template <typename TPoint>
65inline
66void
67DGtal::TriangulatedSurface<TPoint>::clear()
68{
69 isHEDSValid = false;
70 myHEDS.clear();
71 myPositions.clear();
72 myTriangles.clear();
73
74}
75//-----------------------------------------------------------------------------
76template <typename TPoint>
77inline
78typename DGtal::TriangulatedSurface<TPoint>::VertexIndex
79DGtal::TriangulatedSurface<TPoint>::addVertex( const Point& vdata )
80{
81 VertexIndex vi = myPositions.size();
82 myPositions.push_back( vdata );
83 return vi;
84}
85
86//-----------------------------------------------------------------------------
87template <typename TPoint>
88inline
89typename DGtal::TriangulatedSurface<TPoint>::FaceIndex
90DGtal::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//-----------------------------------------------------------------------------
98template <typename TPoint>
99inline
100typename DGtal::TriangulatedSurface<TPoint>::Point&
101DGtal::TriangulatedSurface<TPoint>::position( Vertex v )
102{
103 ASSERT( 0 <= v && v < myPositions.size() );
104 return myPositions[ v ];
105}
106//-----------------------------------------------------------------------------
107template <typename TPoint>
108inline
109const typename DGtal::TriangulatedSurface<TPoint>::Point&
110DGtal::TriangulatedSurface<TPoint>::position( Vertex v ) const
111{
112 ASSERT( 0 <= v && v < myPositions.size() );
113 return myPositions[ v ];
114}
115//-----------------------------------------------------------------------------
116template <typename TPoint>
117inline
118typename DGtal::TriangulatedSurface<TPoint>::Size
119DGtal::TriangulatedSurface<TPoint>::size() const
120{
121 return myPositions.size();
122}
123//-----------------------------------------------------------------------------
124template <typename TPoint>
125inline
126typename DGtal::TriangulatedSurface<TPoint>::Size
127DGtal::TriangulatedSurface<TPoint>::bestCapacity() const
128{
129 return 8;
130}
131//-----------------------------------------------------------------------------
132template <typename TPoint>
133inline
134typename DGtal::TriangulatedSurface<TPoint>::Size
135DGtal::TriangulatedSurface<TPoint>::degree( const Vertex & v ) const
136{
137 ASSERT( isValid() );
138 return myHEDS.nbNeighboringVertices( v );
139}
140
141//-----------------------------------------------------------------------------
142template <typename TPoint>
143template <typename OutputIterator>
144inline
145void
146DGtal::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//-----------------------------------------------------------------------------
157template <typename TPoint>
158template <typename OutputIterator, typename VertexPredicate>
159inline
160void
161DGtal::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//-----------------------------------------------------------------------------
172template <typename TPoint>
173inline
174typename DGtal::TriangulatedSurface<TPoint>::ArcRange
175DGtal::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//-----------------------------------------------------------------------------
191template <typename TPoint>
192inline
193typename DGtal::TriangulatedSurface<TPoint>::ArcRange
194DGtal::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//-----------------------------------------------------------------------------
210template <typename TPoint>
211inline
212typename DGtal::TriangulatedSurface<TPoint>::FaceRange
213DGtal::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//-----------------------------------------------------------------------------
229template <typename TPoint>
230inline
231typename DGtal::TriangulatedSurface<TPoint>::Vertex
232DGtal::TriangulatedSurface<TPoint>::head( const Arc & a ) const
233{
234 return myHEDS.halfEdge( a ).toVertex;
235}
236
237//-----------------------------------------------------------------------------
238template <typename TPoint>
239inline
240typename DGtal::TriangulatedSurface<TPoint>::Vertex
241DGtal::TriangulatedSurface<TPoint>::tail( const Arc & a ) const
242{
243 return head( opposite( a ) );
244}
245
246//-----------------------------------------------------------------------------
247template <typename TPoint>
248inline
249typename DGtal::TriangulatedSurface<TPoint>::Arc
250DGtal::TriangulatedSurface<TPoint>::opposite( const Arc & a ) const
251{
252 return myHEDS.halfEdge( a ).opposite;
253}
254
255//-----------------------------------------------------------------------------
256template <typename TPoint>
257inline
258typename DGtal::TriangulatedSurface<TPoint>::Arc
259DGtal::TriangulatedSurface<TPoint>::next( const Arc & a ) const
260{
261 return myHEDS.halfEdge( a ).next;
262}
263//-----------------------------------------------------------------------------
264template <typename TPoint>
265inline
266typename DGtal::TriangulatedSurface<TPoint>::Arc
267DGtal::TriangulatedSurface<TPoint>::arc
268( const Vertex & t, const Vertex & h ) const
269{
270 return myHEDS.findHalfEdgeIndexFromArc( t, h );
271}
272
273//-----------------------------------------------------------------------------
274template <typename TPoint>
275inline
276typename DGtal::TriangulatedSurface<TPoint>::Face
277DGtal::TriangulatedSurface<TPoint>::faceAroundArc( const Arc & a ) const
278{
279 return myHEDS.halfEdge( a ).face;
280}
281//-----------------------------------------------------------------------------
282template <typename TPoint>
283inline
284typename DGtal::TriangulatedSurface<TPoint>::FaceRange
285DGtal::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//-----------------------------------------------------------------------------
294template <typename TPoint>
295inline
296typename DGtal::TriangulatedSurface<TPoint>::VertexRange
297DGtal::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//-----------------------------------------------------------------------------
314template <typename TPoint>
315inline
316typename DGtal::TriangulatedSurface<TPoint>::ArcRange
317DGtal::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//-----------------------------------------------------------------------------
335template <typename TPoint>
336inline
337bool
338DGtal::TriangulatedSurface<TPoint>::isVertexBoundary( const Vertex& v ) const
339{
340 return myHEDS.isVertexBoundary( v );
341}
342
343//-----------------------------------------------------------------------------
344template <typename TPoint>
345inline
346bool
347DGtal::TriangulatedSurface<TPoint>::isArcBoundary( const Arc& v ) const
348{
349 return INVALID_FACE == myHEDS.halfEdge( v ).face;
350}
351
352//-----------------------------------------------------------------------------
353template <typename TPoint>
354inline
355typename DGtal::TriangulatedSurface<TPoint>::VertexRange
356DGtal::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//-----------------------------------------------------------------------------
387template <typename TPoint>
388inline
389typename DGtal::TriangulatedSurface<TPoint>::FaceRange
390DGtal::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//-----------------------------------------------------------------------------
398template <typename TPoint>
399inline
400typename DGtal::TriangulatedSurface<TPoint>::ArcRange
401DGtal::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//-----------------------------------------------------------------------------
409template <typename TPoint>
410inline
411typename DGtal::TriangulatedSurface<TPoint>::VertexRange
412DGtal::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//-----------------------------------------------------------------------------
421template <typename TPoint>
422inline
423typename DGtal::TriangulatedSurface<TPoint>::ArcRange
424DGtal::TriangulatedSurface<TPoint>::allBoundaryArcs() const
425{
426 return myHEDS.boundaryHalfEdgeIndices();
427}
428
429//-----------------------------------------------------------------------------
430template <typename TPoint>
431inline
432typename DGtal::TriangulatedSurface<TPoint>::VertexRange
433DGtal::TriangulatedSurface<TPoint>::allBoundaryVertices() const
434{
435 return myHEDS.boundaryVertices();
436}
437
438//-----------------------------------------------------------------------------
439template <typename TPoint>
440inline
441bool
442DGtal::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//-----------------------------------------------------------------------------
455template <typename TPoint>
456inline
457void
458DGtal::TriangulatedSurface<TPoint>::flip( const Arc a )
459{
460 myHEDS.flip( a, false );
461}
462
463
464//-----------------------------------------------------------------------------
465template <typename TPoint>
466inline
467typename DGtal::TriangulatedSurface<TPoint>::Vertex
468DGtal::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//-----------------------------------------------------------------------------
477template <typename TPoint>
478inline
479bool
480DGtal::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//-----------------------------------------------------------------------------
501template <typename TPoint>
502inline
503typename DGtal::TriangulatedSurface<TPoint>::Vertex
504DGtal::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 */
522template <typename TPoint>
523inline
524void
525DGtal::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 */
536template <typename TPoint>
537inline
538bool
539DGtal::TriangulatedSurface<TPoint>::isValid() const
540{
541 return isHEDSValid;
542}
543
544
545
546///////////////////////////////////////////////////////////////////////////////
547// Implementation of inline functions //
548
549template <typename TPoint>
550inline
551std::ostream&
552DGtal::operator<< ( std::ostream & out,
553 const TriangulatedSurface<TPoint> & object )
554{
555 object.selfDisplay( out );
556 return out;
557}
558
559// //
560///////////////////////////////////////////////////////////////////////////////
561
562
Generated on Sun Nov 27 2022 15:15:51 for DGtal by doxygen 1.9.5