CGAL users discussion list

[Manuel Caroli <>]

400555 wrote:
> Dear Manuel, thank you for answer!
>
> Could you please tell me what is 
> 1) "validity of the geometric embedding (orientation of faces)"
checks whether the faces are well oriented (counterclockwise I think).
> 2) "combinatorial validity"
checks e.g. whether a vertex is a vertex of the face it points to, 
whether the neighboring relation is coherent and so on.
> 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?
see above. Crossing edges will yield faces of wrong orientation.
>  >> 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" ?
It would be helpful if you could see the documentation:

  void  	  t.flip ( Face_handle f, int i)  	 Exchanges the edge 
incident to f and f->neighbor(i) with the other diagonal of the 
quadrilateral formed by f and f->neighbor(i).
Precondition: 	The faces f and f->neighbor(i) are finite faces and their 
union form a convex quadrilateral.

If you compile your code in debug mode it will abort with an error 
message if you call flip while the preconditions are not fulfilled (as I 
wrote before).
> 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.
You'll have to browse trough the Parts I-III of the manual. I think you 
should have a more thorough look on chapters 1, 4 and especially 7.

For triangulations you should be well off using the predefined 
Exact_predicates_exact_constructions_kernel.
> 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?
no. How do you print it?
> Sorry for many questions. I will very appreciate if you answer them.
You should try to find the problem in your code with the tools I told 
you. As I don't see your code, and neither have the time to debug it, 
I'm afraid I cannot be too helpful answering questions like "why doesn't 
it work".

Good luck!

Manuel

> Thank you.
>
> On Wed, Jul 29, 2009 at 1:05 PM, Manuel Caroli 
> < <mailto:>> 
> 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:>
>         
> <mailto:
>         
> <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