距離之間的兩個

我想計算的距離d折線兩者之間：距離之間的兩個

很顯然，我可以檢查所有對線段的距離，選擇最小的距離，但是這算法n的運行方式將具有O（n ）。有沒有更好的方法？

2017-08-24 user2033412

這看起來像[quadtrees]（https://en.wikipedia.org/wiki/Quadtree）可能會有所幫助 - 但是除了我的頭頂之外，我沒有比這更有用的了。 – hnefatl

不知道答案，但我猜測一些基於四叉樹的算法必須是可能的，其中只計算附近元素之間的點線距離。 – jdehesa

基於邊界框的方法可能會有所幫助。計算部分多段線的邊界框（例如，A的點1 ... 4,4 ... 7和B的8 ... 10,10 ... 12）。對於每一對盒子，你可以計算最小和最大距離，並丟棄無法與最佳對成對競爭的對，遞歸地提煉盒子，直到它們都是2點（1行）盒子，你可以精確地計算。似乎是O（N logN）。 –

分而治之：

定義表示一對摺線的和最低限度的距離他們的axis-aligned minimum bounding boxes (AAMBB)之間的數據結構：pair = (poly_a, poly_b, d_ab)）
創建pair數據estructures空隊列，使用距離d_ab作爲關鍵。
使用最初的折線創建一個pair數據結構並將其推入隊列。
我們將保留目前發現的多段線之間最小距離的變量（min_d）。將其設置爲無限。
重複：從隊列
- 流行與最小距離d_ab的元素。
- 如果d_ab大於min_d我們就完成了。
- 如果任何折線poly_a或poly_b包含一個唯一段：
  - 用蠻力找到那麼之間的最小距離，並相應更新min_d。
- 否則：
  - 鴻溝既折線poly_a和半poly_b，例如：
    
    (1-7) --> { (1-4), (4-7) }
    
    (8-12) --> { (8-10), (10-12) }
  - 使兩者本身叉積TS，創建4層新pair數據結構，然後推入隊列Q.

在平均情況下，複雜度爲O（N *日誌N），最壞的情況下可能是O（ N²）。

更新：在Perl中實現的algorithm。

來源

2017-08-29 09:19:07 salva

這種問題的「標準」方式是構造幾何實體的Voronoi圖。這可以在時間O（N日誌N）中完成。

但是這種線段圖的構建很困難，您應該使用現成的解決方案，例如CGAL。

來源

2017-08-27 15:36:58

voronoi克作爲一個查找表可用於查找從任何地方最近的點，如果這些點不是將要改變，你必須從許多其他點查找最近的一個，它可能是值得的產生voronoi加快查找。但我沒有看到它如何幫助計算兩條多段線之間的距離？ – gordy

距離之間的兩個

回答

相關問題