檢查所有線段的指定距離內的所有點

Question

給定一組點P和一組線段S，是否有一種方法可以有效查找任何段的指定距離d內的所有點？沒有蠻力比較的命令O(|P||S|)？

Bentley-Ottman搜索一組線段之間的所有交點在O(n log n)中運行，並且由於此問題具有類似的風味，我不知道相似的性能是否可能。

C++中寬鬆開源實現的獎勵積分。

Answer 1

在點上構建Voronoi diagram網絡。讓每個單元格保持指向其所有鄰居的指針。比任何事情都可能。

1. 給出一個點，發現這是哪個小區。簡單，借鑑網絡的左下角的點線，並從那個角落細胞開始，接近點，從而找到電池它

2. 給出一條線，找到它所穿過的所有單元。不重要的。

3. 給定一條直線和一條偏移距離，找到走廊內的所有單元。如下從2.

4. 等

維諾網絡用作支撐結構，用於空間導航和查詢。所有的操作都是本地的，所以線性複雜。 之後圖構建完畢。 :)