由於約束Delaunay三角剖分而識別出多邊形三角剖分

Question

我有一組多邊形，它們可以共享公共邊和節點。所有這些多邊形都是嚴格不重疊的，儘管它們可以共享一個共同的頂點或邊。

我想對所有這些多邊形進行批量三角測量，因此，我能想到的解決方案是約束Delaunay三角測量。但約束Delaunay Triangulation的輸出將生成不在原始多邊形中的三角形。

有沒有一種方法來識別這些超出多邊形的三角形？

編輯：Matlab has a way to do it via the inOutStatus;我正在尋找一種獨立於語言的算法。

Answer 1

許多Delaunay三角測量包（例如Triangle，我會推薦）通常包括從三角測量中自動去除「外」三角形的選項。查看文檔。

如果您的算法不是這種情況，您應該能夠通過測試每個三角形的質心是否位於您指定爲約束的多邊形內，通過點來刪除外三角形例如，在多邊形測試中。這應該始終有效，因爲受約束的Delaunay三角剖分將確保沒有三角形邊緣穿過多邊形約束邊緣（沒有部分進/出三角形的機會）。

您的問題的另一個考慮因素是您描述的批處理。大多數（如果不是全部的話）Delaunay三角測量算法的複雜性是非線性的（Triangle達到了O(n*log(n))），所以我認爲通過一次處理多邊形而不是一次處理多邊形實際上可以實現加速。