Re: failure of delauny triangulation

• To: visad-list@xxxxxxxxxxxxx
• Subject: Re: failure of delauny triangulation
• From: Curtis Rueden <curtis@xxxxxxxxxxxxx>
• Date: Fri, 11 Apr 2003 15:11:22 -0500

Hi Donna,

I have seen DelaunayWatson fail for large numbers of points occasionally
(it seems to produce "large" triangles connecting three non-neighboring
points, for some reason that I don't understand).  Unfortunately, I didn't
conceive of the algorithm (I just ported it from C) so it's difficult to
determine what's going wrong.

My advice is to try DelaunayClarkson and see if that works any better for
your data.  DelaunayClarkson seems more reliable, although it does
unfortunately round data points to the nearest integer, meaning that close
points must be scaled up first (your data shouldn't have this problem).

-Curtis

At 02:49 PM 4/11/2003, Donna L Gresh wrote:
>I've been using DelaunayWatson( set of two dimensional vertices) quite 
>effectively for awhile. However just recently I found a case it's failing on. 
>The data is not fundamentally different (at least in any way obvious to me)  
>for this failing case, so I'm wondering what's going on. Attached is the list 
>of x y points.  There are no duplicates. The failure message doesn't help too 
>much, just 
>
>visad.SetException: Delaunay.finish_triang: error in triangulation! 
>
>        at visad.Delaunay.finish_triang(Delaunay.java:592) 
>
>        at visad.DelaunayWatson.<init>(DelaunayWatson.java:318) 
>
>
>
>Any ideas?   
>BTW "jiggling" the points is really not an option for me, as for other reasons 
>I need them to be their original values. I'd rather remove offending points 
>than change any. 
>
>
>Donna L. Gresh, Ph.D.
>Optimization and Mathematical Software Group
>IBM T.J. Watson Research Center
>(914) 945-2472
>http://www.research.ibm.com/people/g/donnagresh
>gresh@xxxxxxxxxx