CGAL users discussion list

[Pedro Machado Manhães de Castro <>]

Hello,

You can test whether a vertex v relocated to p triggers combinatorial changes, by:
1 - Storing the actual location of v somewhere ( Point fp  = v->point() ).
2 - Setting the location of your vertex v to p ( v->set_point(p) ).
3 - Checking whether each adjacent cells of v are well-oriented (predicate: orientation).
4 - Checking whether each adjacent facets of v verify the empty-sphere property (predicate: side_of_sphere).
5 - Set the location of v to p, and you are done ( v->set_point(fp) ).
Your relocation will not trigger combinatorial changes if and only if 3 and 4 are true.

Better approaches exist. Here are some bib:

L. Guibas, D. Russel, An Empirical Comparison of Techniques for Updating Delaunay Triangulations, ACM Symp. on Computational Geometry, pp. 170-179, 2004

Pedro Machado Manhães de Castro,
Jane Tournois,
Pierre Alliez,
 and Olivier Devillers.
Filtering relocations on a Delaunay triangulation.
Computer Graphics Forum,
28:1465-1474,
2009.
Note: Special issue for EUROGRAPHICS Symposium on Geometry Processing.

Best regards,
Pedro

On Sun, Sep 13, 2009 at 10:20 AM, dmyan <> wrote:

Hello,

 

    I have a question about CGAL's Delaunay triangulation 3D.

    Assume I have a 3D Delaunay triangulation and I am moving one of its vertex. Is there a efficient way to test whether the moving point triggers a combinatorial change of the DT?

    Thanks in advance!

 

Best regards

 

Dongming

 

----- Original Message -----

From:

To:

Sent: Sunday, September 13, 2009 4:45 AM

Subject: [cgal-discuss] CGAL_triangulation_precondition

Hello !

Could you tell me what means "CGAL_triangulation_precondition()" in CGAL code ?

I thought that when condition fails - then it returns from subroutine, but when I added in function  Triangulation_2<Gt, Tds>::flip(Face_handle f, int i)

following row:

CGAL_triangulation_precondition(1 == 2);

it has no any affect.

Thank you.

Vitaliy.