java - 使用代码查找距离范围内的点(在数据库中存储一组纬度/经度)

Question

我确实有一个相对较大的应用程序，其中包含 POI 数据库(在本例中，这意味着有两组，一组包含大约 40k 点，另一组包含大约 400k 点)。

这是一个 Web 应用程序，您可以在其中查看给定点的详细信息并查看周围的其他点(假设在 25 公里范围内)。

到目前为止，我已经使用 MS SQL 存储过程解决了这个问题。它有两个参数，以浮点形式给出的纬度和经度，并返回最近的点(纬度/经度也以浮点形式存储，而不是 MSSQL DB 中的地理类型)。

不过我想避免使用存储过程。感觉业务逻辑应该保留在代码中(至少是大部分)。

现在，当我更新项目时(很可能最终会从 ASP WebForms 过渡到 Spring MVC)，我想停止使用我的存储过程。

有没有什么好/简单的方法，而且不会太过分呢？

我能想到的唯一的事情(基于代码)是从数据库中检索所有点并通过集合进行简单迭代，计算给定点与集合中当前点之间的距离。

类似的东西

Point givenPoint = new Point(lat,lng);
List<Point> allPoints = repo.findAll();
List<Point> pointsInRange = new List<Point>();
for(Point p : allPoints){
    if(givenPoint.distanceTo(p) < 25)
         pointsInRange.add(p);
}

不过看起来有点矫枉过正。

Answer 1

参见Fast algorithm to find the x closest points to a given point on a plane其中讨论了一些选项，包括我对 KD 树作为合适的数据结构的暗示。

此外，这可能会给您一些其他选项:Finding nearest point in an efficient way

这是对更广泛主题的有用讨论:http://en.wikipedia.org/wiki/Nearest_neighbor_search