NOTICE: This version of the NSF Unidata web site (archive.unidata.ucar.edu) is no longer being updated.
Current content can be found at unidata.ucar.edu.
To learn about what's going on, see About the Archive Site.
NOTICE: This version of the NSF Unidata web site (archive.unidata.ucar.edu) is no longer being updated.
Current content can be found at unidata.ucar.edu.
To learn about what's going on, see About the Archive Site.
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
visad archives: