查找给定坐标的最近点 - 数据结构

Question

什么是保存2d点集合的好数据结构，以便稍后可以有效地调用像collection.pointsCloserThanDistance（float d，float []坐标）这样的方法？ - 此方法将返回一个列表，其中每个点与给定坐标的距离小于或等于d。

（又怎么会是方法的实现？）

最简单的，也许不那么好解决方案将是一个标准的数组，然后比较指定的坐标。这是O（n）的每一个点，n =点数。但是可能有O（m），m =与给定坐标的距离小于或等于给定值的点数。

Answer 1

您需要一个“空间分区”数据结构，如k-d tree。