31 #if defined(HalfEdgeDataStructure_RECURSES)
32 #error Recursive header files inclusion detected in HalfEdgeDataStructure.h
33 #else // defined(HalfEdgeDataStructure_RECURSES)
35 #define HalfEdgeDataStructure_RECURSES
37 #if !defined HalfEdgeDataStructure_h
39 #define HalfEdgeDataStructure_h
45 #include "DGtal/base/Common.h"
116 typedef std::pair<VertexIndex, VertexIndex>
Arc;
143 if ( vi <= vj ) { v[0] = vi; v[1] = vj; }
144 else { v[0] = vj; v[1] = vi; }
157 std::array<VertexIndex,3>
v;
170 v[0] = v[1] = v[2] = -1;
231 (
const std::vector<Triangle>& triangles, std::vector< Edge >& edges_out )
233 typedef std::set< Edge > EdgeSet;
234 typedef std::set< VertexIndex > VertexIndexSet;
235 VertexIndexSet vertexSet;
237 for(
const Triangle& T : triangles )
239 edgeSet.insert(
Edge( T.i(), T.j() ) );
240 edgeSet.insert(
Edge( T.j(), T.k() ) );
241 edgeSet.insert(
Edge( T.k(), T.i() ) );
242 vertexSet.insert( T.i() );
243 vertexSet.insert( T.j() );
244 vertexSet.insert( T.k() );
246 edges_out.resize( edgeSet.size() );
248 for (
const Edge& edge : edgeSet )
250 edges_out.at(e) = edge;
253 return vertexSet.size();
272 (
const std::vector<PolygonalFace>& polygonal_faces, std::vector< Edge >& edges_out );
297 const std::vector<Triangle>& triangles,
298 const std::vector<Edge>& edges );
323 const std::vector<PolygonalFace>& polygonal_faces,
324 const std::vector<Edge>& edges );
334 bool build(
const std::vector<Triangle>& triangles )
336 std::vector<Edge> edges;
338 return build( nbVtx, triangles, edges );
349 bool build(
const std::vector<PolygonalFace>& polygonal_faces )
351 std::vector<Edge> edges;
353 return build( nbVtx, polygonal_faces, edges );
436 if ( he.
toVertex == arc.second )
return i;
463 Index hei = start_hei;
470 while ( hei != start_hei );
488 Index hei = start_hei;
495 while ( hei != start_hei );
505 Index hei = start_hei;
512 while ( hei != start_hei );
554 std::vector< Index > result;
559 result.push_back( hei );
568 std::vector< Arc > result;
584 const Index start = hei;
589 while ( hei != start );
607 const Index start = hei;
613 while ( hei != start );
639 if ( (
nbSides( hei ) != 3 ) || (
nbSides( hei2 ) != 3 ) )
return false;
645 const auto it_v2 = std::find( neighb_v1.cbegin(), neighb_v1.cend(), v2 );
646 return it_v2 == neighb_v1.cend();
664 void flip(
const Index hei,
bool update_arc2index =
true )
666 const Index i1 = hei;
698 if ( update_arc2index )
750 he0.
edge = new_edgei;
754 he1.
face = new_facei;
755 he1.
edge = new_edgei;
757 he1.
next = new_hei + 2;
759 he2.
face = new_facei;
760 he2.
edge = new_edgei + 1;
765 he3.
edge = new_edgei + 2;
769 he4.
face = new_facei + 1;
770 he4.
edge = new_edgei + 2;
772 he4.
next = new_hei + 5;
774 he5.
face = new_facei + 1;
783 hej.
edge = new_edgei + 1;
785 hej.
next = new_hei + 3;
786 hei_next.
face = new_facei;
787 hei_next.
next = new_hei + 1;
788 hej_next.
face = new_facei + 1;
789 hej_next.
next = new_hei + 4;
799 if ( update_arc2index )
866 const Index i1 = hei;
900 std::vector<VertexIndex> outer_v;
901 std::vector<Index> inner_he;
902 std::vector<Index> outer_he;
908 inner_he.push_back( i );
909 outer_he.push_back( iopp );
914 }
while ( i != i1n );
940 if ( update_arc2index ) {
941 for ( std::size_t j = 0; j < outer_v.size(); ++j ) {
945 for ( std::size_t j = 1; j < ( outer_v.size() - 2 ); ++j ) {
956 if ( ( new_nbV1 != nbV1+nbV2-4 )
957 || ( new_nbV3 != nbV3 -1 )
958 || ( new_nbV4 != nbV4 -1 ) )
963 <<
" nbV4=" << nbV4 << std::endl
964 <<
" new_nbV1=" << new_nbV1
965 <<
" new_nbV3=" << new_nbV3
966 <<
" new_nbV4=" << new_nbV4 << std::endl;
970 std::array< EdgeIndex, 3 > E = { e1, e2, e3 };
971 std::sort( E.begin(), E.end(), std::greater<EdgeIndex>() );
972 for (
Index e : E ) {
975 std::array< FaceIndex, 2 > F = { f1, f2 };
976 std::sort( F.begin(), F.end(), std::greater<FaceIndex>() );
977 for (
Index f : F ) {
980 std::array< Index, 6 > T = { i1, i1n, i1nn, i2, i2n, i2nn };
981 std::sort( T.begin(), T.end(), std::greater<Index>() );
982 for (
Index t : T ) {
1007 if ( update_arc2index ) {
1030 ASSERT( hej.
edge == ej );
1031 ASSERT( hejopp.
edge == ej );
1049 ASSERT( hek.
face == fj );
1087 if ( update_arc2index ) {
1118 <<
"half-edge " << i
1119 <<
" has invalid next half-edge " << he.
next
1125 <<
"half-edge " << i
1126 <<
" has invalid opposite half-edge " << he.
opposite
1132 <<
"half-edge " << i
1133 <<
" has invalid toVertex " << he.
toVertex
1139 <<
"half-edge " << i
1140 <<
" has invalid face " << he.
face
1151 <<
"half-edge " << i <<
" has invalid opposite half-edge." << std::endl;
1156 <<
"half-edge " << i <<
" has opposite half-edge " << j
1157 <<
" but the latter has opposite half-edge " <<
myHalfEdges[ j ].opposite << std::endl;
1164 <<
"half-edge " << i <<
" and its opposite half-edge " << j
1165 <<
" have the same toVertex " << vi << std::endl;
1170 <<
"half-edge " << i
1171 <<
" points to an invalid vertex " << vi << std::endl;
1176 <<
"opposite half-edge " << j
1177 <<
" points to an invalid vertex " << vj << std::endl;
1189 <<
"vertex " << i <<
" is associated to half-edge " << j
1190 <<
" but its opposite half-edge " << jopp <<
" points to vertex " << ip << std::endl;
1200 <<
"face " << f <<
" is associated to half-edge " << i
1201 <<
" but its associated face is " <<
myHalfEdges[ i ].face << std::endl;
1209 const Index start = i;
1212 if ( he.
face != f ) {
1214 <<
"when turning around face " << f <<
", half-edge " << i
1215 <<
" is associated to face " << he.
face << std::endl;
1220 while ( i != start );
1233 <<
"when turning around vertex " << v <<
", some opposite half-edge "
1234 << he.
opposite <<
" points to " << w << std::endl;
1248 <<
"boundary vertex " << i <<
" is associated to the half-edge " << j
1249 <<
" that does not lie on the boundary but on face " <<
halfEdge( j ).
face
1264 <<
"arc (" << v1 <<
"," << v2 <<
") was found to be half-edge " << j
1265 <<
" but it should be half-edge " << i << std::endl;
1276 if ( hei.
edge != ei ) {
1278 <<
"edge " << ei <<
" is associated to half-edge " << i
1279 <<
" but its edge is " << hei.
edge << std::endl;
1282 if ( hej.
edge != ei ) {
1284 <<
"edge " << ei <<
" is associated to half-edge " << i
1285 <<
" of opposite half-edge " << j
1286 <<
" but its edge is " << hej.
edge << std::endl;
1292 if ( check_arc2index )
1298 const Index i = arc2idx.second;
1301 <<
"arc (" << v1 <<
"," << v2 <<
") is associated to half-edge " << i
1302 <<
" but it points to vertex " <<
myHalfEdges[ i ].toVertex << std::endl;
1308 <<
"arc (" << v1 <<
"," << v2 <<
") is associated to half-edge " << i
1309 <<
" but its opposite half-edge " << i2 <<
" points to vertex " <<
myHalfEdges[ i2 ].toVertex
1330 const Index start = i;
1332 std::set<VertexIndex> V;
1333 std::set<EdgeIndex> E;
1336 if ( he.
face != f ) {
1337 trace.
warning() <<
"[HalfEdgeDataStructure::isValidTriangulation] "
1338 <<
"when turning around face " << f
1339 <<
", half-edge " << i
1340 <<
" is associated to face " << he.
face
1345 E.insert( he.
edge );
1349 while ( i != start );
1351 trace.
warning() <<
"[HalfEdgeDataStructure::isValidTriangulation] "
1352 <<
"when turning around face " << f
1353 <<
", we had to visit " << nbv
1354 <<
" half-edges to loop (instead of 3)" << std::endl;
1357 if ( V.size() != 3 ) {
1358 trace.
warning() <<
"[HalfEdgeDataStructure::isValidTriangulation] "
1359 <<
"when turning around face " << f
1360 <<
", the set of vertices has not a size 3:";
1365 if ( E.size() != 3 ) {
1366 trace.
warning() <<
"[HalfEdgeDataStructure::isValidTriangulation] "
1367 <<
"when turning around face " << f
1368 <<
", the set of edges has not a size 3:";
1416 ASSERT( !de2fi.empty() );
1418 Arc2FaceIndex::const_iterator it = de2fi.find(
Arc( vi, vj ) );
1422 if( it == de2fi.end() )
1424 ASSERT( de2fi.find(
Arc( vj, vi ) ) != de2fi.end() );
1440 operator<< ( std::ostream & out,
const HalfEdgeDataStructure &
object );
1447 #include "DGtal/topology/HalfEdgeDataStructure.ih"
1452 #endif // !defined HalfEdgeDataStructure_h
1454 #undef HalfEdgeDataStructure_RECURSES
1455 #endif // else defined(HalfEdgeDataStructure_RECURSES)