Re: [visad] The results of your email commands

• To: scratchboom@xxxxxxxxx
• Subject: Re: [visad] The results of your email commands
• From: Curtis Rueden <ctrueden@xxxxxxxx>
• Date: Tue, 7 Apr 2009 15:07:59 -0500

Hi,

I agree with Bill that you should use DelaunayWatson where appropriate. In
general, for less than a few thousand points in 2D, the Watson algorithm
will perform more efficiently than Clarkson, because Clarkson has more
structural overhead. However, Watson is O(n^2) and supports only 2D, whereas
Clarkson is O(n log n) and supports higher dimensional data.

Unfortunately, both algorithms have limitations. Both can have problems with
colinear and/or colocated points. I have seen Watson generate overlapping
triangles on rare occasion. And the Clarkson algorithm truncates all values
to integers during computation, exascerbating the colinearity issue.

To work around these issues, we have provided two methods in visad.Delaunay,
scale and perturb. The scale method scales data by a given multiplier, which
is useful if you have values clumped within 1.0f of one another and wish to
use the Clarkson algorithm. (Clarkson will fail horribly with such data
unless scaled so that data points are distinct as integers). The perturb
method randomly permutes each sample up to a given epsilon, to help "shake
up" colinear and colocated points.

In your example, if I add the call:
  Delaunay.scale(samples, 2, false);
before constructing the DelaunayClarkson object, then the triangulation
finishes without exception.

There was talk a while back of integrating the TRIANGLE package (
http://people.sc.fsu.edu/~burkardt/c_src/triangle/triangle.html) into VisAD
to improve our triangulation logic, but unfortunately it is not a priority
for us right now.

-Curtis

On Sat, Apr 4, 2009 at 8:35 AM, Bill Hibbard <hiding@xxxxxxxxx> wrote:

>  It looks like you've found a bug in the DelaunayClarkson
> code. As I recall, a programmer at SSEC converted
> Clarkson's C code to Java at least ten years ago. Perhaps
> someone will try to hunt down this bug. But since your data
> set is small and has dimension = 2, I recommend that you
> try replacing the call to the DelaunayClarkson constructor
> with:
>
>   DelaunayWatson d = new DelaunayWatson(samples);
>
> Good luck,
> Bill
>
> ----- Original Message -----
> From: "áÂÁËÕÍÏ× áÎÄÒÅÊ"
> To: visad@xxxxxxxxxxxxxxxx
> Subject: Re: [visad] The results of your email commands
> Date: Sat, 4 Apr 2009 15:56:05 +0400
>
>
> Hello, all!
> I try to use Delaunay triangulation in the following way:
>
> /*five 2d points*/
> float[][] samples = {
> {0.0f, 0.1f, 0.2f, 0.3f, 0.4f},
> {0.0f, 0.5f, 0.0f, 0.5f, 0.0f}
> };
> DelaunayClarkson d = new DelaunayClarkson(samples);
>
> But get an exception
> Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 5
> at visad.DelaunayClarkson.(DelaunayClarkson.java:1120)
> at Test.main(Test.java:95)
> at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
> at
>
> sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:39)
> at
>
> sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:25)
> at java.lang.reflect.Method.invoke(Method.java:597)
>
> Can you tell me, please, what is the trouble?
> thaks!
>
> _______________________________________________
> visad mailing list
> visad@xxxxxxxxxxxxxxxx
> For list information, to unsubscribe, visit:
> http://www.unidata.ucar.edu/mailing_lists/
>
>
> -- Be Yourself @ mail.com!
> Choose From 200+ Email Addresses
> Get a *Free* Account at www.mail.com <http://www.mail.com/Product.aspx>!
>
> _______________________________________________
> visad mailing list
> visad@xxxxxxxxxxxxxxxx
> For list information, to unsubscribe, visit:
> http://www.unidata.ucar.edu/mailing_lists/
>
>

• References:
  • Re: [visad] The results of your email commands
    • From: Bill Hibbard