Re: failure of delauny triangulation

• To: Donna L Gresh <gresh@xxxxxxxxxx>
• Subject: Re: failure of delauny triangulation
• From: Bill Hibbard <billh@xxxxxxxxxxxxx>
• Date: Fri, 11 Apr 2003 17:14:19 -0500 (CDT)

Hi Donna,

> Thanks. It just seems strange, since I've done hundreds of sets of data
> *exactly like this*, that is, with regularly spaced points, even with
> basically the *same* points except for one or two differences here
> (literally one or two differences).

Yeah, it can be a bit maddening. If you want to dig into it,
finish_triang() isn't all that impossible to figure out. The
keys are the comments attached to the Tri, Vertices, Walk and
Edges arrays at the top of Delaunay.java. You can insert more
print statements into finish_triang() to get the indices of
the triangles where it is failing (it finds a triangle i that
thinks its next to triangle othertri, but othertri doesn't
think its next to i). Then print what's happening for triangles
i and othertri in the computation of the Walk array values.
Possible work back even further. At some point you'll probably
discover that the Watson algorithm has left an empty hole in
its triangle mesh, or overlapping triangles, or something like
that.

Good luck,
Bill

• References:
  • Re: failure of delauny triangulation
    • From: Donna L Gresh