如何讓三角形網格成凸多邊形？

Question

我有一個三角形的網格。三角形有不同的「顏色」。就像這樣：

我需要得到的是優化的網格，其中過度的三角形被合併成一個凸多邊形。就像這樣：

有人能給我一些算法鏈接到acomplish是什麼？提前致謝！

P.S.我正在使用C＃。

Answer 1

我沒有任何指向算法的鏈接來解決這個問題，但我認爲比一次構建三角形凸多邊形更好的方法可能是首先將三角形合併爲最大的簡單多邊形（即：它們可以是凹面的，但沒有孔），然後將這些大的多邊形分割成它們的凸面成分。

由於內角大於180度，您知道這些分割將出現在哪些頂點，那麼您只需選擇沿其分割的入射邊緣。選擇最佳邊緣分割的精確方法不是一個簡單的問題，但合理的啓發式可能是最大化分割後180度內角的數目。

Answer 2

Hertel-Mehlhorn算法是這樣做的標準方法;它可以概括爲：

1. 以多邊形P的三角剖分開始;
2. 刪除無關對角線
3. 重複。

（從http://www.philvaz.com/compgeom/）

此作品在多項式時間，並且對最優一個界限，雖然它不一定是最優化的。

就你而言，你可以通過不考慮不同顏色的三角形之間的對角線來修改第2步。

通常會產生「看起來更好看」的一種啓發式方法是在每一步合併最長的對角線。

希望有所幫助。