使用約束delaunay三角剖分三角剖分多邊形

Question

我有一個約束delaunay三角剖分（CDT）算法，我有一個多邊形（它可以是凹面或凸面）作爲輸入。如何使用約束Delaunay三角剖分算法將多邊形分解爲三角形而不引入新點？

編輯：所有三角形的聯合必須等於多邊形。因此，不能僅將CDT和邊界作爲約束邊緣來生成三角形，因爲無論輸入是凹面還是凸面，這都會產生凸多邊形。

Answer 1

，因爲你有一個多邊形，而不是一個點雲將很天真三角然後訪問每個邊和測試，看它是否是使用簡單的線條，多邊形相交測試原多邊形之外的最簡單方法。

根據您的算法，你可以做這個測試的三角形細分的一部分，跳過在最後的傳球。我確信有一個更好的方法，但這是第一個想到的。

編輯：

我實現了這個在我的三角儀，它給了錯誤的結果，因爲我沒有實現的約束。如果你確保使用了所有的多邊形邊緣，那麼我相信它應該可以工作。