Getting the true convex hull with Bowyer-Watson algorithm
No replies to this topic
Members - Reputation: 101
Posted 09 April 2012 - 02:30 PM
I'm trying to make a visualization module for Bezier and NURBS surfaces. I figured I'd start with a simple 2D Delaunay triangulation to understand how to divide up the surfaces. I made an implementation of the Bowyer-Watson incremental algorithm and started with a "super triangle" at (3M,0) (0,3M) (-3M,3M), where M is the largest value in X or Y in the set of points. It seems I did the algorithm right because I get a similar triangulation as the Delaunay() function in MATLAB, except I don't get the true convex hull. I've researched for a while and it seems that the "super triangle" method can produce this sort of problem, but I don't know of a good alternative. I tried using the Graham scan algorithm to get the convex hull and somehow combine the two, but I can't figure out how. If anyone is familiar with this problem, please let me know.
"Hofstadter's Law: It always takes longer than you expect, even when you take into account Hofstadter's Law."
—-- Douglas Hofstadter, Gödel, Escher, Bach: An Eternal Golden Braid