三角測量一個巨大的點的集合

Question

當三角一組點和點的數量巨大（1000萬），你需要使用一個四叉樹或辛樹細分的問題後三角在一次一個數據塊。

到目前爲止，我們現在正在尋找一種聰明的方法來填補每個網格之間的小直縫隙。你知道一個好的嗎？

謝謝。

Answer 1

而不是由網格的單獨的部件焊接在一起光潔度，爲什麼不通過分解設置成重疊的塊的點開始？這樣，您的問題就變成了去除不需要的邊緣而不是找到缺少邊緣的問題，代價是重複沿邊界計算網格。儘管我懷疑它的計算複雜性沒有什麼不同，但這可能會更容易些。

我認爲，最標準的方法來三角測量，不能期望產生跨邊界的同一網格的兩個重疊的塊。然而，我也相信（沒有證據）跨越邊界（鄰近的內部）塊之間的邊界的網格的計算越來越可能在重疊的深度增加時越過邊界產生相同的三角形。

一組點的現有三角的思考，並添加現有點的船體之外的新點。在大多數情況下，對擴展的一組點進行三角測量將只需要局部（在一些模糊的意義上）調整現有網格。類似地，刪除現有網格邊緣處的點將很少影響網格中心的三角測量。

如果特設方法並不能吸引你，用你喜歡的搜索引擎查找平行德勞內三角

Answer 2

如果使用線性元素（直線邊）連接網格，則只有在相鄰邊上的端點不重合時纔可以有間隙。

您可以容忍一些球兩個點是否應作出一個內部檢查，但公差必須比你的網格最短邊小，否則你會崩潰的元素。

我能想到的最聰明的事情就是將工作並行化。將網格分成每個線程/進程的一個塊，並對每個進行容差檢查。

這可能是一個很好的map-reduce工作。或者，GPU和CUDA可能是一個很好的選擇。

當你計算出兩點之間的距離，你可以放棄昂貴的平方根，只是看距離的平方比公差。