# Euler characteristic of 3D triangulation

2 messages
 Hi Adam, Le 05/04/2016 05:06, Adam Getchell a écrit : Hello all, I was debugging my Pachner move code and ran into the lines: frame #0: 0x000000010000fd61 unittests`CGAL::Triangulation_data_structure_3 > >, CGAL::Triangulation_cell_base_with_info_3 > >, CGAL::Parallel_tag>::is_valid(this=0x0000000100703ea8, verbose=false, level=0) const + 769 at Triangulation_data_structure_3.h:3310    3307       if ( cell_count - facet_count + edge_count - vertex_count != 0 ) {    3308         if (verbose)    3309             std::cerr << "Euler relation unsatisfied" << std::endl; -> 3310         CGAL_triangulation_assertion(false);    3311         return false;    3312       }    3313 Which is, I believe, enforcing the constraint that the Euler characteristic of the 3D (odd-dimensional manifold) is zero. This is true only if you have a 3D manifold without boundary which is not the case of your two examples below. (One solution to compute Euler characteristic of an object with boundary is to count cells that must be present in the corresponding closed object, which explain the null set in the reference [1]). For a ball (a 3D manifold with one boundary), the Euler characteristic is 1. Note that this is also only true if your have only one connected component in your object. there is another problem: the formula is vertex_count-edge_count+face_count-cell_count (you inverse the signs). Best Guillaume Now if I look at the (2,3) Pachner move implemented by flip(Cell_handle, facet) I count as follows: On the left we have: Cell count: 1345 + 2345 = 2 Facet count: 134 + 135 + 145 + 345 + 234 + 235 + 245 = 7 Edge count: 13 + 14 + 15 + 23 + 24 + 25 + 34 + 35 + 45 = 9 Vertex count: 5 2 - 7 + 9 - 5 = -1 != 0 On the right we have: Cell count: 1235 + 1234 + 1245 = 3 Facet count: 123 + 125 + 135 + 235 + 124 + 134 + 234 + 145 + 245 = 9 Edge count: 12 + 13 + 14 + 15 + 23 + 24 + 25 + 34 + 35 + 45 = 10 Vertex count: 5 3 - 9 + 10 - 5 = -1 != 0 So, how am I counting wrong? Clearly flip() and flip_really() pass this test. Looking at the literature[1], they count a triangle in the following manner: 1 2-face (the triangle), 3 1-faces (the edges), 3 0-faces (the vertices), plus the null set = 8. (!) Any insights appreciated. Adam Getchell about.me/adamgetchell ```-- =================================================================== Guillaume DAMIAND CNRS - LIRIS UMR 5205 Université Claude Bernard Bâtiment Nautibus (710) 43 Boulevard du 11 Novembre 1918 69622 Villeurbanne Cedex (France) ------------------------------------------------------------------- Tél: +33 (0)4.72.43.14.34 Fax: +33 (0)4.72.43.15.36 Mail: [hidden email] Web: http://liris.cnrs.fr/guillaume.damiand/ =================================================================== ``` smime.p7s (3K) Download Attachment