CGAL_triangulation_preconditio


CGAL_triangulation_preconditio

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 Getchell
about.me/adamgetchell 
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 
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.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 constanttime. 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 cgaldiscuss. To unsubscribe or access the archives, go to https://sympa.inria.fr/sympa/info/cgaldiscuss 
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<<cell_handle>vertex(i)>point()<<","\ <<cell_handle>vertex(j)>point()<<","\ <<cell_handle>vertex(k)>point()<<std::endl; } Maybe the code draw triangulation data struct is incorrect, because Delaunay triangulation algorithm is stable, try to find out is there some wrong with your code; BR TobeYang 
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_handle> 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 
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 constanttime. > > 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 cgaldiscuss. > To unsubscribe or access the archives, go to > https://sympa.inria.fr/sympa/info/cgaldiscuss > >  You are currently subscribed to cgaldiscuss. To unsubscribe or access the archives, go to https://sympa.inria.fr/sympa/info/cgaldiscuss 
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 
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. 
Thank you, TableYoung. I got the same result as you. But I also have no idea why this happens..
Baorong Yang 
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 
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? 
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 
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 
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 
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 
In reply to this post by BRYang
hi, i don't know what you want to do ,but i think you can try 3d mesh generation ,if you want get surface mesh , you can try to use Surface mesh generation algorithm.  Original  From: "ybr";<[hidden email]>; Date: Thu, Apr 30, 2015 08:48 AM To: "cgaldiscuss"<[hidden email]>; Subject: Re: [cgaldiscuss] CGAL_triangulation_precondition vs.CGAL_triangulation_expensive_precondition 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  View this message in context: http://cgaldiscuss.949826.n4.nabble.com/CGALtriangulationpreconditionvsCGALtriangulationexpensivepreconditiontp4660727p4660772.html Sent from the cgaldiscuss mailing list archive at Nabble.com.  You are currently subscribed to cgaldiscuss. To unsubscribe or access the archives, go to https://sympa.inria.fr/sympa/info/cgaldiscuss 
Free forum by Nabble  Edit this page 