# CGAL_triangulation_precondition vs. CGAL_triangulation_expensive_precondition

17 messages
Open this post in threaded view
|

## CGAL_triangulation_precondition vs. CGAL_triangulation_expensive_precondition

 Hello all,I’m searching for documentation on these two functions to determine if I am using them correctly. What is the difference between them? (What makes a particular check expensive?)I have code which does a (2,6) Pachner move that starts out as:void move_26(Delaunay* const D3,             Cell_handle one_three_simplex,             unsigned neighbor_index,             Cell_handle three_one_simplex) noexcept {  // Preconditions  CGAL_triangulation_precondition((dimension() == 3)                                   && (0 <= neighbor_index)                                   && (neighbor_index < 4));  CGAL_triangulation_precondition(one_three_simplex.has_neighbor                                  (three_one_simplex));  CGAL_triangulation_expensive_precondition(is_cell(one_three_simplex,                                                    three_one_simplex));  // Get vertices of common face  unsigned i1 = (neighbor_index + 1)&3;  unsigned i2 = (neighbor_index + 2)&3;  unsigned i3 = (neighbor_index + 3)&3; Adam Getchellabout.me/adamgetchell
Open this post in threaded view
|

## Re: CGAL_triangulation_precondition vs. CGAL_triangulation_expensive_precondition

 Hi, Adam, I use the delaunay triangulation package for triangulation, and I found out that the four vertices of computed cells would lie on the same plane, as the images(I render only the cells incident to one point). But According to my understanding of delaunay triangulation, such kind of triangulation would not be a right delaunay triangulation. Here is my code: //define DT as delaunay triangulation. std::vector< Point> points; //restores the points of input mesh, saying a uniformly sampled cube DT.insert(points.begin(),points.end()); Any idea about the problem? Thank you very much. Monica
Open this post in threaded view
|

## Re: CGAL_triangulation_precondition vs. CGAL_triangulation_expensive_precondition

 Administrator In reply to this post by Adam Getchell Le 25/04/15 08:06, Adam Getchell a écrit : > Hello all, > > I’m searching for documentation on these two functions to determine if I > am using them correctly. What is the difference between them? (What > makes a particular check expensive?) Hi Adam, Preconditions are documented in the developer manual, see http://doc.cgal.org/latest/Manual/devman_checks.htmlTo schematize: Preconditions are "expensive" for instance when they need to browse all vertices (complexity O(n)) or all cells (complexity O(n^2)). "Normal" preconditions are in general constant-time. Best, -- Monique Teillaud http://www.loria.fr/~teillaud/INRIA Nancy - Grand Est, LORIA Institut National de Recherche en Informatique et Automatique -- You are currently subscribed to cgal-discuss. To unsubscribe or access the archives, go to https://sympa.inria.fr/sympa/info/cgal-discuss
Open this post in threaded view
|

## Re: CGAL_triangulation_precondition vs. CGAL_triangulation_expensive_precondition

 In reply to this post by BRYang Hi brYang,            How do you draw the cells ?  or like the code show below:   Delaunay_triangulation::finite_face_iterator begin=DT.finite_facets_begin(),end=finite_facets_end();         for(;begin!=end;++begin){                 Delaunay_triangulation::Cell_handle cell_handle=(*begin).first;                 int index=(*begin).second;                 int i=(index+1)&3,j=(index+2)&3,k=(index+3)&3;                 std::cout<vertex(i)->point()<<","\                             <vertex(j)->point()<<","\                             <vertex(k)->point()<
Open this post in threaded view
|

## Re: CGAL_triangulation_precondition vs. CGAL_triangulation_expensive_precondition

 Hi TableYoung, I use fci->vertex(i)->point() ,where i = 0,1,2,3 to access the four vertices of cells. And for the cells incident to a vertex, I use : //suppose dt is the delaunay triangulation std::list cell_vector; dt.incident_cells(vh, std::back_inserter(cell_vector)); to access all the incidental cells of vh Then I draw all the line segments of each cell by connecting any two of the four vertices of it. But it still shows as the image above. Is there any other possibility for causing this situation? Baorong Yang
Open this post in threaded view
|

## Re: CGAL_triangulation_precondition vs. CGAL_triangulation_expensive_precondition

 In reply to this post by teillaud Thanks Monique! Adam Getchell about.me/adamgetchell > On Apr 27, 2015, at 7:24 AM, Monique Teillaud <[hidden email]> wrote: > > Le 25/04/15 08:06, Adam Getchell a écrit : >> Hello all, >> >> I’m searching for documentation on these two functions to determine if I >> am using them correctly. What is the difference between them? (What >> makes a particular check expensive?) > > Hi Adam, > > Preconditions are documented in the developer manual, see > http://doc.cgal.org/latest/Manual/devman_checks.html> > To schematize: > Preconditions are "expensive" for instance when they need to browse all vertices (complexity O(n)) or all cells (complexity O(n^2)). > "Normal" preconditions are in general constant-time. > > Best, > -- > Monique Teillaud > http://www.loria.fr/~teillaud/> INRIA Nancy - Grand Est, LORIA > Institut National de Recherche en Informatique et Automatique > > -- > You are currently subscribed to cgal-discuss. > To unsubscribe or access the archives, go to > https://sympa.inria.fr/sympa/info/cgal-discuss> > -- You are currently subscribed to cgal-discuss. To unsubscribe or access the archives, go to https://sympa.inria.fr/sympa/info/cgal-discuss
Open this post in threaded view
|

## Re: CGAL_triangulation_precondition vs. CGAL_triangulation_expensive_precondition

 In reply to this post by BRYang Hi,      could you give me your points coordinate, i run it on my machine, and drawing the result. BR  Tobe Yang
Open this post in threaded view
|

## Re: CGAL_triangulation_precondition vs. CGAL_triangulation_expensive_precondition

 In reply to this post by BRYang Hi brYang           pictures below is my result use your points make triangulation.i find it's incorrect on surface .inside is all right.i don't know why this happened.
Open this post in threaded view
|

## Re: CGAL_triangulation_precondition vs. CGAL_triangulation_expensive_precondition

 Thank you, TableYoung. I got the same result as you. But I also have no idea why this happens.. Baorong Yang
Open this post in threaded view
|

## Re: CGAL_triangulation_precondition vs. CGAL_triangulation_expensive_precondition

 Hi BrYang             i seemed to know why this happened, i have tested a case that i used part of your points(about 2560 ) then i made delaunay triangulation,the picture show below that the last point locate on surface .According to the principle of Delaunay algorithm, the CGAL code is always working right. You may search about the Delaunay algorithm.Best Regards TobeYang
Open this post in threaded view
|

## Re: CGAL_triangulation_precondition vs. CGAL_triangulation_expensive_precondition

 Hi, TobeYang, I got what you mean. My concern is what does the "empty sphere property" of Delaunay Triangulation mean? If a point is on the surface of a tetrahedron(cell), does it still satisfy the property of DT?
Open this post in threaded view
|

## Re: CGAL_triangulation_precondition vs. CGAL_triangulation_expensive_precondition

 In reply to this post by TableYoung Hi TobeYang,  As shown in the picture attached, the cells fci in blue are the cells(tetrahedrons) incident to the vertex(the vertex in peacock blue) and with their circumcenter outside the input mesh domain  and the cells in red are the cells incident to the same vertex and with their circumcenter inside the bounding box of input mesh or on the surface of input mesh. It's clearly that there are some cells(in blue) voiding the "empty sphere" property. Do you have any idea about why this happens? Thanks, Best regards, Baorong Yang
Open this post in threaded view
|

## Re: CGAL_triangulation_precondition vs. CGAL_triangulation_expensive_precondition

 Hi brYang          I think all this happened because of there are some degenerate tetrahedrons appeared. four vertices of a tetrahedron are lie on a plane( in mesh generation ,it like silver), circumcircle is a circle not a sphere. above is my personal opinion, maybe it's incorrect. BR TobeYang
Open this post in threaded view
|

## Re: CGAL_triangulation_precondition vs. CGAL_triangulation_expensive_precondition

 yes, I check the mininum dihedral angle of each cell and it seems that there are so many slivers generated from delaunay triangulation, it could be the limitation of DT. Any way, thank you so much for your patience. Best regards, Baorong Yang
Open this post in threaded view
|

## Re: CGAL_triangulation_precondition vs. CGAL_triangulation_expensive_precondition

 In reply to this post by TableYoung Hi TobeYang, another question about CGAL.. Do you know how to access the edge handle of edges of a facet, saying Facet fi , which is also a facet of a cell of DT. Thanks, Baorong Yang