Jump to content

  • Log In with Google      Sign In   
  • Create Account

We're offering banner ads on our site from just $5!

1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.


Don't forget to read Tuesday's email newsletter for your chance to win a free copy of Construct 2!


Getting the true convex hull with Bowyer-Watson algorithm


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

Like
0Likes
Like

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:



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.



PARTNERS