Re: [visad] question using Visad Delaunay

• To: Quike - <quikesan@xxxxxxxxx>
• Subject: Re: [visad] question using Visad Delaunay
• From: Curtis Rueden <ctrueden@xxxxxxxx>
• Date: Sat, 19 Dec 2009 14:22:56 -0600

Hi Quike,

The first way uses the factory (that heuristically decides which method will
> be use), and then uses the method test. So I guess this would be quite
> expensive, but will provide an exact triangulation.
>

The factory heuristic is O(1) and should not add any extra overhead to the
triangulation. The test call is expensive, and is mainly useful for
debugging, since it will not actually "fix" an incorrect triangulation.
There is another method in the Delaunay class called "improve" that uses
iterative edge flipping to improve the triangulation (designed for use with
triangulations produced by DelaunayFast), but it will not fix problems such
as overlapping or degenerate triangles, and it may not always converge on
the optimal triangulation either.

My question is, if used this way, DelaunayClarkson could return a wrong
> triangulation, and if it would be faster than using the factory method (or
> at least always O(N*logN) ).
>

DelaunayClarkson was originally coded to support integer samples. We just
translated it from C to Java, so even though VisAD works with floats and
doubles, DelaunayClarkson will still have a problem when samples are closely
spaced (i.e., within 1.0 of each other). There is a method, Delaunay.scale,
designed to help with this, but it is admittedly a hack.

The DelaunayWatson algorithm should work for closely spaced samples, but
both algorithms will probably have difficulty with degenerate sets (e.g.,
colinear or colocated samples). To help address these issues, there is a
method Delaunay.perturb for randomly shaking up the points slightly.

Another thing to consider is that DelaunayClarkson works in N dimensions,
whereas DelaunayWatson is limited to 2D or 3D only, and DelaunayFast is only
2D.

HTH,
Curtis

On Fri, Dec 18, 2009 at 5:07 AM, Quike - <quikesan@xxxxxxxxx> wrote:

> Hello:
>
> Im using visad to create a Delaunay triangulation. I have two ways.
>
> *1st way:
>         try {
>             delaunay_ = Delaunay.factory(verteces_, true);
>         }
>         catch (VisADException exc) {
>             exc.printStackTrace();
>         }
>
>         assert delaunay_.test(verteces_);*
>
> 2nd way:
>
>         try {
>             delaunay_ = new DelaunayClarkson(verteces_);
>         } catch (VisADException e) {
>             e.printStackTrace();
>         }
>
> The first way uses the factory (that heuristically decides which method
> will be use), and then uses the method test. So I guess this would be quite
> expensive, but will provide an exact triangulation.
>
> My question is, if used this way, DelaunayClarkson could return a wrong
> triangulation, and if it would be faster than using the factory method (or
> at least always O(N*logN) ).
>
> Thank you very much
>
> _______________________________________________
> visad mailing list
> visad@xxxxxxxxxxxxxxxx
> For list information, to unsubscribe, visit:
> http://www.unidata.ucar.edu/mailing_lists/
>
>