# delaunay triangulation of square

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

## 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 on other sites
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 on other sites
What do you mean by winding order?

mike
http://www.coolgroups.com/forum

##### 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 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 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.

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 11
• 12
• 10
• 11
• 13
• ### Forum Statistics

• Total Topics
634096
• Total Posts
3015480
×