Jump to content
  • Advertisement
Sign in to follow this  
mike74

delaunay triangulation of square

This topic is 4835 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

What is the Delaunay triangulation of the four endpoints of a square? Obviously, it is two triangles, but the question is, which two? Which diagonal should you use to split the square? How do you decide? The two diagonals both seem equally viable. mike http://www.coolgroups.com/forum

Share this post


Link to post
Share on other sites
Advertisement
I don't think there is any 'generally correct' choice, but I'd choose which ever matches the winding order of the API I was going to render with. That may or may not be an issue in your case.

Share this post


Link to post
Share on other sites
The winding order of a polygon (triangle) is the order in which its vertices must be read. If this is defined one can use it to determine front and back of the triangle a.o. for culling it.

There is indeed no best choice -- all delaunay triangulation specifies is a criterion on the smallest angle in the result. Which way the square is divided produces the same results in these terms. Note also that it is perfectly legal for a problem to have multiple optimal solutions; there can be multiple solutions with the same cost.

Greetz,

Illco

Share this post


Link to post
Share on other sites
For a true square, e.g., a planar 4 vertex polygon with equal-length and perpendicular edges, either diagonal will give you an equivalently good result.

In actuality, a true square cannot be triangulated in the Delaunay sense, since regardless of which triangle you choose, the 4th vertex will be on the border of both circumcircles (not actually inside), while a true Delaunay triangulation has no vertices remaining inside circumcircles. A minor, unavoidable technicality, :).

Share this post


Link to post
Share on other sites
I would say that they are both Delaunay triangulations. Wikipedia seems to agree with me:

Quote:
[...]for 4 points on the same circle (e.g., the vertices of a rectangle) the Delaunay triangulation is not unique: clearly, the two possible triangulations that split the quadrangle into two triangles satisfy the Delaunay condition.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!