DGtal  1.0.0
HalfEdgeDataStructure.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 HalfEdgeDataStructure.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/03
23  *
24  * Implementation of inline methods defined in HalfEdgeDataStructure.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 inline
43 DGtal::HalfEdgeDataStructure::Size
44 DGtal::HalfEdgeDataStructure::getUnorderedEdgesFromPolygonalFaces
45 ( const std::vector<PolygonalFace>& polygonal_faces, std::vector< Edge >& edges_out )
46 {
47  typedef std::set< Edge > EdgeSet;
48  typedef std::set< VertexIndex > VertexIndexSet;
49  VertexIndexSet vertexSet;
50  EdgeSet edgeSet;
51  for( const PolygonalFace& P : polygonal_faces )
52  {
53  ASSERT( P.size() >= 3 ); // a face has at least 3 vertices
54  for ( unsigned int i = 0; i < P.size(); ++i )
55  {
56  edgeSet.insert( Edge( P[ i ], P[ (i+1) % P.size() ] ) );
57  vertexSet.insert( P[ i ] );
58  }
59  }
60  edges_out.resize( edgeSet.size() );
61  Size e = 0;
62  for ( const Edge& edge : edgeSet )
63  {
64  edges_out.at(e) = edge;
65  ++e;
66  }
67  return vertexSet.size();
68 }
69 
70 //-----------------------------------------------------------------------------
71 inline
72 bool
73 DGtal::HalfEdgeDataStructure::
74 build( const Size num_vertices,
75  const std::vector<Triangle>& triangles,
76  const std::vector<Edge>& edges )
77 {
78  bool ok = true;
79  Arc2FaceIndex de2fi;
80  // Visiting triangles to associates faces to arcs.
81  FaceIndex fi = 0;
82  for( const Triangle& T : triangles )
83  {
84  auto it01 = de2fi.find( Arc( T.v[0], T.v[1] ) );
85  auto it12 = de2fi.find( Arc( T.v[1], T.v[2] ) );
86  auto it20 = de2fi.find( Arc( T.v[2], T.v[0] ) );
87  if ( ( it01 != de2fi.end() ) || ( it12 != de2fi.end() ) || ( it20 != de2fi.end() ) )
88  {
89  trace.warning() << "[HalfEdgeDataStructure::build] Some arcs belongs to more than one face. Dropping triangle."
90  << " Triangle (" << T.v[ 0 ] << "," << T.v[ 1 ] << "," << T.v[ 2 ] << ")"
91  << " arc01 " << ( it01 != de2fi.end() ? it01->second : HALF_EDGE_INVALID_INDEX )
92  << " arc12 " << ( it12 != de2fi.end() ? it12->second : HALF_EDGE_INVALID_INDEX )
93  << " arc20 " << ( it20 != de2fi.end() ? it20->second : HALF_EDGE_INVALID_INDEX )
94  << std::endl;
95  ok = false;
96  // JOL: if we continue here, we may create infinite loops
97  // afterwards. Stopping now.
98  break;
99  }
100  de2fi[ Arc( T.v[0], T.v[1] ) ] = fi;
101  de2fi[ Arc( T.v[1], T.v[2] ) ] = fi;
102  de2fi[ Arc( T.v[2], T.v[0] ) ] = fi;
103  fi++;
104  }
105  // JOL: if we continue here, we may create infinite loops
106  // afterwards. Stopping now.
107  if ( !ok ) return false;
108  // Clearing and resizing data structure to start from scratch and
109  // prepare everything.
110  clear();
111  Size num_edges = edges.size();
112  Size num_triangles = triangles.size();
113  myVertexHalfEdges.resize( num_vertices, HALF_EDGE_INVALID_INDEX );
114  myFaceHalfEdges.resize( num_triangles, HALF_EDGE_INVALID_INDEX );
115  myEdgeHalfEdges.resize( num_edges, HALF_EDGE_INVALID_INDEX );
116  myHalfEdges.reserve( num_edges*2 );
117  // Visiting edges to connect everything.
118  for( EdgeIndex ei = 0; ei < num_edges; ++ei )
119  {
120  const Edge& edge = edges[ ei ];
121 
122  // Add the halfedge_t structures to the end of the list.
123  const Index he0index = myHalfEdges.size();
124  myHalfEdges.push_back( HalfEdge() );
125  HalfEdge& he0 = myHalfEdges.back();
126  const Index he1index = myHalfEdges.size();
127  myHalfEdges.push_back( HalfEdge() );
128  HalfEdge& he1 = myHalfEdges.back();
129 
130  // The face will be HALF_EDGE_INVALID_INDEX if it is a boundary half-edge.
131  he0.face = arc2FaceIndex( de2fi, edge.v[0], edge.v[1] );
132  he0.toVertex = edge.v[1];
133  he0.edge = ei;
134 
135  // The face will be HALF_EDGE_INVALID_INDEX if it is a boundary half-edge.
136  he1.face = arc2FaceIndex( de2fi, edge.v[1], edge.v[0] );
137  he1.toVertex = edge.v[0];
138  he1.edge = ei;
139 
140  // Store the opposite half-edge index.
141  he0.opposite = he1index;
142  he1.opposite = he0index;
143 
144  // Also store the index in our myArc2Index map.
145  assert( myArc2Index.find( Arc( edge.v[0], edge.v[1] ) ) == myArc2Index.end() );
146  assert( myArc2Index.find( Arc( edge.v[1], edge.v[0] ) ) == myArc2Index.end() );
147  myArc2Index[ std::make_pair( edge.v[0], edge.v[1] ) ] = he0index;
148  myArc2Index[ std::make_pair( edge.v[1], edge.v[0] ) ] = he1index;
149 
150  // If the vertex pointed to by a half-edge doesn't yet have an out-going
151  // halfedge, store the opposite halfedge.
152  // Also, if the vertex is a boundary vertex, make sure its
153  // out-going halfedge is a boundary halfedge.
154  // NOTE: Halfedge data structure can't properly handle butterfly vertices.
155  // If the mesh has butterfly vertices, there will be multiple outgoing
156  // boundary halfedges. Because we have to pick one as the vertex's outgoing
157  // halfedge, we can't iterate over all neighbors, only a single wing of the
158  // butterfly.
159  if( myVertexHalfEdges[ he0.toVertex ] == HALF_EDGE_INVALID_INDEX || HALF_EDGE_INVALID_INDEX == he1.face )
160  myVertexHalfEdges[ he0.toVertex ] = he0.opposite;
161  if( myVertexHalfEdges[ he1.toVertex ] == HALF_EDGE_INVALID_INDEX || HALF_EDGE_INVALID_INDEX == he0.face )
162  myVertexHalfEdges[ he1.toVertex ] = he1.opposite;
163 
164  // If the face pointed to by a half-edge doesn't yet have a
165  // halfedge pointing to it, store the halfedge.
166  if( HALF_EDGE_INVALID_INDEX != he0.face && myFaceHalfEdges[ he0.face ] == HALF_EDGE_INVALID_INDEX )
167  myFaceHalfEdges[ he0.face ] = he0index;
168  if( HALF_EDGE_INVALID_INDEX != he1.face && myFaceHalfEdges[ he1.face ] == HALF_EDGE_INVALID_INDEX )
169  myFaceHalfEdges[ he1.face ] = he1index;
170 
171  // Store one of the half-edges for the edge.
172  assert( myEdgeHalfEdges[ ei ] == HALF_EDGE_INVALID_INDEX );
173  myEdgeHalfEdges[ ei ] = he0index;
174  }
175 
176  // Now that all the half-edges are created, set the remaining next_he field.
177  // We can't yet handle boundary halfedges, so store them for later.
178  HalfEdgeIndexRange boundary_heis;
179  for( Index hei = 0; hei < myHalfEdges.size(); ++hei )
180  {
181  HalfEdge& he = myHalfEdges.at( hei );
182  // Store boundary halfedges for later.
183  if( HALF_EDGE_INVALID_INDEX == he.face )
184  {
185  boundary_heis.push_back( hei );
186  continue;
187  }
188 
189  const Triangle& face = triangles[ he.face ];
190  const VertexIndex i = he.toVertex;
191  VertexIndex j = HALF_EDGE_INVALID_INDEX;
192  if( face.v[0] == i ) j = face.v[1];
193  else if( face.v[1] == i ) j = face.v[2];
194  else if( face.v[2] == i ) j = face.v[0];
195  ASSERT( HALF_EDGE_INVALID_INDEX != j );
196  he.next = myArc2Index[ Arc( i, j ) ];
197  }
198 
199  // Make a map from vertices to boundary halfedges (indices)
200  // originating from them. NOTE: There will only be multiple
201  // originating boundary halfedges at butterfly vertices.
202  std::map< VertexIndex, std::set< Index > > vertex2outgoing_boundary_hei;
203  for ( Index hei : boundary_heis )
204  {
205  const VertexIndex origin_v = myHalfEdges[ myHalfEdges[ hei ].opposite ].toVertex;
206  vertex2outgoing_boundary_hei[ origin_v ].insert( hei );
207  if( vertex2outgoing_boundary_hei[ origin_v ].size() > 1 )
208  {
209  trace.error() << "Butterfly vertex encountered." << std::endl;
210  ok = false;
211  }
212  }
213 
214  // For each boundary halfedge, make its next_he one of the boundary halfedges
215  // originating at its to_vertex.
216  for ( Index hei : boundary_heis )
217  {
218  HalfEdge& he = myHalfEdges[ hei ];
219 
220  std::set< Index >& outgoing = vertex2outgoing_boundary_hei[ he.toVertex ];
221  if( !outgoing.empty() )
222  {
223  std::set< Index >::iterator outgoing_hei = outgoing.begin();
224  he.next = *outgoing_hei;
225  outgoing.erase( outgoing_hei );
226  }
227  }
228 
229  #ifndef NDEBUG
230  for( auto it = vertex2outgoing_boundary_hei.begin();
231  it != vertex2outgoing_boundary_hei.end(); ++it )
232  {
233  ASSERT( it->second.empty() );
234  }
235  #endif
236  return ok;
237 }
238 
239 
240 //-----------------------------------------------------------------------------
241 inline
242 bool
243 DGtal::HalfEdgeDataStructure::
244 build( const Size num_vertices,
245  const std::vector<PolygonalFace>& polygonal_faces,
246  const std::vector<Edge>& edges )
247 {
248  // TODO
249  bool ok = true;
250  Arc2FaceIndex de2fi;
251  // Visiting triangles to associates faces to arcs.
252  FaceIndex fi = 0;
253  for( const PolygonalFace& P : polygonal_faces )
254  {
255  ASSERT( P.size() >= 3 ); // a face has at least 3 vertices
256  bool face_ok = true;
257  for ( unsigned int i = 0; i < P.size(); ++i )
258  {
259  const VertexIndex v0 = P[ i ];
260  const VertexIndex v1 = P[ (i+1) % P.size() ];
261  auto it01 = de2fi.find( Arc( v0, v1 ) );
262  if ( it01 != de2fi.end() )
263  {
264  trace.warning() << "[HalfEdgeDataStructure::build] Arc (" << v0 << "," << v1 << ")"
265  << " of polygonal face " << fi << " belongs to more than one face. "
266  << " Dropping face " << fi << std::endl;
267  face_ok = false;
268  break;
269  }
270  }
271  if ( face_ok )
272  for ( unsigned int i = 0; i < P.size(); ++i )
273  {
274  const VertexIndex v0 = P[ i ];
275  const VertexIndex v1 = P[ (i+1) % P.size() ];
276  de2fi[ Arc( v0, v1 ) ] = fi;
277  }
278  // JOL: if we continue here, we may create infinite loops
279  // afterwards. Stopping now.
280  else return false;
281  fi++;
282  }
283  // Clearing and resizing data structure to start from scratch and
284  // prepare everything.
285  clear();
286  Size num_edges = edges.size();
287  Size num_polygons = polygonal_faces.size();
288  myVertexHalfEdges.resize( num_vertices, HALF_EDGE_INVALID_INDEX );
289  myFaceHalfEdges.resize( num_polygons, HALF_EDGE_INVALID_INDEX );
290  myEdgeHalfEdges.resize( num_edges, HALF_EDGE_INVALID_INDEX );
291  myHalfEdges.reserve( num_edges*2 );
292  // Visiting edges to connect everything.
293  for( EdgeIndex ei = 0; ei < num_edges; ++ei )
294  {
295  const Edge& edge = edges[ ei ];
296 
297  // Add the halfedge_t structures to the end of the list.
298  const Index he0index = myHalfEdges.size();
299  myHalfEdges.push_back( HalfEdge() );
300  HalfEdge& he0 = myHalfEdges.back();
301  const Index he1index = myHalfEdges.size();
302  myHalfEdges.push_back( HalfEdge() );
303  HalfEdge& he1 = myHalfEdges.back();
304 
305  // The face will be HALF_EDGE_INVALID_INDEX if it is a boundary half-edge.
306  he0.face = arc2FaceIndex( de2fi, edge.v[0], edge.v[1] );
307  he0.toVertex = edge.v[1];
308  he0.edge = ei;
309 
310  // The face will be HALF_EDGE_INVALID_INDEX if it is a boundary half-edge.
311  he1.face = arc2FaceIndex( de2fi, edge.v[1], edge.v[0] );
312  he1.toVertex = edge.v[0];
313  he1.edge = ei;
314 
315  // Store the opposite half-edge index.
316  he0.opposite = he1index;
317  he1.opposite = he0index;
318 
319  // Also store the index in our myArc2Index map.
320  assert( myArc2Index.find( Arc( edge.v[0], edge.v[1] ) ) == myArc2Index.end() );
321  assert( myArc2Index.find( Arc( edge.v[1], edge.v[0] ) ) == myArc2Index.end() );
322  myArc2Index[ std::make_pair( edge.v[0], edge.v[1] ) ] = he0index;
323  myArc2Index[ std::make_pair( edge.v[1], edge.v[0] ) ] = he1index;
324 
325  // If the vertex pointed to by a half-edge doesn't yet have an out-going
326  // halfedge, store the opposite halfedge.
327  // Also, if the vertex is a boundary vertex, make sure its
328  // out-going halfedge is a boundary halfedge.
329  // NOTE: Halfedge data structure can't properly handle butterfly vertices.
330  // If the mesh has butterfly vertices, there will be multiple outgoing
331  // boundary halfedges. Because we have to pick one as the vertex's outgoing
332  // halfedge, we can't iterate over all neighbors, only a single wing of the
333  // butterfly.
334  if( myVertexHalfEdges[ he0.toVertex ] == HALF_EDGE_INVALID_INDEX
335  || HALF_EDGE_INVALID_INDEX == he1.face )
336  myVertexHalfEdges[ he0.toVertex ] = he0.opposite;
337  if( myVertexHalfEdges[ he1.toVertex ] == HALF_EDGE_INVALID_INDEX
338  || HALF_EDGE_INVALID_INDEX == he0.face )
339  myVertexHalfEdges[ he1.toVertex ] = he1.opposite;
340 
341  // If the face pointed to by a half-edge doesn't yet have a
342  // halfedge pointing to it, store the halfedge.
343  if( HALF_EDGE_INVALID_INDEX != he0.face
344  && myFaceHalfEdges[ he0.face ] == HALF_EDGE_INVALID_INDEX )
345  myFaceHalfEdges[ he0.face ] = he0index;
346  if( HALF_EDGE_INVALID_INDEX != he1.face
347  && myFaceHalfEdges[ he1.face ] == HALF_EDGE_INVALID_INDEX )
348  myFaceHalfEdges[ he1.face ] = he1index;
349 
350  // Store one of the half-edges for the edge.
351  assert( myEdgeHalfEdges[ ei ] == HALF_EDGE_INVALID_INDEX );
352  myEdgeHalfEdges[ ei ] = he0index;
353  }
354 
355  // Now that all the half-edges are created, set the remaining next_he field.
356  // We can't yet handle boundary halfedges, so store them for later.
357  HalfEdgeIndexRange boundary_heis;
358  for( Index hei = 0; hei < myHalfEdges.size(); ++hei )
359  {
360  HalfEdge& he = myHalfEdges.at( hei );
361  // Store boundary halfedges for later.
362  if( HALF_EDGE_INVALID_INDEX == he.face )
363  {
364  boundary_heis.push_back( hei );
365  continue;
366  }
367 
368  const PolygonalFace& face = polygonal_faces[ he.face ];
369  const VertexIndex i = he.toVertex;
370  auto it = std::find( face.cbegin(), face.cend(), i );
371  if ( it == face.cend() )
372  {
373  trace.error() << "[HalfEdgeDataStructure::build]"
374  << " Unable to find vertex " << i << " in face "
375  << he.face << std::endl;
376  ok = false;
377  }
378  else
379  {
380  // Go to next.
381  ++it;
382  it = ( it == face.cend() ) ? face.cbegin() : it;
383  const VertexIndex j = *it ;
384  he.next = myArc2Index[ Arc( i, j ) ];
385  }
386  }
387 
388  // Make a map from vertices to boundary halfedges (indices)
389  // originating from them. NOTE: There will only be multiple
390  // originating boundary halfedges at butterfly vertices.
391  std::map< VertexIndex, std::set< Index > > vertex2outgoing_boundary_hei;
392  for ( Index hei : boundary_heis )
393  {
394  const VertexIndex origin_v = myHalfEdges[ myHalfEdges[ hei ].opposite ].toVertex;
395  vertex2outgoing_boundary_hei[ origin_v ].insert( hei );
396  if( vertex2outgoing_boundary_hei[ origin_v ].size() > 1 )
397  {
398  trace.error() << "[HalfEdgeDataStructure::build]"
399  << " Butterfly vertex encountered at he index=" << hei
400  << std::endl;
401  ok = false;
402  }
403  }
404 
405  // For each boundary halfedge, make its next_he one of the boundary halfedges
406  // originating at its to_vertex.
407  for ( Index hei : boundary_heis )
408  {
409  HalfEdge& he = myHalfEdges[ hei ];
410 
411  std::set< Index >& outgoing = vertex2outgoing_boundary_hei[ he.toVertex ];
412  if( !outgoing.empty() )
413  {
414  std::set< Index >::iterator outgoing_hei = outgoing.begin();
415  he.next = *outgoing_hei;
416  outgoing.erase( outgoing_hei );
417  }
418  }
419 
420  #ifndef NDEBUG
421  for( auto it = vertex2outgoing_boundary_hei.begin();
422  it != vertex2outgoing_boundary_hei.end(); ++it )
423  {
424  ASSERT( it->second.empty() );
425  }
426  #endif
427  return ok;
428 }
429 
430 //-----------------------------------------------------------------------------
431 
432 
433 ///////////////////////////////////////////////////////////////////////////////
434 // Interface - public :
435 
436 /**
437  * Writes/Displays the object on an output stream.
438  * @param out the output stream where the object is written.
439  */
440 inline
441 void
442 DGtal::HalfEdgeDataStructure::selfDisplay ( std::ostream & out ) const
443 {
444  out << "[HalfEdgeDataStructure"
445  << " #he=" << myHalfEdges.size()
446  << " #V=" << myVertexHalfEdges.size()
447  << " #E=" << myEdgeHalfEdges.size()
448  << " #F=" << myFaceHalfEdges.size()
449  << "]";
450 }
451 
452 /**
453  * Checks the validity/consistency of the object.
454  * @return 'true' if the object is valid, 'false' otherwise.
455  */
456 inline
457 bool
458 DGtal::HalfEdgeDataStructure::isValid() const
459 {
460  return true;
461 }
462 
463 
464 
465 ///////////////////////////////////////////////////////////////////////////////
466 // Implementation of inline functions //
467 
468 inline
469 std::ostream&
470 DGtal::operator<< ( std::ostream & out,
471  const HalfEdgeDataStructure & object )
472 {
473  object.selfDisplay( out );
474  return out;
475 }
476 
477 // //
478 ///////////////////////////////////////////////////////////////////////////////
479 
480