DGtal 1.4.0
Loading...
Searching...
No Matches
testHalfEdgeDataStructure.cpp
Go to the documentation of this file.
1
31#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
40using namespace DGtal;
41
43// Functions for testing class HalfEdgeDataStructure.
45typedef HalfEdgeDataStructure::Triangle Triangle;
46typedef HalfEdgeDataStructure::PolygonalFace PolygonalFace;
47typedef HalfEdgeDataStructure::Edge Edge;
48typedef HalfEdgeDataStructure::Arc ArcT; //Arc already defined in wingdi.h
49typedef HalfEdgeDataStructure::VertexIndexRange VertexIndexRange;
50typedef HalfEdgeDataStructure::Size Size;
51
52
53
54HalfEdgeDataStructure makeTwoTriangles()
55{
56 std::vector< Triangle > triangles( 2 );
57 triangles[0].v = { 0, 1, 2 };
58 triangles[1].v = { 2, 1, 3 };
59
60 HalfEdgeDataStructure mesh;
61 mesh.build( triangles );
62 return mesh;
63}
64
65HalfEdgeDataStructure makeThreeTriangles()
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
72 HalfEdgeDataStructure mesh;
73 mesh.build( triangles );
74 return mesh;
75}
76
77HalfEdgeDataStructure makeTetrahedron()
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
85 HalfEdgeDataStructure mesh;
86 mesh.build( triangles );
87 return mesh;
88}
89
90HalfEdgeDataStructure makeOctahedron()
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 };
101 HalfEdgeDataStructure mesh;
102 mesh.build( triangles );
103 return mesh;
104}
105
106HalfEdgeDataStructure makeRibbonWithHole()
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
117 = HalfEdgeDataStructure::getUnorderedEdgesFromTriangles( triangles, edges );
118 HalfEdgeDataStructure mesh;
119 mesh.build( kNumVertices, triangles, edges );
120 return mesh;
121}
122
123HalfEdgeDataStructure makeTriangulatedDisk()
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
135 = HalfEdgeDataStructure::getUnorderedEdgesFromTriangles( triangles, edges );
136 HalfEdgeDataStructure mesh;
137 mesh.build( kNumVertices, triangles, edges );
138 return mesh;
139}
140
141HalfEdgeDataStructure makePyramid()
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 } );
149 HalfEdgeDataStructure mesh;
150 mesh.build( faces );
151 return mesh;
152}
153
154HalfEdgeDataStructure makeCube()
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 } );
163 HalfEdgeDataStructure mesh;
164 mesh.build( faces );
165 return mesh;
166}
167
168HalfEdgeDataStructure makeBox()
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 } );
177 HalfEdgeDataStructure mesh;
178 mesh.build( faces );
179 return mesh;
180}
181
182
183SCENARIO( "HalfEdgeDataStructure build", "[halfedge][build]" )
184{
185 GIVEN( "Two triangles incident by an edge" ) {
186 HalfEdgeDataStructure mesh = makeTwoTriangles();
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" ) {
220 HalfEdgeDataStructure mesh = makeThreeTriangles();
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" ) {
252 HalfEdgeDataStructure mesh = makeTetrahedron();
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" ) {
275 HalfEdgeDataStructure mesh = makeRibbonWithHole();
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" ) {
302 HalfEdgeDataStructure mesh = makeTriangulatedDisk();
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" ) {
333 HalfEdgeDataStructure mesh = makePyramid();
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" ) {
353 HalfEdgeDataStructure mesh = makeCube();
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" ) {
373 HalfEdgeDataStructure mesh = makeBox();
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
395SCENARIO( "HalfEdgeDataStructure neighboring relations", "[halfedge][neighbors]" ){
396 GIVEN( "Two triangles incident by an edge" ) {
397 HalfEdgeDataStructure mesh = makeTwoTriangles();
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" ) {
425 HalfEdgeDataStructure mesh = makeRibbonWithHole();
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" ) {
448 HalfEdgeDataStructure mesh = makeBox();
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
471SCENARIO( "HalfEdgeDataStructure flips", "[halfedge][flips]" ){
472 GIVEN( "Two triangles incident by an edge" ) {
473 HalfEdgeDataStructure mesh = makeTwoTriangles();
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" ) {
485 HalfEdgeDataStructure mesh = makePyramid();
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" ) {
497 HalfEdgeDataStructure mesh = makeTetrahedron();
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" ) {
509 HalfEdgeDataStructure mesh = makeTwoTriangles();
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" ) {
545 HalfEdgeDataStructure mesh = makeTwoTriangles();
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
585SCENARIO( "HalfEdgeDataStructure splits", "[halfedge][splits]" ){
586 GIVEN( "Two triangles incident by an edge" ) {
587 HalfEdgeDataStructure mesh = makeTwoTriangles();
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
612SCENARIO( "HalfEdgeDataStructure merges", "[halfedge][merges]" ){
613 GIVEN( "An octahedron" ) {
614 HalfEdgeDataStructure mesh = makeOctahedron();
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
Aim: This class represents an half-edge data structure, which is a structure for representing the top...
Definition HalfEdgeDataStructure.h:83
DGtal::HalfEdgeDataStructure::VertexIndexRange
std::vector< VertexIndex > VertexIndexRange
Definition HalfEdgeDataStructure.h:111
DGtal::HalfEdgeDataStructure::halfEdgeIndexFromEdgeIndex
Index halfEdgeIndexFromEdgeIndex(const EdgeIndex ei) const
Definition HalfEdgeDataStructure.h:454
DGtal::HalfEdgeDataStructure::split
VertexIndex split(const Index i, bool update_arc2index=true)
Definition HalfEdgeDataStructure.h:727
DGtal::HalfEdgeDataStructure::findHalfEdgeIndexFromArc
Index findHalfEdgeIndexFromArc(const VertexIndex i, const VertexIndex j) const
Definition HalfEdgeDataStructure.h:418
DGtal::HalfEdgeDataStructure::PolygonalFace
std::vector< VertexIndex > PolygonalFace
Definition HalfEdgeDataStructure.h:182
DGtal::HalfEdgeDataStructure::isMergeable
bool isMergeable(const Index hei) const
Definition HalfEdgeDataStructure.h:827
DGtal::HalfEdgeDataStructure::getUnorderedEdgesFromTriangles
static Size getUnorderedEdgesFromTriangles(const std::vector< Triangle > &triangles, std::vector< Edge > &edges_out)
Definition HalfEdgeDataStructure.h:231
DGtal::HalfEdgeDataStructure::boundaryArcs
std::vector< Arc > boundaryArcs() const
Definition HalfEdgeDataStructure.h:566
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
DGtal::HalfEdgeDataStructure::neighboringVertices
VertexIndexRange neighboringVertices(const VertexIndex vi) const
Definition HalfEdgeDataStructure.h:475
DGtal::HalfEdgeDataStructure::Size
std::size_t Size
The type for counting elements.
Definition HalfEdgeDataStructure.h:87
DGtal::HalfEdgeDataStructure::boundaryVertices
VertexIndexRange boundaryVertices() const
Definition HalfEdgeDataStructure.h:536
DGtal::HalfEdgeDataStructure::flip
void flip(const Index hei, bool update_arc2index=true)
Definition HalfEdgeDataStructure.h:664
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
DGtal::HalfEdgeDataStructure::merge
VertexIndex merge(const Index hei, bool update_arc2index=true)
Definition HalfEdgeDataStructure.h:865
DGtal::HalfEdgeDataStructure::halfEdgeIndexFromArc
Index halfEdgeIndexFromArc(const VertexIndex i, const VertexIndex j) const
Definition HalfEdgeDataStructure.h:397
DGtal::HalfEdgeDataStructure::build
bool build(const Size num_vertices, const std::vector< Triangle > &triangles, const std::vector< Edge > &edges)
DGtal::HalfEdgeDataStructure::getNeighboringVertices
void getNeighboringVertices(const VertexIndex vi, VertexIndexRange &result) const
Definition HalfEdgeDataStructure.h:459
DGtal
DGtal is the top-level namespace which contains all DGtal functions and types.
Definition ClosedIntegerHalfPlane.h:49
DGtal::HalfEdgeDataStructure::Triangle
Represents an unoriented triangle as three vertices.
Definition HalfEdgeDataStructure.h:155
GIVEN
GIVEN("A cubical complex with random 3-cells")
Definition testCubicalComplex.cpp:70
VertexIndexRange
HalfEdgeDataStructure::VertexIndexRange VertexIndexRange
Definition testHalfEdgeDataStructure.cpp:49
Size
HalfEdgeDataStructure::Size Size
Definition testHalfEdgeDataStructure.cpp:50
makeRibbonWithHole
HalfEdgeDataStructure makeRibbonWithHole()
Definition testHalfEdgeDataStructure.cpp:106
makePyramid
HalfEdgeDataStructure makePyramid()
Definition testHalfEdgeDataStructure.cpp:141
makeThreeTriangles
HalfEdgeDataStructure makeThreeTriangles()
Definition testHalfEdgeDataStructure.cpp:65
makeTriangulatedDisk
HalfEdgeDataStructure makeTriangulatedDisk()
Definition testHalfEdgeDataStructure.cpp:123
Triangle
HalfEdgeDataStructure::Triangle Triangle
Definition testHalfEdgeDataStructure.cpp:45
ArcT
HalfEdgeDataStructure::Arc ArcT
Definition testHalfEdgeDataStructure.cpp:48
makeTwoTriangles
HalfEdgeDataStructure makeTwoTriangles()
Definition testHalfEdgeDataStructure.cpp:54
makeOctahedron
HalfEdgeDataStructure makeOctahedron()
Definition testHalfEdgeDataStructure.cpp:90
Edge
HalfEdgeDataStructure::Edge Edge
Definition testHalfEdgeDataStructure.cpp:47
makeTetrahedron
HalfEdgeDataStructure makeTetrahedron()
Definition testHalfEdgeDataStructure.cpp:77
makeBox
HalfEdgeDataStructure makeBox()
Definition testHalfEdgeDataStructure.cpp:168
PolygonalFace
HalfEdgeDataStructure::PolygonalFace PolygonalFace
Definition testHalfEdgeDataStructure.cpp:46
makeCube
HalfEdgeDataStructure makeCube()
Definition testHalfEdgeDataStructure.cpp:154
REQUIRE
REQUIRE(domain.isInside(aPoint))
SCENARIO
SCENARIO("UnorderedSetByBlock< PointVector< 2, int > unit tests with 32 bits blocks", "[unorderedsetbyblock][2d]")
Definition testUnorderedSetByBlock.cpp:58