Hi Markus,
> I encountered a peculiarity with the two Delaunay algorithms for three
> dimensions, DelaunayWatson and DelaunayClarkson. I need the
> triangulation to construct 3D Voronoi cells.
>
> Depending on which algorithm I choose, the result is different: The
> result looks fine (visuliazed with Java3D) if using the Watson
> implementation, suggesting that my own Voronoi-construction-algorithms
> might work. With the Clarkson implementation quite often two or more
> Voronoi faces do not hit at exactly one vertex as they should. Instead
> they hit "somewhere around" the actual vertex position.
>
> So before I continue to debug my source code in more detail I would
> like to ask if there is a known bug in the Clarkson algorithm.
The Clarkson algorithm calls Math.floor() on sample
coordinates, "rounding" them to integers. This probably
accounts for the difference in triangulations with the
Watson algorithm. If this is a problem, you can scale
your coordinates up by a factor (but large coordinate
values can result in overflows, as the algorithms computes
products of coordinates).
> PS: Although the Watson implemenation works fine, it sometimes happens
> that its test()-method reports an internal error. Clarkson
> doesn't. But this is another question ...
Any Delaunay algorithm will have problems with co-linear
or co-located (i.e., identical) sample points.
Good luck,
Bill
----------------------------------------------------------
Bill Hibbard, SSEC, 1225 W. Dayton St., Madison, WI 53706
hibbard@xxxxxxxxxxxxxxxxx 608-263-4427 fax: 608-263-6738
http://www.ssec.wisc.edu/~billh/vis.html
