CGAL users discussion list

[400555 <>]

Dear Manuel, thank you for answer!

Could you please tell me what is 

1) "validity of the geometric embedding (orientation of faces)"

2) "combinatorial validity"

I figured out that my triangulation becomes not valid after my first flip, for both cases: Delaunay_triangulation_2 and Triangulation_2. 

And I don't understand why.

As I understand triangulation if it is not Delaunay could be not valid if some edges cross, and for Delaunay additional check for circle criteria,  anything else?

>> This is guaranteed only if the precondition is fulfilled. You should compile your code in debug mode, then the preconditions will be tested for explicitly.

What do you mean "precondition is fulfilled" ?

Also, could you please say in easy words what does it mean: exact \ inexact predicates \ constructions ?

I read manual but didn't find explanation, maybe because of my hurry.

And also a small questions. When I print vertex->point() - I see something like (2; 3) when really it should be (1,8799; 2,789). Do you know why?

Sorry for many questions. I will very appreciate if you answer them.

Thank you.

On Wed, Jul 29, 2009 at 1:05 PM, Manuel Caroli <> wrote:

Hi,

400555 wrote:

[...]

So, In the beginning I have correct Delaunay. Then after several flipping I get that is_valid() != 1. By the way what exactly validity is_valid() function checks? If Delaunay - I don't need it.

1) The Delaunay_triangulation_2::is_valid() checks the Delaunay property.
2) Triangulation_2::is_valid() checks the validity of the geometric embedding (orientation of faces)
3) Triangulation_data_structure_2::is_valid() checks combinatorial validity.

1 does not apply to you. 2 calls 3 so I would recommend you to use 2.
All this is described in the documentation btw.

If it checks for not edge crossing etc - then how is it possible that I am getting not valid structure after applying several T.flip(f, i), in manual I see that this function "guaranteed to lead to a valid triangulation".

This is guaranteed only if the precondition is fulfilled. You should compile your code in debug mode, then the preconditions will be tested for explicitly.

About "square perimeter of a vertex" I meant that I have square border of my domain, all points lie inside of this square and also some of them on the border (so in fact on the sane line).

If you use an exact predicates kernel degenerate cases will be treated correctly.

Do you have any idea what could be wrong?

Still no because I don't know what your code is doing ;-) These are just hints that are supposed to help you debug your code.

Manuel

Thank you.

On Wed, Jul 29, 2009 at 11:00 AM, Manuel Caroli < <mailto:>> wrote:

   Dear 400555,


   400555 wrote:

       Hello !
       Could you please help with my problem.

       I make Delaunay_2 for set of points.

       Then, on each iteration I change positions of point and
       accordingly to my criteria do Flip of some edges (only for finite).
       (and I checked that new edge obtained after flipping also stand
       finite)

   Note that as soon as you change point coordinates or do flips
   manually the triangulation is most probably not Delaunay anymore. So
   there are no guarantees anymore about the behavior of e.g. the
   insert function.


       After somewhile I find that for one edge vertex(i) and vertex
       which is mirror_vertex to it - become the same.

       Do you know how is it possible?

   no, because I don't know what your code is doing. You might want to
   use the is_valid() functions from Triangulation_2 and
   Triangulation_data_structure_2 to check whether you still have a
   valid triangulation after each of your modifications.


       There is a part of my code below. ov1 becomes equal to ov2.
       Someone knows why?

   Your code below does not modify the triangulation. I suppose the
   error occurs already during modification. See above.


       Can the fact that I have also square perimeter of vertices
       (which are lie on the line) be affected to this problem?

   I'm sorry I don't understand this one. What do you mean by the
   square perimeter of a vertex?

   About your question before about edge with info: As edges are not
   represented explicitly there is no possibility to store some info
   with it. However you could store the info in one of the incident
   faces, then you can look it up in constant time.

   best

   Manuel




       for (Finite_edges_iterator2 eit = T.finite_edges_begin(); eit !=
       T.finite_edges_end(); ++eit)
       {

           Edge2 ed = *eit;

           Face_handle2 f = ed.first;
           int i = ed.second;
           Vertex_handle2 vh1 = f->vertex(T.cw(i));
           Vertex_handle2 vh2 = f->vertex(T.ccw(i));

           if ((f->vertex(i) != T.infinite_vertex()) &&
       (f->mirror_vertex(i) != T.infinite_vertex()))
           {

                ov1 = f->vertex(i)->info();
                ov2 = T.mirror_vertex(f, i)->info();

                - - - - - -
           }

           - - - - - }

       Thank you.


   --    You are currently subscribed to cgal-discuss.
   To unsubscribe or access the archives, go to
   https://lists-sop.inria.fr/wws/info/cgal-discuss

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss