Bruno-<div><br></div><div>The work was influenced by Guibas and Stolfi's point walking algorithm. It is described quickly in <a href="http://gandalf.psych.umn.edu/groups/schraterlab/schrater_lab/publications/bc.pdf">http://gandalf.psych.umn.edu/groups/schraterlab/schrater_lab/publications/bc.pdf</a>. There are other references, but with a quick look I could not find the original reference in </div>

<div><div>[13] Leonidas Guibas and Jorge Stol. Primitives for the manipulation of general subdivisions and the</div><div>computation of Voronoi diagrams. ACM Transactions on Graphics, 4(2):75{123, 1985.</div><div><br></div>

<div>Will</div><br><div class="gmail_quote">On Thu, Aug 12, 2010 at 10:12 AM, wyldckat <span dir="ltr"><<a href="mailto:bruno.santos@bluecape.com.pt">bruno.santos@bluecape.com.pt</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">

<br>
Greetings Will and David,<br>
<br>
@David: I don't believe it's 100% related to the bug you posted, since<br>
vtkDelaunay2D hasn't crashed with us (yet).<br>
<br>
@Will: Thank you for the link and we'll start on that ASAP. But could you<br>
please also provide the link or references for the textual information about<br>
the currently implemented code?<br>
Because it feels that the current code fails sometimes only because it uses<br>
an absolute referential for finding the triangles, instead of using various<br>
relative referentials for each relevant section of the geometry. So, by<br>
using multiple referentials, the numerical precision errors could be<br>
minimized/eliminated with some additional heuristic. And without some<br>
paper/text/document as reference for the current code, it will harder to<br>
analyze the current implementation.<br>
<br>
Best regards,<br>
Bruno<br>
<div><div></div><div class="h5"><br>
<br>
David Doria-2 wrote:<br>
><br>
> On Tue, Aug 10, 2010 at 2:44 PM, Will Schroeder<br>
> <<a href="mailto:will.schroeder@kitware.com">will.schroeder@kitware.com</a>> wrote:<br>
>> Hi Bruno-<br>
>> I'm sorry about your problem with Delaunay2D, although it<br>
>> not totally unexpected. Due to numerical precision, the implemented<br>
>> algorithm can be made to fail. To really fix this we would have to<br>
>> rewrite<br>
>> the algorithm using arbitrary precision methods. (See for<br>
>> example <a href="http://www.cs.cmu.edu/~jrs/jrspapers.html" target="_blank">http://www.cs.cmu.edu/~jrs/jrspapers.html</a> as a starting point.)<br>
>> In the short term, you can sometimes work around the algorithm<br>
>> by injecting the points in a different order, e.g., randomizing them or<br>
>> changing into a more spatially dispersed order. Try that and if it<br>
>> doesn't<br>
>> work let me know and we will try to fix the existing code to swallow<br>
>> numerical degeneracies. Then one day will figure out how to get arbitrary<br>
>> precision into these algorithms and do it right...<br>
>> Will<br>
><br>
> I submitted a bug the other day that may be related to this?<br>
><br>
> <a href="http://public.kitware.com/Bug/view.php?id=11102" target="_blank">http://public.kitware.com/Bug/view.php?id=11102</a><br>
><br>
> Thanks,<br>
><br>
> David<br>
</div></div><div class="im">> _______________________________________________<br>
> Powered by <a href="http://www.kitware.com" target="_blank">www.kitware.com</a><br>
><br>
> Visit other Kitware open-source projects at<br>
> <a href="http://www.kitware.com/opensource/opensource.html" target="_blank">http://www.kitware.com/opensource/opensource.html</a><br>
><br>
> Follow this link to subscribe/unsubscribe:<br>
> <a href="http://www.vtk.org/mailman/listinfo/vtk-developers" target="_blank">http://www.vtk.org/mailman/listinfo/vtk-developers</a><br>
><br>
><br>
><br>
<br>
--<br>
</div>View this message in context: <a href="http://vtk.1045678.n5.nabble.com/vtkDelaunay2D-fails-to-tesselate-a-partially-complex-geometry-with-one-hole-tp2290262p2473259.html" target="_blank">http://vtk.1045678.n5.nabble.com/vtkDelaunay2D-fails-to-tesselate-a-partially-complex-geometry-with-one-hole-tp2290262p2473259.html</a><br>


<div><div></div><div class="h5">Sent from the VTK - Dev mailing list archive at Nabble.com.<br>
_______________________________________________<br>
Powered by <a href="http://www.kitware.com" target="_blank">www.kitware.com</a><br>
<br>
Visit other Kitware open-source projects at <a href="http://www.kitware.com/opensource/opensource.html" target="_blank">http://www.kitware.com/opensource/opensource.html</a><br>
<br>
Follow this link to subscribe/unsubscribe:<br>
<a href="http://www.vtk.org/mailman/listinfo/vtk-developers" target="_blank">http://www.vtk.org/mailman/listinfo/vtk-developers</a><br>
<br>
</div></div></blockquote></div><br><br clear="all"><br>-- <br>William J. Schroeder, PhD<br>Kitware, Inc.<br>28 Corporate Drive<br>Clifton Park, NY 12065<br><a href="mailto:will.schroeder@kitware.com">will.schroeder@kitware.com</a><br>

<a href="http://www.kitware.com">http://www.kitware.com</a><br>(518) 881-4902<br>
</div>