帶方向矢量的點的最近鄰居搜索警告

Question

我有一組3D點，每個點都與方向（例如單位矢量）相關聯。給定另一個點+方向，我想找出也滿足方向向量的某個條件（例如，兩個方向向量之間的角度在一定角度量內）的集合中的最近點（使用標準2-範數）。到目前爲止，我已經在3D點上進行基於KD樹的範圍搜索，然後檢查這些點是否符合角度約束條件，但是意識到這是一種高度未優化的黑客攻擊。想知道是否有明顯的更好的方法來做到這一點。

非常感謝提前。

Answer 1

考慮使用R * - 樹。這種基於矩形的數據結構對於複雜的查詢非常適合。

I.e.如果您可以檢查一個矩形是否可以包含滿足約束條件的點，那麼可以使用R * -tree來加速此查詢。 ELKI中的索引是可擴展的，所以這可能是一個很好的起點。根據我的理解，您應該能夠將其作爲ELKI中的距離函數進行表達，如this tutorial in their wiki：如果矩形不能滿足約束條件，則返回無限距離。

Answer 2

對我而言，當前公式中的主要問題是角比較是核化的（即需要比較矢量）。如果將每個角度的方向擴展到單獨的二維矢量（cos theta，sin theta），那麼您應該能夠在該空間中進行另一個有限半徑的最近鄰居搜索（KDTree應該沒問題）兩個結果集。

Answer 3

你很早以前發佈過，但我正在研究類似的問題，並找到了一些答案，所以我會發布並希望它仍然有用。

這在文獻中被稱爲約束最近鄰搜索。 This paper在R樹上的工作方式上有一個很好的部分，即使這篇論文是關於其他東西的。

您的KD樹是一個很好的起點。本文中針對R樹的算法也適用於KD樹案例。

該論文描述了一種特殊版本的正常最近鄰搜索，如下所示。

首先建立一個深度優先的搜索，它將遍歷所有包含至少一個滿足警告的點的單元格。搜索應該從查詢點以增加mindist的順序訪問單元格。 mindist是從查詢點到單元中最近點的距離。

現在修改遍歷跳過下降到mindist大於最佳點（最接近查詢和滿足警告）的單元格到目前爲止。