Unfortunately, neither DelaunayWatson nor DelaunayClarkson are 100%
robust. I'm sorry to hear about your problems. Most problems are due to
colocated or colinear points, or closely clumped values if using
DelaunayClarkson. To avoid closely clumped values, the Delaunay.scale
method is provided to scale up the data. To avoid colocated and colinear
points, the Delaunay.perturb method is provided to randomly perturb data
points by a small value (hopefully small enough to avoid altering the
It has been several years since I worked on the Delaunay algorithms, and
since I ported them from C, I did not need to fully understand them. I
know that MAXDIM in DelaunayClarkson provides an upper bound on the
dimensionality the algorithm can handle. Since you are working with data
of no more than three dimensions, changing yours to MAXDIM=4 should not
pose a problem for you. However, both of your problems (DelaunayWatson
throwing an ArrayIndexOutOfBoundsException and DelaunayClarkson
depending on the version of MAXDIM) are certainly not the intended behavior.
If you can send me any sample datasets with some code to duplicate the
problems (perhaps one for DelaunayWatson and one for DelaunayClarkson),
I would be willing to investigate further. I would like DelaunayWatson
and DelaunayClarkson to be as robust as possible.
Lezlie Fort wrote:
I apologize for the second mailing, but I wanted to let you know that
I believe I was able to find the cause (sort of) of the "data
flattening" problem that I described in my last e-mail. Given the
fact that the only difference between my working graphs and the
failing graph was the amount of data (as opposed to the data itself,
since identical data was being rendered differently), I began to
suspect that some of the initial variable settings in the first part
of DelaunayClarkson.java might be contributing to the problem. After
tweaking some of them, I noticed that when I changed the "MAXDIM"
value from 8 to 9, the graph that had previously rendered correctly
now failed with the same "flattening" behaviour I had noticed before.
Suspicious, I lowered the value from 9 to 7 and re-ran the
application. Now, both of the graphs rendered correctly.
Additionally, the graph that had previously been failing (it had taken
about 22 seconds to render) now rendered successfully in 16 seconds.
As a stopgap for now, I have altered my version of
DelaynayClarkson.java to set MAXDIM to 4. This is the only change
that I have made, and so far all of my data seems to be rendering
correctly (I received some additional data today, and that rendered
successfully, as well). I've examined the code, but not being overly
familiar with triangulation algorithms, I am unable to get a complete
handle on the (seemingly) multipurpose function of the MAXDIM value.
Am I endangering the sanity of my application by altering the value as
I have? Is there an explanation for why a simple change in this
variable can have such drastic effects on the generated graph output?
Thanks very much,
Lezlie Fort wrote:
I have run across a few questions this weekend that have me banging
my head against the wall. I'm hoping that you might be able to
address some of them.
To provide some background: The application that I am writing is
designed to graph data that falls within a user-specified time
range. Every day, I have received a new batch of data, and have
generated both 3D spacial graphs and 3D line graphs. All has been
well. However, over the weekend, I received another batch of data,
and I plugged it into the app as usual. This particular batch was
larger than the others (obviously, since everything is cumulative).
The generated 3D spacial graph was nothing like those that I had seen
on the previous days. Most of the surfaces were flattened out - with
absolutely no variation. Initially, I presumed that the problem was
caused by the fact that I had probably crossed the Delaunay
Watson/Clarkson boundary that you described in your previous post.
After all, before the problem, my total data set was < 3000. After
the problem, it was >3000. When I started delving into the
situation, however, I discovered that I have /never/ been using
DelaunayWatson at all (even for the <3000 cases). When
DelaunayWatson was called, an error was always generated, and the
DelaunayFactory method fell back to using DelaunayClarkson. The
error has always been silent, so I never realized that it was
occurring until I started debugging the code and stepping through
it. My first approach was to figure out why the error was generated
during DelaunayWatson execution. The problem always seemed to be due
to an "array out of bounds" exception that occurred during the
portion of the code that builds the triangle vertices and
components. However, the data set was exactly the same as that used
"successfully" by Clarkson. It basically consists of a sample of
type float, where the first dimension is the number of domain
dimensions (in my case, 2), and the second is the length of each
domain vector. This seemed correct to me, so I was (and am still)
unable to determine why the DelaunayWatson routine fails consistently.
So my next thought was to somehow adjust the Clarkson algorithm so
that it doesn't round to the nearest integer. This was the only
explanation I could think of for the sudden "flat" surfaces generated
with my most recent plot. But that explanation still doesn't account
for the fact that I am building on the same data day by day. On
previous days, the same data that appears flat on the final day's
graph was nicely varied. Why, then, would it suddenly flatten out
when the data points have not changed? I know I must be missing
something quite obvious, but it continues to elude me.
Do you have any ideas on any of these problems?
1. Why would DelaunayWatson fail on a sample type described above?
2. Why would Clarkson suddenly decide to flatten out data that was
previously nicely varied?
3. Since I can't seem to use DelaunayWatson successfully, is there
a change I can make to DelaunayClarkson.java to prevent the
problem described in (2), above?
Any help that you could provide would be very much appreciated.
Until this weekend, things have been going quite well, but I find
that I've suddenly crashed into a brick wall. At this point, I don't
trust the output of DelaunayClarkson enough to use it at all for 3D
surface graph generation, but I am unable to successfully generate a
surface graph any other way.
Thanks for any assistance,