Re: On the nature of irregular sets

• To: Ugo Taddei <taddei@xxxxxxxxxx>
• Subject: Re: On the nature of irregular sets
• From: Bill Hibbard <billh@xxxxxxxxxxxxx>
• Date: Tue, 23 Nov 2004 06:34:28 -0600 (CST)

Hi Ugo,

Nice to hear from you.

For your Exceptions in DelaunayWatson and DelaunayFast,
all anyone could do would be to run under jdb or another
debugger and try to track down what is going on. I don't
have any specific idea about these, and doubt anyone else
does either. Probably best to stick with DelaunayClarkson.

Thanks for the image for your 'curtain-like artefacts'. You
are correct that they occur because the outline of your 2-D
Set of points is concave, not convex, but the Delaunay
algorithm fills in long thin edge triangles to make it convex.

The only thing I can think of is an ad hoc algorithm to detect
and remove triangles on the edge (i.e., with an edge not shared
with another triangle: look for -1 values in the Delaunay.Walk
array, I think) and such that that outer, unshared edge, is
very long compared with the triangle's shortest edge.

Such an algorithm would be generally useful, so if you wanted
to contribute it back as a (static?) method of Delaunay.java
that would be great. But I understand that you are in business
and may want to keep it proprietary.

Cheers,
Bill

On Tue, 23 Nov 2004, Ugo Taddei wrote:

> Hi,
>
> I couldn't put the accompanying image on our server yesterday; I'm
> attaching it (and hoping this is allowed in this list!).
>
> One sees on the left the "curtains" I mentioned. These are planes which
> are very close together and on the edge of the dataset. Intersting is
> really one one rotates the image, the planes sort of flicker.
>
> On the right it's the same effect. This is not really a bug, I know (or
> think); but it's created when the algorithm joins exterior points
> (points on the boundary of the dataset), and which are concave. Is there
> a way to avoid that?
>
> Cheers,
>
> Ugo
>
> Ugo Taddei wrote:
>
> > Hello everyone!
> >
> > We're trying to use the visad Delaunay classes to triangulate some
> > elevation data on-the-fly. I'm quite happy about the performance (at
> > least on my machine ;-) but I've run into a few of problems and would
> > like to clear the matter before carying on with development.
> >
> > First, only DelaunayClarkson seems to work OK with my data.
> > DelaunayWatson and DelaunayFast throw
> > "java.lang.ArrayIndexOutOfBoundsException: 23320; at
> > visad.DelaunayWatson.<init>(DelaunayWatson.java:190)
> > and "visad.SetException: Delaunay.finish_triang: error in triangulation!
> >    at visad.Delaunay.finish_triang(Delaunay.java:592)
> >    at visad.DelaunayFast.<init>(DelaunayFast.java:581)", respectively
> >
> > Any ideas?
> >
> > For this dataset we've 11560 points.
> >
> > I've already tried the common hack for the irregular 2d sets
> > (multiplying values by 1000 to spread them apart)...
> >
> > The second problem concerns triangles on the edgdes of the dataset.
> > Points very close together and on the edge are creating curtain-like
> > artefacts. Is there a way to avoid that?
> >
> > Thanks for the help!
> >
> > Cheers,
> >
> > Ugo
> >
>
> --
> l a t / l o n  GmbH
> Meckenheimer Allee 176                53115 Bonn, Germany
> phone ++49 +228 732838                fax ++49 +228 732153
> http://www.lat-lon.de         http://www.deegree.org
>
>

• Follow-Ups:
  • Re: On the nature of irregular sets
    • From: Ugo Taddei

• References:
  • Re: On the nature of irregular sets
    • From: Ugo Taddei