用於完成部分三角測量的算法（約束三角測量）

Question

給定一組平面中的一組點和一個不完整的triangulation of the convex hull of the points（只給出一些邊），我正在尋找一種算法來完成三角測量（初始給定邊應該保持不變）。您可以假設可以完成部分三角測量，但如果您也可以建議一種用於檢查的算法，那就太好了。

UPDATE「你給出了一組點R^2的凸包，它基本上是一個多邊形，裏面有一些點，我們想要對點集進行三角化，這本身就是一個直接的問題，但你也有一些邊緣，你想出的任何三角形都應該使用這些邊緣。「

Answer 1

也許這是一個天真的答案，但你不能只用一個約束Delaunay三角？將已知邊添加爲約束。

CGAL有nice implementation。工具triangle具有相似的功能，並且更容易入門，但具有（可能）更少的靈活性。

Answer 2

我發現這本書「計算幾何：介紹」有主題的詳細處理，雖然它不給一個準備執行僞代碼。

最簡單的算法是一個貪婪其中一個枚舉所有可能的邊緣，然後由一個避免與先前添加的年齡交點添加它們之一。關於如何將運行時間減少到O（n^2 log n），本書有很長的討論。

然後有一個爲O（n log n）的算法，該算法首先規則化與給定的邊緣凸包，然後分別進行三角測量每個單調多邊形。