CGAL users discussion list

["Laurent Rineau (GeometryFactory)" <>]

On Friday 11 December 2009 18:20:26 Ben Supnik wrote:
> Hi Y'all,
> 
> When I insert a point into a delauney triangulation...
> 
> - How many other triangle pairs might have their common edge "flipped"
> to maintain delauney-ness?  Can this cascade?  is there a limit to the
> cascade?

When you insert a new point in a Delaunay triangulation, you can compute the 
conflict zone of the new point, which is the union of the triangles of the 
current triangulation (before insertion) whose circumscribed circle contains 
the new point in their interior. If no circumcircle contain the new point on 
its boundary (co-circular configuration), the new triangulation is computed 
as 
such:
  - all triangles of the conflict zone are removed, and that creates a hole,
  - the hole is stared using the new inserted point.

The co-circular configuration are dealt with a symbolic perturbation, so that 
a co-circular configuration is equivalent to a non-co-circular one.

> - Do the CDT CGAL classes provide a way to determine this from a point
> insert?  (E.g. a visitor or notifier that I could override?)

You can compute the conflict zone using the member functions  get_conflicts 
or 
get_conflicts_and_boundary, before you insert the new point.

Once you have computed the conflict zone, you can use the member function 
star_hole (documented in the base class Triangulation_2<Gt,Tds>). One 
insertion in a Delaunay_triangulation_2<Gt,Tds> is equivalent to the use of 
get_conflicts_and_boundary+star_hole.

Visitors in CGAL triangulations would be a good solution. I have thought 
about 
that several time, but for the moment nobody has found enough time+motivation 
to write a proposal, get it reviewed, and implement it.

-- 
Laurent Rineau, PhD
R&D Engineer at GeometryFactory           http://www.geometryfactory.com/
Release Manager of the CGAL Project       http://www.cgal.org/