[vtk-developers] Issue found in the vtkDelaunay2D filter?

[Philippe Pébay]

Hello all,

I think that I just ran into a numerical instability of the Delanauy 2D
triangulator, when used with a specified boundary constraint. For those
interested in this issue, please look at the attached picture: the boundary
constraint is in the upper left corner, which also includes the generators
in red. The CDT is shown in the upper right corner, where I indicated the
problematic edge: clearly, the 2 adjacent triangles do not satisfy the
empty ball property, and that edge should be flipped. This is confirmed by
the Voronoi diagram underneath where we see one cell protruding into
another.

In fact the highlighted edge should be flipped to obtain a correct CDT, and
this what happens indeed when I nudge on of the points with a tiny epsilon.
See the correct picture attached (where the "forced edges" for the sake of
the constraint have been removed).

By the way I observed similar instabilities, but with *slightly different
generators*, when calling the Delaunay 2D from ParaView.

I intend to work on the Delaunay 2D triangulator, but in collaboration with
whoever is interested in this. Please let me know.

Thanks
P

-- 
Philippe Pébay, PhD
Director of Visualization and High Performance Computing /
Directeur de la Visualisation et du Calcul Haute Performance
Kitware SAS
26 rue Louis Guérin, 69100 Villeurbanne, France
+33 (0) 6.83.61.55.70 / 4.37.45.04.15
http://www.kitware.fr <http://www.kitware.fr/>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://public.kitware.com/pipermail/vtk-developers/attachments/20130309/b99a0b15/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: IncorrectCDT.png
Type: image/png
Size: 51701 bytes
Desc: not available
URL: <http://public.kitware.com/pipermail/vtk-developers/attachments/20130309/b99a0b15/attachment-0002.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Star13-hole-all.png
Type: image/png
Size: 38117 bytes
Desc: not available
URL: <http://public.kitware.com/pipermail/vtk-developers/attachments/20130309/b99a0b15/attachment-0003.png>