查找給定座標的最近點 - 數據結構

Question

什麼是保存2d點集合的好數據結構，以便稍後可以有效地調用像collection.pointsCloserThanDistance（float d，float []座標）這樣的方法？ - 此方法將返回一個列表，其中每個點與給定座標的距離小於或等於d。

（又怎麼會是方法的實現？）

最簡單的，也許不那麼好解決方案將是一個標準的數組，然後比較指定的座標。這是O（n）的每一個點，n =點數。但是可能有O（m），m =與給定座標的距離小於或等於給定值的點數。

Answer 1

您需要一個「空間分區」數據結構，如k-d tree。