隨機生成約束條件以生成約束Delaunay三角剖分

Question

我已經實施了Domiter和Zalik使用的掃描線方法來爲Java中的二維空間中的一組點創建約束Delaunay三角剖分。我想確保我開發的代碼真正適用於n隨機生成的點和其中約束邊的k。

現在使用通用的策略，我想請從組n頂點的隨機點，然後選擇第二個隨機點，並有因爲我從一個約束德勞的定義理解它們之間的邊緣可能無法正常工作三角剖分是約束邊是平面直線圖的邊。因此它們不相交。如果隨機選擇點，則可能必須執行檢查以確定它們不會產生相交約束。這種方法可能效率不高。

因此，我想知道是否有人知道隨機生成約束的有效策略。

在此先感謝。

Answer 1

你可以嘗試兩個階段：

• 產生一個小的組隨機點，構建一個非約束Delaunay三角。然後，您可以從這個小三角形的邊緣內隨機選擇，形成一組約束邊。顯然，由於邊緣來自三角測量，所以它們將不相交。

• 向數據集添加一組附加的隨機點並構造全集的約束Delaunay三角剖分，強加先前找到的約束邊。

雖然我相信這個方法是建立一個不相交，隨機約束數據三角碼設置，更好的方法可能是使用真實數據來測試一種有效的方式。

Triangle包裝包括幾個基準幾何形狀，在這方面可能很有用。

希望這會有所幫助。