Hi Lezlie,
To give you some more background on Delaunay: it is actually not a
single algorithm, but a term used to describe the optimal triangulation
structure for a collection of points. VisAD includes three algorithms
for generating Delaunay triangulations: DelaunayClarkson, originally
written by Ken Clarkson in C as part of a program called hull;
DelaunayWatson, originally written by Dave Watson in C as part of a
program called nnsort; and DelaunayFast, written by me, which does not
compute a true Delaunay triangulation, but rather an approximation using
a divide and conquer scheme.
DelaunayClarkson operates in O(n log n) time on samples in N dimensions,
but has a high overhead cost. DelaunayWatson operates in O(n^2) on
samples in 2 or 3 dimensions, with a low overhead cost. DelaunayFast
operates on samples in 2-D only. On my machine, DelaunayWatson is faster
than DelaunayClarkson for ~3700 samples or less due to
DelaunayClarkson's high overhead. The static Delaunay.factory method
takes this into account in its heuristic, using DelaunayWatson for
samples <= 3000, DelaunayClarkson for 3000 < samples <= 10000, and
DelaunayFast for samples > 10000 (if the dimension is 2 and an exact
triangulation is not required).
Actually, there is another Delaunay approximation algorithm for 2D data
of a very specialized organization (overlapping grids) that I wrote
called DelaunayOverlap, but to my knowledge it is not being used for
anything.
You can try out the various Delaunay algorithms using the DelaunayTest
class in the visad/examples directory. Run "java DelaunayTest" for a
list of options.
I also second what Bill said about using DelaunayCustom. If you have any
geometric knowledge of your samples' structure, it is often possible to
compute your own triangulation more quickly or accurately than the
included Delaunay algorithms could. If the triangulation you create is
not perfect, you can even improve it by calling the Delaunay.improve
method to perform a number of improvement passes (a greedy algorithm
that performs edge flips to bring the triangulation closer to the
optimal one).
Lastly, again along the lines of what Bill said, if your samples
actually lie in a grid structure, even if the grid is twisted or uneven,
as long as each grid box is convex, you can use a GriddedSet instead of
an IrregularSet to greatly improve your performance.
-Curtis
Lezlie Fort wrote:
Hi Bill,
Thanks so much for your reply. I should preface my response by
indicating my hope that you saw the second addendum message that I
sent out. The number in my initial mail (380) referred to a single
"group" of Depth parameters. There were 20 such groups in my data
set, so the true number of points was 7600. But even that number is
small compared to the 42000 that you mentioned in your first reply! I
think that you nailed my problem, though, in your p.s. I am using the
TextAdapter to read in my data files, and I looked at TextAdapter.java
to see what was going on. Sure enough, based on my defined math type,
it is creating an Irregular set using the Delaunay algorithm. I did
some brief research online and found out that performance of Delaunay
can be as high as O(n^2), so that helped me to understand what was
happening. I read one post where someone was plotting over 100,000
points using the algorithm, and had to wait for over 8 hours for the
calculations to complete. I read about other algorithms out there,
but Delaunay seems to be one that is prevalent. I feel better just
having an explanation for what I am seeing. If I have time, I might
do a little more research into the Delaunay algorithm. One post
suggested that a way to reduce performance time is to pre-sort one of
the vectors involved in the calculations (the vector that is
associated with the most dramatic changes in data values). They
indicated that such a step could result in a performance savings of
25%. But, like I said, this is just cursory research.
At any rate, I have been very pleased with VisAD, and this is really
the only issue that I've run into (although I've had a few questions
along the way, as my recent posts will attest ;). And it's not really
an issue, in the long run. For large data sets I can always plot 3D
line graphs, which are extremely quick.
Thanks again!
lzf
