Skip to Content.
Sympa Menu

cgal-discuss - Re: [cgal-discuss] stupid delauney triangulation question

Subject: CGAL users discussion list

List archive

Re: [cgal-discuss] stupid delauney triangulation question


Chronological Thread 
  • From: "Laurent Rineau (GeometryFactory)" <>
  • To:
  • Subject: Re: [cgal-discuss] stupid delauney triangulation question
  • Date: Mon, 14 Dec 2009 10:58:42 +0100
  • Organization: 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/



Archive powered by MHonArc 2.6.16.

Top of Page