使用單調多邊形的多邊形三角網

我有一個沒有孔的簡單多邊形，它需要被三角化爲用於物理引擎的凸多邊形，並且還可以使用這些凸多邊形通過三角形條進行渲染。使用單調多邊形的多邊形三角網

This百科文章顯示瞭如何使用單調多邊形來對多邊形進行三角測量。它提供了它如何工作的簡短描述，但沒有足夠的細節讓我理解。這種方法似乎對我所需要的完美，而它鏈接到的Flash Demo顯示該算法完全符合我的需求。

我一直在尋找谷歌尋找更好的解釋算法，我只能找到庫或源代碼做三角測量。我寧願學習它是如何工作的，並編寫我自己的方法，但如果我需要使用預先編寫的庫，它將不得不這樣做。

任何人都可以提供一個解釋，或資源如何我可以瞭解這種類型的三角測量工作？

2012-02-07 Brad

是否有編程語言的要求？（請標記是否存在）是否有硬件限制 - cpu/gpu允許？ – mfa 2012-02-07 02:35:33

的CGAL庫提供簡單多邊形的凸分解的幾種實現無孔。看看這個chapter

2012-02-07 07:15:58 sloriot

我建議你看看Delaunay三角剖分：Wikipedia。 QHull是標準實現。（作爲一個參考點，MATLAB依靠Qhull：link

如果Qhull是不是你的東西，嘗試這個collection

2012-02-07 05:59:57 Throwback1986

舊帖子，但無論如何。值得指出的是， Delaunay三角測量用於一組點，而不是多邊形 - 這只是一個輪廓 – Croolman 2017-05-09 22:38:56

回答