DGtal  1.3.beta
testHalfEdgeDataStructure.cpp
Go to the documentation of this file.
1 
30 #include <iostream>
32 #include <algorithm>
33 #include "DGtal/base/Common.h"
34 #include "ConfigTest.h"
35 #include "DGtalCatch.h"
36 #include "DGtal/helpers/StdDefs.h"
37 #include "DGtal/topology/HalfEdgeDataStructure.h"
39 
40 using namespace DGtal;
41 
43 // Functions for testing class HalfEdgeDataStructure.
48 typedef HalfEdgeDataStructure::Arc ArcT; //Arc already defined in wingdi.h
51 
52 
53 
55 {
56  std::vector< Triangle > triangles( 2 );
57  triangles[0].v = { 0, 1, 2 };
58  triangles[1].v = { 2, 1, 3 };
59 
61  mesh.build( triangles );
62  return mesh;
63 }
64 
66 {
67  std::vector< Triangle > triangles( 3 );
68  triangles[0].v = { 0, 1, 2 };
69  triangles[1].v = { 2, 1, 3 };
70  triangles[2].v = { 2, 3, 0 };
71 
73  mesh.build( triangles );
74  return mesh;
75 }
76 
78 {
79  std::vector< Triangle > triangles( 4 );
80  triangles[0].v = { 0, 1, 2 };
81  triangles[1].v = { 2, 1, 3 };
82  triangles[2].v = { 2, 3, 0 };
83  triangles[3].v = { 0, 3, 1 };
84 
86  mesh.build( triangles );
87  return mesh;
88 }
89 
91 {
92  std::vector< Triangle > triangles( 8 );
93  triangles[0].v = { 0, 1, 2 };
94  triangles[1].v = { 0, 2, 3 };
95  triangles[2].v = { 0, 3, 4 };
96  triangles[3].v = { 0, 4, 1 };
97  triangles[4].v = { 5, 2, 1 };
98  triangles[5].v = { 5, 3, 2 };
99  triangles[6].v = { 5, 4, 3 };
100  triangles[7].v = { 5, 1, 4 };
102  mesh.build( triangles );
103  return mesh;
104 }
105 
107 {
108  std::vector< Triangle > triangles( 6 );
109  triangles[0].v = { 0, 1, 2 };
110  triangles[1].v = { 2, 1, 3 };
111  triangles[2].v = { 2, 3, 4 };
112  triangles[3].v = { 4, 3, 5 };
113  triangles[4].v = { 4, 5, 0 };
114  triangles[5].v = { 0, 5, 1 };
115  std::vector< Edge > edges;
116  const auto kNumVertices
119  mesh.build( kNumVertices, triangles, edges );
120  return mesh;
121 }
122 
124 {
125  std::vector< Triangle > triangles( 7 );
126  triangles[0].v = { 0, 1, 2 };
127  triangles[1].v = { 2, 1, 3 };
128  triangles[2].v = { 2, 3, 4 };
129  triangles[3].v = { 4, 3, 5 };
130  triangles[4].v = { 4, 5, 0 };
131  triangles[5].v = { 0, 5, 1 };
132  triangles[6].v = { 4, 0, 2 };
133  std::vector< Edge > edges;
134  const auto kNumVertices
137  mesh.build( kNumVertices, triangles, edges );
138  return mesh;
139 }
140 
142 {
143  std::vector< PolygonalFace > faces( 5 );
144  faces[ 0 ] = PolygonalFace( { 0, 3, 2, 1 } );
145  faces[ 1 ] = PolygonalFace( { 0, 1, 4 } );
146  faces[ 2 ] = PolygonalFace( { 1, 2, 4 } );
147  faces[ 3 ] = PolygonalFace( { 2, 3, 4 } );
148  faces[ 4 ] = PolygonalFace( { 3, 0, 4 } );
150  mesh.build( faces );
151  return mesh;
152 }
153 
155 {
156  std::vector< PolygonalFace > faces( 6 );
157  faces[ 0 ] = PolygonalFace( { 1, 0, 2, 3 } );
158  faces[ 1 ] = PolygonalFace( { 0, 1, 5, 4 } );
159  faces[ 2 ] = PolygonalFace( { 1, 3, 7, 5 } );
160  faces[ 3 ] = PolygonalFace( { 3, 2, 6, 7 } );
161  faces[ 4 ] = PolygonalFace( { 2, 0, 4, 6 } );
162  faces[ 5 ] = PolygonalFace( { 4, 5, 7, 6 } );
164  mesh.build( faces );
165  return mesh;
166 }
167 
169 {
170  std::vector< PolygonalFace > faces( 6 );
171  faces[ 0 ] = PolygonalFace( { 1, 0, 2, 3 } );
172  faces[ 1 ] = PolygonalFace( { 0, 1, 5, 4 } );
173  faces[ 2 ] = PolygonalFace( { 1, 3, 7, 5 } );
174  faces[ 3 ] = PolygonalFace( { 3, 2, 6, 7 } );
175  faces[ 4 ] = PolygonalFace( { 2, 0, 4, 6 } );
176  faces[ 5 ] = PolygonalFace( { 4, 5, 8, 9 } );
178  mesh.build( faces );
179  return mesh;
180 }
181 
182 
183 SCENARIO( "HalfEdgeDataStructure build", "[halfedge][build]" )
184 {
185  GIVEN( "Two triangles incident by an edge" ) {
187  THEN( "The mesh is valid" ) {
188  REQUIRE( mesh.isValid() );
189  }
190  THEN( "The mesh is a valid triangulation" ) {
191  REQUIRE( mesh.isValidTriangulation() );
192  }
193  THEN( "The mesh has 4 vertices, 5 edges, 2 faces, 10 half-edges" ) {
194  REQUIRE( mesh.nbVertices() == 4 );
195  REQUIRE( mesh.nbEdges() == 5 );
196  REQUIRE( mesh.nbFaces() == 2 );
197  REQUIRE( mesh.nbHalfEdges() == 10 );
198  }
199  THEN( "The mesh has 4 boundary vertices" ) {
200  VertexIndexRange bdry = mesh.boundaryVertices();
201  std::sort( bdry.begin(), bdry.end() );
202  REQUIRE( bdry.size() == 4 );
203  REQUIRE( bdry[ 0 ] == 0 );
204  REQUIRE( bdry[ 1 ] == 1 );
205  REQUIRE( bdry[ 2 ] == 2 );
206  REQUIRE( bdry[ 3 ] == 3 );
207  }
208  THEN( "The mesh has 4 boundary arcs" ) {
209  std::vector<ArcT> bdry = mesh.boundaryArcs();
210  std::sort( bdry.begin(), bdry.end() );
211  REQUIRE( bdry.size() == 4 );
212  // std::cout << " arc=(" << bdry[ 0 ].first << "," << bdry[ 0 ].second << ")" << std::endl;
213  REQUIRE( bdry[ 0 ] == ArcT( 0, 2 ) );
214  REQUIRE( bdry[ 1 ] == ArcT( 1, 0 ) );
215  REQUIRE( bdry[ 2 ] == ArcT( 2, 3 ) );
216  REQUIRE( bdry[ 3 ] == ArcT( 3, 1 ) );
217  }
218  }
219  GIVEN( "Three triangles forming a fan around a vertex" ) {
221  THEN( "The mesh is valid" ) {
222  REQUIRE( mesh.isValid() );
223  }
224  THEN( "The mesh is a valid triangulation" ) {
225  REQUIRE( mesh.isValidTriangulation() );
226  }
227  THEN( "The mesh has 4 vertices, 6 edges, 3 faces, 12 half-edges" ) {
228  REQUIRE( mesh.nbVertices() == 4 );
229  REQUIRE( mesh.nbEdges() == 6 );
230  REQUIRE( mesh.nbFaces() == 3 );
231  REQUIRE( mesh.nbHalfEdges() == 12 );
232  }
233  THEN( "The mesh has 3 boundary vertices" ) {
234  VertexIndexRange bdry = mesh.boundaryVertices();
235  std::sort( bdry.begin(), bdry.end() );
236  REQUIRE( bdry.size() == 3 );
237  REQUIRE( bdry[ 0 ] == 0 );
238  REQUIRE( bdry[ 1 ] == 1 );
239  REQUIRE( bdry[ 2 ] == 3 );
240  }
241  THEN( "The mesh has 3 boundary arcs" ) {
242  std::vector<ArcT> bdry = mesh.boundaryArcs();
243  std::sort( bdry.begin(), bdry.end() );
244  REQUIRE( bdry.size() == 3 );
245  // std::cout << " arc=(" << bdry[ 0 ].first << "," << bdry[ 0 ].second << ")" << std::endl;
246  REQUIRE( bdry[ 0 ] == ArcT( 0, 3 ) );
247  REQUIRE( bdry[ 1 ] == ArcT( 1, 0 ) );
248  REQUIRE( bdry[ 2 ] == ArcT( 3, 1 ) );
249  }
250  }
251  GIVEN( "Four triangles forming a tetrahedron" ) {
253  THEN( "The mesh is valid" ) {
254  REQUIRE( mesh.isValid() );
255  }
256  THEN( "The mesh is a valid triangulation" ) {
257  REQUIRE( mesh.isValidTriangulation() );
258  }
259  THEN( "The mesh has 4 vertices, 6 edges, 4 faces, 12 half-edges" ) {
260  REQUIRE( mesh.nbVertices() == 4 );
261  REQUIRE( mesh.nbEdges() == 6 );
262  REQUIRE( mesh.nbFaces() == 4 );
263  REQUIRE( mesh.nbHalfEdges() == 12 );
264  }
265  THEN( "The mesh has no boundary vertices" ) {
266  VertexIndexRange bdry = mesh.boundaryVertices();
267  REQUIRE( bdry.size() == 0 );
268  }
269  THEN( "The mesh has no boundary arcs" ) {
270  std::vector<ArcT> bdry = mesh.boundaryArcs();
271  REQUIRE( bdry.size() == 0 );
272  }
273  }
274  GIVEN( "A ribbon with a hole" ) {
276  THEN( "The mesh is valid" ) {
277  REQUIRE( mesh.isValid() );
278  }
279  THEN( "The mesh has 6 vertices, 12 edges, 6 faces, 24 half-edges" ) {
280  REQUIRE( mesh.nbVertices() == 6 );
281  REQUIRE( mesh.nbEdges() == 12 );
282  REQUIRE( mesh.nbFaces() == 6 );
283  REQUIRE( mesh.nbHalfEdges() == 24 );
284  }
285  THEN( "The mesh has 6 boundary vertices" ) {
286  VertexIndexRange bdry = mesh.boundaryVertices();
287  REQUIRE( bdry.size() == 6 );
288  }
289  THEN( "The mesh has 6 boundary arcs" ) {
290  std::vector<ArcT> bdry = mesh.boundaryArcs();
291  std::sort( bdry.begin(), bdry.end() );
292  REQUIRE( bdry.size() == 6 );
293  REQUIRE( bdry[ 0 ] == ArcT( 0, 2 ) );
294  REQUIRE( bdry[ 1 ] == ArcT( 1, 5 ) );
295  REQUIRE( bdry[ 2 ] == ArcT( 2, 4 ) );
296  REQUIRE( bdry[ 3 ] == ArcT( 3, 1 ) );
297  REQUIRE( bdry[ 4 ] == ArcT( 4, 0 ) );
298  REQUIRE( bdry[ 5 ] == ArcT( 5, 3 ) );
299  }
300  }
301  GIVEN( "The same ribbon with his hole closed" ) {
303  THEN( "The mesh is valid" ) {
304  REQUIRE( mesh.isValid() );
305  }
306  THEN( "The mesh is a valid triangulation" ) {
307  REQUIRE( mesh.isValidTriangulation() );
308  }
309  THEN( "The mesh has 6 vertices, 12 edges, 7 faces, 24 half-edges" ) {
310  REQUIRE( mesh.nbVertices() == 6 );
311  REQUIRE( mesh.nbEdges() == 12 );
312  REQUIRE( mesh.nbFaces() == 7 );
313  REQUIRE( mesh.nbHalfEdges() == 24 );
314  }
315  THEN( "The mesh has 3 boundary vertices" ) {
316  VertexIndexRange bdry = mesh.boundaryVertices();
317  std::sort( bdry.begin(), bdry.end() );
318  REQUIRE( bdry.size() == 3 );
319  REQUIRE( bdry[ 0 ] == 1 );
320  REQUIRE( bdry[ 1 ] == 3 );
321  REQUIRE( bdry[ 2 ] == 5 );
322  }
323  THEN( "The mesh has 3 boundary arcs" ) {
324  std::vector<ArcT> bdry = mesh.boundaryArcs();
325  std::sort( bdry.begin(), bdry.end() );
326  REQUIRE( bdry.size() == 3 );
327  REQUIRE( bdry[ 0 ] == ArcT( 1, 5 ) );
328  REQUIRE( bdry[ 1 ] == ArcT( 3, 1 ) );
329  REQUIRE( bdry[ 2 ] == ArcT( 5, 3 ) );
330  }
331  }
332  GIVEN( "A pyramid with a square base" ) {
334  THEN( "The mesh is valid" ) {
335  REQUIRE( mesh.isValid() );
336  }
337  THEN( "The mesh has 5 vertices, 8 edges, 5 faces, 16 half-edges" ) {
338  REQUIRE( mesh.nbVertices() == 5 );
339  REQUIRE( mesh.nbEdges() == 8 );
340  REQUIRE( mesh.nbFaces() == 5 );
341  REQUIRE( mesh.nbHalfEdges() == 16 );
342  }
343  THEN( "The mesh has 0 boundary vertices" ) {
344  VertexIndexRange bdry = mesh.boundaryVertices();
345  REQUIRE( bdry.size() == 0 );
346  }
347  THEN( "The mesh has 0 boundary arcs" ) {
348  std::vector<ArcT> bdry = mesh.boundaryArcs();
349  REQUIRE( bdry.size() == 0 );
350  }
351  }
352  GIVEN( "A cube" ) {
354  THEN( "The mesh is valid" ) {
355  REQUIRE( mesh.isValid() );
356  }
357  THEN( "The mesh has 8 vertices, 12 edges, 6 faces, 24 half-edges" ) {
358  REQUIRE( mesh.nbVertices() == 8 );
359  REQUIRE( mesh.nbEdges() == 12 );
360  REQUIRE( mesh.nbFaces() == 6 );
361  REQUIRE( mesh.nbHalfEdges() == 24 );
362  }
363  THEN( "The mesh has 0 boundary vertices" ) {
364  VertexIndexRange bdry = mesh.boundaryVertices();
365  REQUIRE( bdry.size() == 0 );
366  }
367  THEN( "The mesh has 0 boundary arcs" ) {
368  std::vector<ArcT> bdry = mesh.boundaryArcs();
369  REQUIRE( bdry.size() == 0 );
370  }
371  }
372  GIVEN( "A box with an open side" ) {
374  THEN( "The mesh is valid" ) {
375  REQUIRE( mesh.isValid() );
376  }
377  THEN( "The mesh has 10 vertices, 15 edges, 6 faces, 30 half-edges" ) {
378  REQUIRE( mesh.nbVertices() == 10 );
379  REQUIRE( mesh.nbEdges() == 15 );
380  REQUIRE( mesh.nbFaces() == 6 );
381  REQUIRE( mesh.nbHalfEdges() == 30 );
382  }
383  THEN( "The mesh has 6 boundary vertices" ) {
384  VertexIndexRange bdry = mesh.boundaryVertices();
385  REQUIRE( bdry.size() == 6 );
386  }
387  THEN( "The mesh has 6 boundary arcs" ) {
388  std::vector<ArcT> bdry = mesh.boundaryArcs();
389  REQUIRE( bdry.size() == 6 );
390  }
391  }
392 
393 }
394 
395 SCENARIO( "HalfEdgeDataStructure neighboring relations", "[halfedge][neighbors]" ){
396  GIVEN( "Two triangles incident by an edge" ) {
398  VertexIndexRange nv;
399  THEN( "Vertex 0 has 2 neighboring vertices" ) {
400  mesh.getNeighboringVertices( 0, nv );
401  VertexIndexRange expected = { 1, 2 };
402  REQUIRE( nv.size() == 2 );
403  REQUIRE( std::is_permutation( nv.begin(), nv.end(), expected.begin() ) );
404  }
405  THEN( "Vertex 1 has 3 neighboring vertices" ) {
406  mesh.getNeighboringVertices( 1, nv );
407  VertexIndexRange expected = { 3, 2, 0 };
408  REQUIRE( nv.size() == 3 );
409  REQUIRE( std::is_permutation( nv.begin(), nv.end(), expected.begin() ) );
410  }
411  THEN( "Vertex 2 has 3 neighboring vertices" ) {
412  mesh.getNeighboringVertices( 2, nv );
413  VertexIndexRange expected = { 0, 1, 3 };
414  REQUIRE( nv.size() == 3 );
415  REQUIRE( std::is_permutation( nv.begin(), nv.end(), expected.begin() ) );
416  }
417  THEN( "Vertex 3 has 2 neighboring vertices" ) {
418  mesh.getNeighboringVertices( 3, nv );
419  VertexIndexRange expected = { 2, 1 };
420  REQUIRE( nv.size() == 2 );
421  REQUIRE( std::is_permutation( nv.begin(), nv.end(), expected.begin() ) );
422  }
423  }
424  GIVEN( "A ribbon with a hole" ) {
426  VertexIndexRange nv;
427  THEN( "Vertex 0 has 4 neighboring vertices" ) {
428  mesh.getNeighboringVertices( 0, nv );
429  VertexIndexRange expected = { 4, 5, 1, 2 };
430  REQUIRE( nv.size() == 4 );
431  REQUIRE( std::is_permutation( nv.begin(), nv.end(), expected.begin() ) );
432  }
433  THEN( "Vertex 1 has 4 neighboring vertices" ) {
434  mesh.getNeighboringVertices( 1, nv );
435  VertexIndexRange expected = { 3, 2, 0, 5 };
436  REQUIRE( nv.size() == 4 );
437  REQUIRE( std::is_permutation( nv.begin(), nv.end(), expected.begin() ) );
438  }
439  THEN( "Vertex 2 has 4 neighboring vertices" ) {
440  mesh.getNeighboringVertices( 2, nv );
441  VertexIndexRange expected = { 0, 1, 3, 4 };
442  REQUIRE( nv.size() == 4 );
443  REQUIRE( std::is_permutation( nv.begin(), nv.end(), expected.begin() ) );
444  }
445  }
446 
447  GIVEN( "A box with an open side" ) {
449  VertexIndexRange nv;
450  THEN( "Vertex 0 has 3 neighboring vertices" ) {
451  mesh.getNeighboringVertices( 0, nv );
452  VertexIndexRange expected = { 1, 4, 2 };
453  REQUIRE( nv.size() == 3 );
454  REQUIRE( std::is_permutation( nv.begin(), nv.end(), expected.begin() ) );
455  }
456  THEN( "Vertex 5 has 4 neighboring vertices" ) {
457  mesh.getNeighboringVertices( 5, nv );
458  VertexIndexRange expected = { 8, 4, 1, 7 };
459  REQUIRE( nv.size() == 4 );
460  REQUIRE( std::is_permutation( nv.begin(), nv.end(), expected.begin() ) );
461  }
462  THEN( "Vertex 7 has 3 neighboring vertices" ) {
463  mesh.getNeighboringVertices( 7, nv );
464  VertexIndexRange expected = { 5, 3, 6 };
465  REQUIRE( nv.size() == 3 );
466  REQUIRE( std::is_permutation( nv.begin(), nv.end(), expected.begin() ) );
467  }
468  }
469 }
470 
471 SCENARIO( "HalfEdgeDataStructure flips", "[halfedge][flips]" ){
472  GIVEN( "Two triangles incident by an edge" ) {
474  THEN( "Only one edge is flippable" ) {
475  int nbflippable = 0;
476  for ( Size e = 0; e < mesh.nbEdges(); e++ )
477  {
478  if ( mesh.isFlippable( mesh.halfEdgeIndexFromEdgeIndex( e ) ) )
479  nbflippable++;
480  }
481  REQUIRE( nbflippable == 1 );
482  }
483  }
484  GIVEN( "A pyramid" ) {
486  THEN( "Only four edges are flippable" ) {
487  int nbflippable = 0;
488  for ( Size e = 0; e < mesh.nbEdges(); e++ )
489  {
490  if ( mesh.isFlippable( mesh.halfEdgeIndexFromEdgeIndex( e ) ) )
491  nbflippable++;
492  }
493  REQUIRE( nbflippable == 4 );
494  }
495  }
496  GIVEN( "A tetrahedron" ) {
498  THEN( "No edges are flippable" ) {
499  int nbflippable = 0;
500  for ( Size e = 0; e < mesh.nbEdges(); e++ )
501  {
502  if ( mesh.isFlippable( mesh.halfEdgeIndexFromEdgeIndex( e ) ) )
503  nbflippable++;
504  }
505  REQUIRE( nbflippable == 0 );
506  }
507  }
508  GIVEN( "Two triangles incident by an edge" ) {
510  auto he = mesh.halfEdgeIndexFromArc( {1,2} );
511  REQUIRE( mesh.isFlippable( he ) );
512  mesh.flip( he );
513  THEN( "The mesh is valid after flip" ) {
514  REQUIRE( mesh.isValid() );
515  }
516  THEN( "The mesh is a valid triangulation after flip" ) {
517  REQUIRE( mesh.isValidTriangulation() );
518  }
519  THEN( "Vertex 0 has 2,3,1 as neighbors after flip" ) {
520  VertexIndexRange nv = mesh.neighboringVertices( 0 );
521  VertexIndexRange expected = { 2, 3, 1 };
522  REQUIRE( nv.size() == 3 );
523  REQUIRE( std::equal( nv.begin(), nv.end(), expected.begin() ) );
524  }
525  THEN( "Vertex 1 has 0,3 as neighbors after flip" ) {
526  VertexIndexRange nv = mesh.neighboringVertices( 1 );
527  VertexIndexRange expected = { 0, 3 };
528  REQUIRE( nv.size() == 2 );
529  REQUIRE( std::equal( nv.begin(), nv.end(), expected.begin() ) );
530  }
531  THEN( "Vertex 2 has 3,0 as neighbors after flip" ) {
532  VertexIndexRange nv = mesh.neighboringVertices( 2 );
533  VertexIndexRange expected = { 3, 0 };
534  REQUIRE( nv.size() == 2 );
535  REQUIRE( std::equal( nv.begin(), nv.end(), expected.begin() ) );
536  }
537  THEN( "Vertex 3 has 2,0,1 as neighbors after flip" ) {
538  VertexIndexRange nv = mesh.neighboringVertices( 3 );
539  VertexIndexRange expected = { 1, 0, 2 };
540  REQUIRE( nv.size() == 3 );
541  REQUIRE( std::equal( nv.begin(), nv.end(), expected.begin() ) );
542  }
543  }
544  GIVEN( "Two triangles incident by an edge" ) {
546  auto he = mesh.findHalfEdgeIndexFromArc( {1,2} );
547  REQUIRE( mesh.isFlippable( he ) );
548  mesh.flip( he );
549  auto he2 = mesh.findHalfEdgeIndexFromArc( {0,3} );
550  REQUIRE( mesh.isFlippable( he2 ) );
551  mesh.flip( he2 );
552  THEN( "The mesh is valid after two flips" ) {
553  REQUIRE( mesh.isValid() );
554  }
555  THEN( "The mesh is a valid triangulation after two flips" ) {
556  REQUIRE( mesh.isValidTriangulation() );
557  }
558  THEN( "Vertex 0 has 2,1 as neighbors after flip" ) {
559  VertexIndexRange nv = mesh.neighboringVertices( 0 );
560  VertexIndexRange expected = { 2, 1 };
561  REQUIRE( nv.size() == 2 );
562  REQUIRE( std::equal( nv.begin(), nv.end(), expected.begin() ) );
563  }
564  THEN( "Vertex 1 has 0,2,3 as neighbors after flip" ) {
565  VertexIndexRange nv = mesh.neighboringVertices( 1 );
566  VertexIndexRange expected = { 0,2,3 };
567  REQUIRE( nv.size() == 3 );
568  REQUIRE( std::equal( nv.begin(), nv.end(), expected.begin() ) );
569  }
570  THEN( "Vertex 2 has 3,1,0 as neighbors after flip" ) {
571  VertexIndexRange nv = mesh.neighboringVertices( 2 );
572  VertexIndexRange expected = { 3, 1, 0 };
573  REQUIRE( nv.size() == 3 );
574  REQUIRE( std::equal( nv.begin(), nv.end(), expected.begin() ) );
575  }
576  THEN( "Vertex 3 has 1,2 as neighbors after flip" ) {
577  VertexIndexRange nv = mesh.neighboringVertices( 3 );
578  VertexIndexRange expected = { 1, 2 };
579  REQUIRE( nv.size() == 2 );
580  REQUIRE( std::equal( nv.begin(), nv.end(), expected.begin() ) );
581  }
582  }
583 }
584 
585 SCENARIO( "HalfEdgeDataStructure splits", "[halfedge][splits]" ){
586  GIVEN( "Two triangles incident by an edge" ) {
588  auto he = mesh.findHalfEdgeIndexFromArc( {1,2} );
589  REQUIRE( mesh.isFlippable( he ) );
590  //auto vtx =
591  mesh.split( he );
592  THEN( "After split, mesh is valid" ) {
593  REQUIRE( mesh.isValid() );
594  }
595  THEN( "The mesh is a valid triangulation after split" ) {
596  REQUIRE( mesh.isValidTriangulation() );
597  }
598  THEN( "After split, mesh has 5 vertices, 8 edges, 4 faces" ) {
599  REQUIRE( mesh.nbVertices() == 5 );
600  REQUIRE( mesh.nbEdges() == 8 );
601  REQUIRE( mesh.nbFaces() == 4 );
602  }
603  THEN( "After split, vertex 4 has 4 neighbors { 0,1,2,3 }" ) {
604  VertexIndexRange nv = mesh.neighboringVertices( 4 );
605  VertexIndexRange expected = { 0, 1, 2, 3 };
606  REQUIRE( nv.size() == 4 );
607  REQUIRE( std::is_permutation( nv.begin(), nv.end(), expected.begin() ) );
608  }
609  }
610 }
611 
612 SCENARIO( "HalfEdgeDataStructure merges", "[halfedge][merges]" ){
613  GIVEN( "An octahedron" ) {
615  auto he = mesh.findHalfEdgeIndexFromArc( {1,2} );
616  REQUIRE( mesh.isMergeable( he ) );
617  auto vtx = mesh.merge( he );
618  THEN( "After merge, mesh is valid" ) {
619  REQUIRE( mesh.isValid() );
620  }
621  THEN( "The mesh is a valid triangulation after merge" ) {
622  REQUIRE( mesh.isValidTriangulation() );
623  }
624  THEN( "After merge, merged vertex is 1" ) {
625  REQUIRE( vtx == 1 );
626  }
627  THEN( "After merge, mesh has 5 vertices, 9 edges, 6 faces" ) {
628  REQUIRE( mesh.nbVertices() == 5 );
629  REQUIRE( mesh.nbEdges() == 9 );
630  REQUIRE( mesh.nbFaces() == 6 );
631  }
632  THEN( "After merge, vertex 0 has 3 neighbors { 1,3,4 }" ) {
633  VertexIndexRange nv = mesh.neighboringVertices( 0 );
634  VertexIndexRange expected = { 1, 3, 4 };
635  REQUIRE( nv.size() == 3 );
636  REQUIRE( std::is_permutation( nv.begin(), nv.end(), expected.begin() ) );
637  }
638  }
639 }
640 
DGtal::HalfEdgeDataStructure::nbEdges
Size nbEdges() const
Definition: HalfEdgeDataStructure.h:373
VertexIndexRange
HalfEdgeDataStructure::VertexIndexRange VertexIndexRange
Definition: testHalfEdgeDataStructure.cpp:49
DGtal::HalfEdgeDataStructure::build
bool build(const Size num_vertices, const std::vector< Triangle > &triangles, const std::vector< Edge > &edges)
DGtal::HalfEdgeDataStructure::halfEdgeIndexFromArc
Index halfEdgeIndexFromArc(const VertexIndex i, const VertexIndex j) const
Definition: HalfEdgeDataStructure.h:397
DGtal::HalfEdgeDataStructure::boundaryArcs
std::vector< Arc > boundaryArcs() const
Definition: HalfEdgeDataStructure.h:566
makeTwoTriangles
HalfEdgeDataStructure makeTwoTriangles()
Definition: testHalfEdgeDataStructure.cpp:54
DGtal::HalfEdgeDataStructure::VertexIndexRange
std::vector< VertexIndex > VertexIndexRange
Definition: HalfEdgeDataStructure.h:111
DGtal::HalfEdgeDataStructure::nbHalfEdges
Size nbHalfEdges() const
Definition: HalfEdgeDataStructure.h:367
DGtal::HalfEdgeDataStructure::isValid
bool isValid(bool check_arc2index=true) const
Definition: HalfEdgeDataStructure.h:1109
DGtal::HalfEdgeDataStructure::isFlippable
bool isFlippable(const Index hei) const
Definition: HalfEdgeDataStructure.h:628
makeThreeTriangles
HalfEdgeDataStructure makeThreeTriangles()
Definition: testHalfEdgeDataStructure.cpp:65
DGtal::HalfEdgeDataStructure::nbVertices
Size nbVertices() const
Definition: HalfEdgeDataStructure.h:370
REQUIRE
REQUIRE(domain.isInside(aPoint))
DGtal::HalfEdgeDataStructure::findHalfEdgeIndexFromArc
Index findHalfEdgeIndexFromArc(const VertexIndex i, const VertexIndex j) const
Definition: HalfEdgeDataStructure.h:418
DGtal::HalfEdgeDataStructure::merge
VertexIndex merge(const Index hei, bool update_arc2index=true)
Definition: HalfEdgeDataStructure.h:865
DGtal::HalfEdgeDataStructure::isValidTriangulation
bool isValidTriangulation() const
Definition: HalfEdgeDataStructure.h:1322
PolygonalFace
HalfEdgeDataStructure::PolygonalFace PolygonalFace
Definition: testHalfEdgeDataStructure.cpp:46
Size
HalfEdgeDataStructure::Size Size
Definition: testHalfEdgeDataStructure.cpp:50
DGtal::HalfEdgeDataStructure::Triangle
Represents an unoriented triangle as three vertices.
Definition: HalfEdgeDataStructure.h:154
DGtal::HalfEdgeDataStructure::Edge
Definition: HalfEdgeDataStructure.h:126
DGtal::HalfEdgeDataStructure::Size
std::size_t Size
The type for counting elements.
Definition: HalfEdgeDataStructure.h:87
makeOctahedron
HalfEdgeDataStructure makeOctahedron()
Definition: testHalfEdgeDataStructure.cpp:90
makeTetrahedron
HalfEdgeDataStructure makeTetrahedron()
Definition: testHalfEdgeDataStructure.cpp:77
DGtal::HalfEdgeDataStructure::flip
void flip(const Index hei, bool update_arc2index=true)
Definition: HalfEdgeDataStructure.h:664
DGtal
DGtal is the top-level namespace which contains all DGtal functions and types.
DGtal::HalfEdgeDataStructure::halfEdgeIndexFromEdgeIndex
Index halfEdgeIndexFromEdgeIndex(const EdgeIndex ei) const
Definition: HalfEdgeDataStructure.h:454
makePyramid
HalfEdgeDataStructure makePyramid()
Definition: testHalfEdgeDataStructure.cpp:141
DGtal::HalfEdgeDataStructure
Aim: This class represents an half-edge data structure, which is a structure for representing the top...
Definition: HalfEdgeDataStructure.h:82
DGtal::HalfEdgeDataStructure::neighboringVertices
VertexIndexRange neighboringVertices(const VertexIndex vi) const
Definition: HalfEdgeDataStructure.h:475
DGtal::HalfEdgeDataStructure::getNeighboringVertices
void getNeighboringVertices(const VertexIndex vi, VertexIndexRange &result) const
Definition: HalfEdgeDataStructure.h:459
makeCube
HalfEdgeDataStructure makeCube()
Definition: testHalfEdgeDataStructure.cpp:154
DGtal::HalfEdgeDataStructure::getUnorderedEdgesFromTriangles
static Size getUnorderedEdgesFromTriangles(const std::vector< Triangle > &triangles, std::vector< Edge > &edges_out)
Definition: HalfEdgeDataStructure.h:231
DGtal::HalfEdgeDataStructure::Arc
std::pair< VertexIndex, VertexIndex > Arc
An arc is a directed edge from a first vertex to a second vertex.
Definition: HalfEdgeDataStructure.h:116
Triangle
HalfEdgeDataStructure::Triangle Triangle
Definition: testHalfEdgeDataStructure.cpp:45
makeBox
HalfEdgeDataStructure makeBox()
Definition: testHalfEdgeDataStructure.cpp:168
makeRibbonWithHole
HalfEdgeDataStructure makeRibbonWithHole()
Definition: testHalfEdgeDataStructure.cpp:106
Edge
HalfEdgeDataStructure::Edge Edge
Definition: testHalfEdgeDataStructure.cpp:47
ArcT
HalfEdgeDataStructure::Arc ArcT
Definition: testHalfEdgeDataStructure.cpp:48
DGtal::HalfEdgeDataStructure::isMergeable
bool isMergeable(const Index hei) const
Definition: HalfEdgeDataStructure.h:827
SCENARIO
SCENARIO("HalfEdgeDataStructure build", "[halfedge][build]")
Definition: testHalfEdgeDataStructure.cpp:183
DGtal::HalfEdgeDataStructure::nbFaces
Size nbFaces() const
Definition: HalfEdgeDataStructure.h:376
makeTriangulatedDisk
HalfEdgeDataStructure makeTriangulatedDisk()
Definition: testHalfEdgeDataStructure.cpp:123
GIVEN
GIVEN("A cubical complex with random 3-cells")
Definition: testCubicalComplex.cpp:70
DGtal::HalfEdgeDataStructure::boundaryVertices
VertexIndexRange boundaryVertices() const
Definition: HalfEdgeDataStructure.h:536
DGtal::HalfEdgeDataStructure::split
VertexIndex split(const Index i, bool update_arc2index=true)
Definition: HalfEdgeDataStructure.h:727
DGtal::HalfEdgeDataStructure::PolygonalFace
std::vector< VertexIndex > PolygonalFace
Definition: HalfEdgeDataStructure.h:182