查找与所选点的特定距离内的所有地址的最佳方法是什么

Question

我正在开发一个应用程序,它应该显示位于特定距离的地址.我知道如何找到两点之间的距离,但问题是我不确定在性能方面什么是最好的方法.

一种方法是检索所有地址并逐一检查后端的选定地址,但有没有办法最小化我从数据库中检索的项目数,而不是使用内存？最好的做法是什么？如何做？

想象一下,我有300,000条记录,我必须全部检索它们并计算它们到选定点的距离吗？正如詹姆斯建议我可以在不同地区记录并计算距离,那么哪种方法可以遵循,通过查询或Java进行距离计算？

  public class Address{
    long Id;
    Double latitude;
    Double longitude;
    ..
  }

计算

public static double distFrom(double lat1, double lng1, double lat2, double lng2) {
  double earthRadius = 3958.75;
  double dLat = Math.toRadians(lat2-lat1);
  double dLng = Math.toRadians(lng2-lng1);
  double sindLat = Math.sin(dLat / 2);
  double sindLng = Math.sin(dLng / 2);
  double a = Math.pow(sindLat, 2) + Math.pow(sindLng, 2)
        * Math.cos(Math.toRadians(lat1)) *     Math.cos(Math.toRadians(lat2));
  double c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a));
  double dist = earthRadius * c;

  return dist;
}

这个问题和这个提供了通过mysql计算距离的方法,但哪种方式更好的Java或mysql我很困惑.

Answer 1

当我在MySQL中实现它时(用于存储扁平球体上的位置,这基本上就像地球一样(我假设你在谈论地球!)),我已经在数据库中存储了尽可能多的预先计算的信息.所以,对于行,存储latitude和longitude,我也算在插入时以下字段:

• radiansLongitude(Math.toRadians(longitude))
• sinRadiansLatitude(Math.sin(Math.toRadians(latitude))
• cosRadiansLatitude(Math.cos(Math.toRadians(latitude))

然后,当我搜索在latitude/ longitude有问题的X单位内的地方时,我准备的声明如下:

from Location l where
    acos(
        sin(:latitude) * sinRadiansLatitude + 
        cos(:latitude) * cosRadiansLatitude * 
        cos(radiansLongitude - :longitude) 
        ) * YYYY < :distance
    and l.latitude>:minimumSearchLatitude
    and l.latitude<:maximumSearchLatitude 
    and l.longitude>:minimumSearchLongitude 
    and l.longitude<:maximumSearchLongitude 
    order by acos(
                sin(:latitude) * sinRadiansLatitude + 
                cos(:latitude) * cosRadiansLatitude * 
                cos(radiansLongitude - :longitude)  
        ) * YYYY asc

其中YYYY= 3965为您提供以英里为单位的距离或YYYY= 6367可用于以km为单位的距离.

最后,在数据库必须执行任何计算之前,我已使用maximumSearchLatitude/ maximumSearchLongitude/ minimumSearchLongitude/ maximumSearchLongitude参数从结果集中排除大多数点.您可能需要也可能不需要此功能.如果您确实使用了这个参数,那么您可以选择为这些参数选择的值,因为它取决于您要搜索的内容.

显然,数据库中索引的明智应用是必要的.

使用这种方法的好处是,它永远不会每一次变化,但所需要的信息只计算一次,而计算的值radiansLongitude,sinRadiansLatitude,cosRadiansLatitude为每次执行搜索时会变得非常昂贵非常快的时间每一行.

另一种选择是使用地理空间索引,这意味着所有这些都由数据库为您处理.我不知道Hibernate如何与它集成.

免责声明:我看了很久以来,我不是GIS专家!

Answer 2

您可以在查询本身而不是客户端中在服务器端进行计算，从而仅检索计算结果。这里（后人的存档链接）是一个基于 SQL 的半正矢实现的示例（抱歉，这篇文章太长了，我无法在这里复制+粘贴或总结，尽管它是一篇很棒的文章并且很容易阅读）。

或者，您可以将数据库划分为多个区域（例如带有极坐标的四叉树）并仅检索该点附近的区域，从而为您提供一个较小的子集来针对客户端进行测试。同样，您可以根据您的距离，使用纬度和经度的数据库索引来计算粗略的纬度和经度边界框，并仅选择该范围内的地址以供计算时考虑。

不过，查询方法是一种更简单、更清晰的方法，由于初始距离过滤而具有良好的性能。如果由于某种原因您无法实施前者，我只会采用区域方法。