針對二維幾何數據的高效近接查詢

Question

我在二維空間中有一組數據點D.我有一個查詢點P（在二維空間中）。我正在尋找一種能夠回答查詢的有效（優於線性時間）算法：找到D中與D最接近的幾何距離的數據點d。

有關如何執行此操作的任何指針？

謝謝

Answer 1

我在scipy中發現了一個k-d樹的實現，它實現了我想要的功能。注意：K-d樹不會給你最壞的情況O（log（n））性能，但它確實給你提供了平均情況O（log（n））的性能。請參閱：

https://docs.scipy.org/doc/scipy-0.14.0/reference/generated/scipy.spatial.KDTree.html

Answer 2

你可以使用基於一個K-D Tree的方法。