構造一個多邊形的輪廓（特別是三角形）

Question

我該如何去構造二維多邊形的輪廓，它只由三角形構成，它可以有孔，外部輪廓可以是凹凸的，並且孔可以也是凹面/凸面。

從什麼I'm reading over here看來，它恰好是三角測量問題的反面。 你是否知道處理這類問題的任何文章？

八叉樹/四叉樹是否與此相關？

Answer 1

我想你有三組數據，它們構成一個「填充」三角形，這些三角形沿着邊連接，並且所有將是完整形狀的角的頂點也是頂點觸及這一點的所有三角形。那麼你只需要找到所有不加倍的邊，即不屬於兩個相鄰的三角形。

Answer 2

我認爲你可以通過創建一個拓撲數據結構來表示你的三角形集合，然後使用該結構在位於邊界上的三角形邊緣上依次迭代來解決你的問題。

例如：你可以創建一個halfedge數據結構。假設你在邊界上（正確地）插入半邊，遍歷邊界輪廓就像在邊界上定位一個半邊，然後迭代它的「下一個」指針一樣簡單，直到你回到你開始的半邊。

類似於halfedges，你可以使用其他拓撲結構，如翼邊等，但概念是相同的。