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