Getting the true convex hull with Bowyer-Watson algorithm

Started by timthereaper, Apr 09 2012 02:30 PM

Convex hull Delaunay triangulation Bowyer-Watson incremental

Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

You cannot reply to this topic

No replies to this topic

#1 timthereaper Members - Reputation: 101

0Likes

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

Sponsor:

Back to Graphics Programming and Theory

Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.