CGAL users discussion list

Le Mar 3 juillet 2007 23:07, Thomas Zangl - Home a écrit :
> I encounter a bug using a certain set of circles:
> CGAL error: assertion violation!
> Expr: result
> File: /home/TZi/CGAL-3.3/include/CGAL/Regular_triangulation_2.h
> Line: 710
> Aborted (core dumped)
>
> Attached you can find the program and the points (no makefile supplied)

Hi Thomas,
Next time, could you please remove the unnecessary #includes, and try to
minimize your test case (by minimizing the number of inserted points?

> I am using CGAL 3.3 (with the fix of stack_flip_4_2 in
> Regular_triangulation_2.h applied).

The bug is the following: in a triangulation, if a point is inserted
twice, the second insertion is usually simply discarded. But in the case
of a regular triangulation, the point with the lower weight is hidden by
the one with the higher weight (and these weights may be equal). This
should not happen in the case when the weights are equal too, i.e. in the
case the weighted points are the same. At least is_valid does not accept
this (and this is probably reasonable).

There are various options to remove this bug, depending on whether you
want duplicated vertices (with same weight) or not:

- workarounds: not inserting the same weighted point twice or not calling
is_valid() ;-)

- if you want repeated vertices, changing is_valid to take this into
account (I can send you a diff if you want, but I consider this to be a
bad idea).

- best approach, in my view: if you want to filter out the duplicated
points (only when they have the same weight, of course), rewrite the
insert function in the following way (I mark the lines I added).

template < class Gt, class Tds >
typename Regular_triangulation_2<Gt,Tds>::Vertex_handle
Regular_triangulation_2<Gt,Tds>::
insert(const Weighted_point &p, Locate_type lt, Face_handle loc, int li)
{
    Vertex_handle v;
    switch (lt) {
    case Base::VERTEX:
        {
            CGAL_precondition (dimension() >= 0);
            if (dimension() == 0) {
                // in this case locate() oddly returns loc = NULL and li = 4,
                // so we work around it.
                loc = finite_vertex()->face();
                li = 0;
            }

            Vertex_handle vv = loc->vertex(li);
            if (power_test (vv->point(), p) < 0) {
                return hide_new_vertex (loc, p);
            }
            if (power_test (vv->point(), p) > 0) { //----NEW LINE----
              v = this->_tds.create_vertex();
              v->set_point(p);
              exchange_incidences(v,vv);
              hide_vertex(loc, vv);
              regularize (v);
              return v;
            }                                      //----NEW LINE----
            return vv;                             //----NEW LINE----
        }
    case Base::EDGE:
<--------------THE REST DOES NOT CHANGE-------------->

-- 
Camille