DGtal  0.9.4.1
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.
50 
52 {
53  std::vector< Triangle > triangles( 2 );
54  triangles[0].v = { 0, 1, 2 };
55  triangles[1].v = { 2, 1, 3 };
56 
58  mesh.build( triangles );
59  return mesh;
60 }
61 
63 {
64  std::vector< Triangle > triangles( 3 );
65  triangles[0].v = { 0, 1, 2 };
66  triangles[1].v = { 2, 1, 3 };
67  triangles[2].v = { 2, 3, 0 };
68 
70  mesh.build( triangles );
71  return mesh;
72 }
73 
75 {
76  std::vector< Triangle > triangles( 4 );
77  triangles[0].v = { 0, 1, 2 };
78  triangles[1].v = { 2, 1, 3 };
79  triangles[2].v = { 2, 3, 0 };
80  triangles[3].v = { 0, 3, 1 };
81 
83  mesh.build( triangles );
84  return mesh;
85 }
86 
88 {
89  std::vector< Triangle > triangles( 6 );
90  triangles[0].v = { 0, 1, 2 };
91  triangles[1].v = { 2, 1, 3 };
92  triangles[2].v = { 2, 3, 4 };
93  triangles[3].v = { 4, 3, 5 };
94  triangles[4].v = { 4, 5, 0 };
95  triangles[5].v = { 0, 5, 1 };
96  std::vector< Edge > edges;
97  const int kNumVertices
100  mesh.build( kNumVertices, triangles, edges );
101  return mesh;
102 }
103 
105 {
106  std::vector< Triangle > triangles( 7 );
107  triangles[0].v = { 0, 1, 2 };
108  triangles[1].v = { 2, 1, 3 };
109  triangles[2].v = { 2, 3, 4 };
110  triangles[3].v = { 4, 3, 5 };
111  triangles[4].v = { 4, 5, 0 };
112  triangles[5].v = { 0, 5, 1 };
113  triangles[6].v = { 4, 0, 2 };
114  std::vector< Edge > edges;
115  const int kNumVertices
118  mesh.build( kNumVertices, triangles, edges );
119  return mesh;
120 }
121 
123 {
124  std::vector< PolygonalFace > faces( 5 );
125  faces[ 0 ] = PolygonalFace( { 0, 3, 2, 1 } );
126  faces[ 1 ] = PolygonalFace( { 0, 1, 4 } );
127  faces[ 2 ] = PolygonalFace( { 1, 2, 4 } );
128  faces[ 3 ] = PolygonalFace( { 2, 3, 4 } );
129  faces[ 4 ] = PolygonalFace( { 3, 0, 4 } );
131  mesh.build( faces );
132  return mesh;
133 }
134 
136 {
137  std::vector< PolygonalFace > faces( 6 );
138  faces[ 0 ] = PolygonalFace( { 1, 0, 2, 3 } );
139  faces[ 1 ] = PolygonalFace( { 0, 1, 5, 4 } );
140  faces[ 2 ] = PolygonalFace( { 1, 3, 7, 5 } );
141  faces[ 3 ] = PolygonalFace( { 3, 2, 6, 7 } );
142  faces[ 4 ] = PolygonalFace( { 2, 0, 4, 6 } );
143  faces[ 5 ] = PolygonalFace( { 4, 5, 7, 6 } );
145  mesh.build( faces );
146  return mesh;
147 }
148 
150 {
151  std::vector< PolygonalFace > faces( 6 );
152  faces[ 0 ] = PolygonalFace( { 1, 0, 2, 3 } );
153  faces[ 1 ] = PolygonalFace( { 0, 1, 5, 4 } );
154  faces[ 2 ] = PolygonalFace( { 1, 3, 7, 5 } );
155  faces[ 3 ] = PolygonalFace( { 3, 2, 6, 7 } );
156  faces[ 4 ] = PolygonalFace( { 2, 0, 4, 6 } );
157  faces[ 5 ] = PolygonalFace( { 4, 5, 8, 9 } );
159  mesh.build( faces );
160  return mesh;
161 }
162 
163 
164 SCENARIO( "HalfEdgeDataStructure build", "[halfedge][build]" )
165 {
166  GIVEN( "Two triangles incident by an edge" ) {
168  THEN( "The mesh has 4 vertices, 5 edges, 2 faces, 10 half-edges" ) {
169  REQUIRE( mesh.nbVertices() == 4 );
170  REQUIRE( mesh.nbEdges() == 5 );
171  REQUIRE( mesh.nbFaces() == 2 );
172  REQUIRE( mesh.nbHalfEdges() == 10 );
173  }
174  THEN( "The mesh has 4 boundary vertices" ) {
175  VertexIndexRange bdry = mesh.boundaryVertices();
176  std::sort( bdry.begin(), bdry.end() );
177  REQUIRE( bdry.size() == 4 );
178  REQUIRE( bdry[ 0 ] == 0 );
179  REQUIRE( bdry[ 1 ] == 1 );
180  REQUIRE( bdry[ 2 ] == 2 );
181  REQUIRE( bdry[ 3 ] == 3 );
182  }
183  THEN( "The mesh has 4 boundary arcs" ) {
184  std::vector<Arc> bdry = mesh.boundaryArcs();
185  std::sort( bdry.begin(), bdry.end() );
186  REQUIRE( bdry.size() == 4 );
187  // std::cout << " arc=(" << bdry[ 0 ].first << "," << bdry[ 0 ].second << ")" << std::endl;
188  REQUIRE( bdry[ 0 ] == Arc( 0, 2 ) );
189  REQUIRE( bdry[ 1 ] == Arc( 1, 0 ) );
190  REQUIRE( bdry[ 2 ] == Arc( 2, 3 ) );
191  REQUIRE( bdry[ 3 ] == Arc( 3, 1 ) );
192  }
193  }
194  GIVEN( "Three triangles forming a fan around a vertex" ) {
196  THEN( "The mesh has 4 vertices, 6 edges, 3 faces, 12 half-edges" ) {
197  REQUIRE( mesh.nbVertices() == 4 );
198  REQUIRE( mesh.nbEdges() == 6 );
199  REQUIRE( mesh.nbFaces() == 3 );
200  REQUIRE( mesh.nbHalfEdges() == 12 );
201  }
202  THEN( "The mesh has 3 boundary vertices" ) {
203  VertexIndexRange bdry = mesh.boundaryVertices();
204  std::sort( bdry.begin(), bdry.end() );
205  REQUIRE( bdry.size() == 3 );
206  REQUIRE( bdry[ 0 ] == 0 );
207  REQUIRE( bdry[ 1 ] == 1 );
208  REQUIRE( bdry[ 2 ] == 3 );
209  }
210  THEN( "The mesh has 3 boundary arcs" ) {
211  std::vector<Arc> bdry = mesh.boundaryArcs();
212  std::sort( bdry.begin(), bdry.end() );
213  REQUIRE( bdry.size() == 3 );
214  // std::cout << " arc=(" << bdry[ 0 ].first << "," << bdry[ 0 ].second << ")" << std::endl;
215  REQUIRE( bdry[ 0 ] == Arc( 0, 3 ) );
216  REQUIRE( bdry[ 1 ] == Arc( 1, 0 ) );
217  REQUIRE( bdry[ 2 ] == Arc( 3, 1 ) );
218  }
219  }
220  GIVEN( "Four triangles forming a tetrahedron" ) {
222  THEN( "The mesh has 4 vertices, 6 edges, 4 faces, 12 half-edges" ) {
223  REQUIRE( mesh.nbVertices() == 4 );
224  REQUIRE( mesh.nbEdges() == 6 );
225  REQUIRE( mesh.nbFaces() == 4 );
226  REQUIRE( mesh.nbHalfEdges() == 12 );
227  }
228  THEN( "The mesh has no boundary vertices" ) {
229  VertexIndexRange bdry = mesh.boundaryVertices();
230  REQUIRE( bdry.size() == 0 );
231  }
232  THEN( "The mesh has no boundary arcs" ) {
233  std::vector<Arc> bdry = mesh.boundaryArcs();
234  REQUIRE( bdry.size() == 0 );
235  }
236  }
237  GIVEN( "A ribbon with a hole" ) {
239  THEN( "The mesh has 6 vertices, 12 edges, 6 faces, 24 half-edges" ) {
240  REQUIRE( mesh.nbVertices() == 6 );
241  REQUIRE( mesh.nbEdges() == 12 );
242  REQUIRE( mesh.nbFaces() == 6 );
243  REQUIRE( mesh.nbHalfEdges() == 24 );
244  }
245  THEN( "The mesh has 6 boundary vertices" ) {
246  VertexIndexRange bdry = mesh.boundaryVertices();
247  REQUIRE( bdry.size() == 6 );
248  }
249  THEN( "The mesh has 6 boundary arcs" ) {
250  std::vector<Arc> bdry = mesh.boundaryArcs();
251  std::sort( bdry.begin(), bdry.end() );
252  REQUIRE( bdry.size() == 6 );
253  REQUIRE( bdry[ 0 ] == Arc( 0, 2 ) );
254  REQUIRE( bdry[ 1 ] == Arc( 1, 5 ) );
255  REQUIRE( bdry[ 2 ] == Arc( 2, 4 ) );
256  REQUIRE( bdry[ 3 ] == Arc( 3, 1 ) );
257  REQUIRE( bdry[ 4 ] == Arc( 4, 0 ) );
258  REQUIRE( bdry[ 5 ] == Arc( 5, 3 ) );
259  }
260  }
261  GIVEN( "The same ribbon with his hole closed" ) {
263  THEN( "The mesh has 6 vertices, 12 edges, 7 faces, 24 half-edges" ) {
264  REQUIRE( mesh.nbVertices() == 6 );
265  REQUIRE( mesh.nbEdges() == 12 );
266  REQUIRE( mesh.nbFaces() == 7 );
267  REQUIRE( mesh.nbHalfEdges() == 24 );
268  }
269  THEN( "The mesh has 3 boundary vertices" ) {
270  VertexIndexRange bdry = mesh.boundaryVertices();
271  std::sort( bdry.begin(), bdry.end() );
272  REQUIRE( bdry.size() == 3 );
273  REQUIRE( bdry[ 0 ] == 1 );
274  REQUIRE( bdry[ 1 ] == 3 );
275  REQUIRE( bdry[ 2 ] == 5 );
276  }
277  THEN( "The mesh has 3 boundary arcs" ) {
278  std::vector<Arc> bdry = mesh.boundaryArcs();
279  std::sort( bdry.begin(), bdry.end() );
280  REQUIRE( bdry.size() == 3 );
281  REQUIRE( bdry[ 0 ] == Arc( 1, 5 ) );
282  REQUIRE( bdry[ 1 ] == Arc( 3, 1 ) );
283  REQUIRE( bdry[ 2 ] == Arc( 5, 3 ) );
284  }
285  }
286  GIVEN( "A pyramid with a square base" ) {
288  THEN( "The mesh has 5 vertices, 8 edges, 5 faces, 16 half-edges" ) {
289  REQUIRE( mesh.nbVertices() == 5 );
290  REQUIRE( mesh.nbEdges() == 8 );
291  REQUIRE( mesh.nbFaces() == 5 );
292  REQUIRE( mesh.nbHalfEdges() == 16 );
293  }
294  THEN( "The mesh has 0 boundary vertices" ) {
295  VertexIndexRange bdry = mesh.boundaryVertices();
296  REQUIRE( bdry.size() == 0 );
297  }
298  THEN( "The mesh has 0 boundary arcs" ) {
299  std::vector<Arc> bdry = mesh.boundaryArcs();
300  REQUIRE( bdry.size() == 0 );
301  }
302  }
303  GIVEN( "A cube" ) {
305  THEN( "The mesh has 8 vertices, 12 edges, 6 faces, 24 half-edges" ) {
306  REQUIRE( mesh.nbVertices() == 8 );
307  REQUIRE( mesh.nbEdges() == 12 );
308  REQUIRE( mesh.nbFaces() == 6 );
309  REQUIRE( mesh.nbHalfEdges() == 24 );
310  }
311  THEN( "The mesh has 0 boundary vertices" ) {
312  VertexIndexRange bdry = mesh.boundaryVertices();
313  REQUIRE( bdry.size() == 0 );
314  }
315  THEN( "The mesh has 0 boundary arcs" ) {
316  std::vector<Arc> bdry = mesh.boundaryArcs();
317  REQUIRE( bdry.size() == 0 );
318  }
319  }
320  GIVEN( "A box with an open side" ) {
322  THEN( "The mesh has 10 vertices, 15 edges, 6 faces, 30 half-edges" ) {
323  REQUIRE( mesh.nbVertices() == 10 );
324  REQUIRE( mesh.nbEdges() == 15 );
325  REQUIRE( mesh.nbFaces() == 6 );
326  REQUIRE( mesh.nbHalfEdges() == 30 );
327  }
328  THEN( "The mesh has 6 boundary vertices" ) {
329  VertexIndexRange bdry = mesh.boundaryVertices();
330  REQUIRE( bdry.size() == 6 );
331  }
332  THEN( "The mesh has 6 boundary arcs" ) {
333  std::vector<Arc> bdry = mesh.boundaryArcs();
334  REQUIRE( bdry.size() == 6 );
335  }
336  }
337 
338 }
339 
340 SCENARIO( "HalfEdgeDataStructure neighboring relations", "[halfedge][neighbors]" ){
341  GIVEN( "Two triangles incident by an edge" ) {
343  VertexIndexRange nv;
344  THEN( "Vertex 0 has 2 neighboring vertices" ) {
345  mesh.getNeighboringVertices( 0, nv );
346  VertexIndexRange expected = { 1, 2 };
347  REQUIRE( nv.size() == 2 );
348  REQUIRE( std::is_permutation( nv.begin(), nv.end(), expected.begin() ) );
349  }
350  THEN( "Vertex 1 has 3 neighboring vertices" ) {
351  mesh.getNeighboringVertices( 1, nv );
352  VertexIndexRange expected = { 3, 2, 0 };
353  REQUIRE( nv.size() == 3 );
354  REQUIRE( std::is_permutation( nv.begin(), nv.end(), expected.begin() ) );
355  }
356  THEN( "Vertex 2 has 3 neighboring vertices" ) {
357  mesh.getNeighboringVertices( 2, nv );
358  VertexIndexRange expected = { 0, 1, 3 };
359  REQUIRE( nv.size() == 3 );
360  REQUIRE( std::is_permutation( nv.begin(), nv.end(), expected.begin() ) );
361  }
362  THEN( "Vertex 3 has 2 neighboring vertices" ) {
363  mesh.getNeighboringVertices( 3, nv );
364  VertexIndexRange expected = { 2, 1 };
365  REQUIRE( nv.size() == 2 );
366  REQUIRE( std::is_permutation( nv.begin(), nv.end(), expected.begin() ) );
367  }
368  }
369  GIVEN( "A ribbon with a hole" ) {
371  VertexIndexRange nv;
372  THEN( "Vertex 0 has 4 neighboring vertices" ) {
373  mesh.getNeighboringVertices( 0, nv );
374  VertexIndexRange expected = { 4, 5, 1, 2 };
375  REQUIRE( nv.size() == 4 );
376  REQUIRE( std::is_permutation( nv.begin(), nv.end(), expected.begin() ) );
377  }
378  THEN( "Vertex 1 has 4 neighboring vertices" ) {
379  mesh.getNeighboringVertices( 1, nv );
380  VertexIndexRange expected = { 3, 2, 0, 5 };
381  REQUIRE( nv.size() == 4 );
382  REQUIRE( std::is_permutation( nv.begin(), nv.end(), expected.begin() ) );
383  }
384  THEN( "Vertex 2 has 4 neighboring vertices" ) {
385  mesh.getNeighboringVertices( 2, nv );
386  VertexIndexRange expected = { 0, 1, 3, 4 };
387  REQUIRE( nv.size() == 4 );
388  REQUIRE( std::is_permutation( nv.begin(), nv.end(), expected.begin() ) );
389  }
390  }
391 
392  GIVEN( "A box with an open side" ) {
394  VertexIndexRange nv;
395  THEN( "Vertex 0 has 3 neighboring vertices" ) {
396  mesh.getNeighboringVertices( 0, nv );
397  VertexIndexRange expected = { 1, 4, 2 };
398  REQUIRE( nv.size() == 3 );
399  REQUIRE( std::is_permutation( nv.begin(), nv.end(), expected.begin() ) );
400  }
401  THEN( "Vertex 5 has 4 neighboring vertices" ) {
402  mesh.getNeighboringVertices( 5, nv );
403  VertexIndexRange expected = { 8, 4, 1, 7 };
404  REQUIRE( nv.size() == 4 );
405  REQUIRE( std::is_permutation( nv.begin(), nv.end(), expected.begin() ) );
406  }
407  THEN( "Vertex 7 has 3 neighboring vertices" ) {
408  mesh.getNeighboringVertices( 7, nv );
409  VertexIndexRange expected = { 5, 3, 6 };
410  REQUIRE( nv.size() == 3 );
411  REQUIRE( std::is_permutation( nv.begin(), nv.end(), expected.begin() ) );
412  }
413  }
414 }
415 
static Size getUnorderedEdgesFromTriangles(const std::vector< Triangle > &triangles, std::vector< Edge > &edges_out)
std::pair< VertexIndex, VertexIndex > Arc
An arc is a directed edge from a first vertex to a second vertex.
HalfEdgeDataStructure::PolygonalFace PolygonalFace
SCENARIO("HalfEdgeDataStructure build", "[halfedge][build]")
HalfEdgeDataStructure::Arc Arc
HalfEdgeDataStructure makeBox()
HalfEdgeDataStructure makeCube()
void getNeighboringVertices(const Index vi, VertexIndexRange &result) const
std::vector< VertexIndex > VertexIndexRange
Represents an unoriented triangle as three vertices.
HalfEdgeDataStructure makeThreeTriangles()
HalfEdgeDataStructure makeRibbonWithHole()
VertexIndexRange boundaryVertices() const
HalfEdgeDataStructure makeTetrahedron()
REQUIRE(domain.isInside(aPoint))
HalfEdgeDataStructure makeTwoTriangles()
bool build(const Size num_vertices, const std::vector< Triangle > &triangles, const std::vector< Edge > &edges)
std::vector< VertexIndex > PolygonalFace
HalfEdgeDataStructure::Edge Edge
HalfEdgeDataStructure makePyramid()
DGtal is the top-level namespace which contains all DGtal functions and types.
std::vector< Arc > boundaryArcs() const
Aim: This class represents an half-edge data structure, which is a structure for representing the top...
HalfEdgeDataStructure makeTriangulatedDisk()
HalfEdgeDataStructure::Triangle Triangle
HalfEdgeDataStructure::VertexIndexRange VertexIndexRange
GIVEN("A cubical complex with random 3-cells")