查找四叉樹中最近的相鄰邊緣

Question

我在四叉樹中存儲了一組點。一旦用這些點創建了四叉樹，然後我將所有的邊添加到四叉樹中，這樣每條邊都被存儲在它所穿過的所有葉節點中，開始或結束於。

現在，我有一個觀點，說A，我需要找到最接近它的邊緣。在我當前的算法中，我遞歸到包含此A點的葉節點，並找出A與此葉節點包含的所有線段之間的距離。 現在這看起來像是正確的解決方案，但它不是我必須比較相鄰節點中存在的邊緣以及能夠給出準確答案。

現在我的問題是

一）我如何去提取最接近的邊緣？

b）我應該比較包含在父節點（到感興趣點）節點的所有邊嗎？ （但我知道一個事實，即把一個硬限制上等級的數量必須上去尋找最近的邊緣是不正確基於直覺）

Answer 1

你可以嘗試Voronoi圖，查找邊緣僅在voronoi單元內。

Answer 2

四叉樹上的每個節點表示空間中的立方體（其中一些邊可能無限），並且可以計算該立方體與目標點A之間的最小距離。請注意，包含多維數據集的立方體的距離爲0 A.

從根節點開始，您必須計算每個子立方體（節點）到A的距離並將其插入最小堆中。

迭代地，您可以在堆頂部獲得最近的立方體並重復該過程。當你到達一個葉子節點時，你只需用蠻力在它內部搜索最近的A到A的邊緣。

一旦堆頂部立方體的距離大於迄今爲止找到的最近邊的距離，就可以停止搜索。

更新：順便說一句，這實際上是搜索任何使用四叉樹或kd樹或可能是大多數空間結構的一般方法。