如何查找距离选定点特定距离内的所有地址的最佳方法？

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，我感到很困惑。

- Jack

---

我会考虑使用处理地理信息并专为此而设计的数据库，比如PostGIS。 - Buhake Sindi

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时，表示距离以千米为单位。

最后，我使用了maximumSearchLatitude/maximumSearchLongitude/minimumSearchLongitude/maximumSearchLongitude参数，在数据库执行任何计算之前，排除了大部分点。您可以选择是否需要使用这些参数。如果使用，您可以根据搜索内容自行选择参数值。

显然，在数据库中谨慎地应用索引是必要的。

使用这种方法的好处在于，每次需要但从未更改的信息只被计算一次，而对于每个搜索，每一行计算 radiansLongitude、sinRadiansLatitude 和 cosRadiansLatitude 的值将变得非常昂贵。

另一种选择是使用地理空间索引，这意味着所有这些都由数据库处理。不过我不知道Hibernate与此整合得如何。

免责声明：我很久以前看过这个东西，但并不是GIS专家！

- Rich

Answer 2

你可以在查询中使用服务器端计算，而不是客户端，从而仅检索计算结果。 这里（存档链接供后人参考）是一个基于Haversine的SQL实现示例（抱歉，文章对我来说太长了，无法复制粘贴或摘要，虽然它是一篇很好的文章，易于阅读）。

另外，你可以将数据库分成区域（例如极坐标的四叉树），并仅检索接近该点的区域，从而获得更小的子集以在客户端测试。同样，你可以根据距离计算出大致的纬度和经度边界框，并在纬度和经度上建立数据库索引，仅选择该范围内的地址进行考虑。

尽管查询方法具有良好的性能，但由于初始距离过滤，因此区域方法是更简单、更清洁的方法。如果前者由于某些原因不能实现，我只会采用区域方法。

- Jason C

---

@Jack 很抱歉，我没有太多可以补充的。出于上述原因，SQL仍然是更好的选择，或者至少是预过滤的选择。如果你在Java端处理，你必须从数据库中检索可能包含大量数据的查询结果。如果你在SQL端处理，索引可以用来优化，并且你最小化需要查询的数据量。如果你想尝试，可以两种方法都试一下，在高负载测试条件下观察结果。通过合理的设计，你的应用架构应该允许你轻松地将一种方法替换为另一种方法进行测试。 - Jason C

Answer 3

我认为数据库方法是最好的，因为您不需要拥有大量内存。您可以使用以下代码通过Hibernate检索它们。

@Transactional
public List<Double> getAllPoisAroundUser(double longitude, double latitude, int page) {

Query query = getSessionFactory().getCurrentSession().createSQLQ uery("SELECT (6371 * 2 * ASIN(SQRT(POWER(SIN((:ulatitude - abs(latitude)) * pi()/180 / 2),2) +" +
"COS(:ulatitude * pi()/180 ) * COS(abs(latitude) * pi()/180) *" +
"POWER(SIN((:ulongitude - longitude) * pi()/180 / 2), 2))))*1000 as distance " +
"FROM poi HAVING distance < 5000 ORDER BY distance");

query.setParameter("ulongitude", longitude);
query.setParameter("ulatitude", latitude);
query.setFirstResult((page-1)*10);
query.setMaxResults(10);

return (List<Double>) query.list();
}

- Daniel Newtown

Answer 4

我正在使用Hibernate，并以以下方式执行此操作：

public List<Tour> searchTours(double lat, double lon, double distance) {

    Session session = getSession();

    Criteria criteria = session.createCriteria(Tour.class, "tour");

    //
    // 1 Grad lat = 111 km
    // 1 grad lon = cos(lat) * 111
    //
    final double KM_IN_ONE_LAT = 111.0;

    double t1 = distance / Math.abs(Math.cos(Math.toRadians(lat)) * KM_IN_ONE_LAT);
    double t2 = distance / KM_IN_ONE_LAT;

    double lonA = lon - t1;
    double lonB = lon + t1;

    double latA = lat - t2;
    double latB = lat + t2;

    Criterion c1 = Restrictions.between("longitude", lonA, lonB);
    Criterion c2 = Restrictions.between("latitude", latA, latB);

    criteria.add(c1);
    criteria.add(c2);

    criteria.setResultTransformer(Criteria.DISTINCT_ROOT_ENTITY);

    return criteria.list();
}

请查看此文档以获取更多信息：使用MySQL进行地理（接近）搜索

- dieter

---

你的解决方案很有用，但我有一些问题：

1. 我是否必须使用大约6398公里的地球半径？
2. 为什么您没有在乘法中使用69英里？
3. 您所采取的距离，是我需要找到位置之间的半径吗？

- CodeRunner

1纬度的距离为111公里。 1纬度的距离为69英里。 而69英里等于111公里。因此我们在转换中使用了这些参数。 - CodeRunner

尽管这个解决方案不能计算出完美的圆形，只能计算出一个转换为公里的正方形（仅适用于较短的距离），但它提供了一种快速高效的方式来查询给定距离内的一堆地址。使用经纬度索引将提高大量条目的速度。也许可以将其用作预计算，然后对实际圆形和距离进行更精确的计算。 - kaiser

Answer 5

计划A: 由于您有300K行，对于性能而言，INDEX(lat)是不可行的，即使限制到一个条带：AND lat BETWEEN 65 AND 69。 INDEX(lat, lng)也不好，因为优化器甚至不会使用两个列，即使有AND lng BETWEEN... 计划B: 下一个选择将涉及lat和lng，以及子查询。 版本5.6会很有帮助。 大致如下（在包括INDEX(lat, lng, id)之后）：

SELECT ... FROM (
    SELECT id FROM tbl
        WHERE lat BETWEEN... 
          AND lng BETWEEN... ) x
    JOIN tbl USING (id)
    WHERE ...;

由于各种原因，计划B只比计划A稍微好一点。

计划C：如果您需要数百万行，则需要 我的披萨店算法。这涉及使用存储过程进行重复探测，寻找足够的行。它还涉及 PARTITION 来获取粗略的二维索引。

计划A和B的时间复杂度为 O(sqrt(N))；计划C的时间复杂度为 O(1)。也就是说，对于计划A和B，如果将行数增加四倍，则所需时间将增加一倍。计划C不会随着 N 的增加而变慢。

- Rick James

Answer 6

您可以在Hibernate中使用原始查询来选择地址表中的ID列表。

public List<Long> getNearByLocations(float latitude, float longitude,
            float distance) {
        Session sess = getSession();
        String queryString = "SELECT id, (6371 * acos (cos(radians("
                + latitude
                + ")) * cos(radians(latitude)) * cos(radians(longitude) - radians("
                + longitude
                + "))  + sin(radians("
                + latitude
                + ")) * sin(radians(latitude)))) AS distance FROM Address HAVING distance < "
                + distance + " ORDER BY distance";
        Query qry = sess.createSQLQuery(queryString);

        List<Object[]> list = null;
        list = qry.list();
        List<Long> idList = new ArrayList<>();
        for (Object[] obj : list) {
            Long id = (Long) obj[0];
            idList.add(id);
        }
        return idList;
    }

- Meenakshi Mishra

Answer 7

你需要多精确呢？使用postgres GIS索引或r-tree索引作为起点可能会很有用。然后执行一个边界框查询。然后在客户端上执行径向距离。这样FP数学就不会由中央服务器（影响可扩展性）进行计算。我的问题是GIS和rtree是最慢的索引类型（仅次于FTS索引）。因此，我通常选择1D索引，如geohashes..如果您有点数据，只需将所有内容存储在常见的GSD（Ground Sample Distance）中，例如10米或1米等。构造一个“字符串”（通常是base-64编码），它是lat-long（每个比特交替使用lat和long）。这些点被存储为DB中的简单字符串索引（非常有效的索引和存储）。然后对于查询，您必须从搜索点产生一个边界框，跨越您感兴趣的geo-hashes范围...除非您有非常大的半径，否则这应该缩小搜索结果...在客户端中（或使用其他人列出的预计算三角值技术）进行最终过滤。

问题在于，快速筛选100万个点是很容易的。但进行1000次随机磁盘访问则不可行。因此，即使您拥有一个很好的地理哈希，如果它有许多随机点，则这种方法不起作用。

我通常的做法是将所有相关数据块都存储在磁盘上。因此，地理搜索会给出一组有限的磁盘位置...然后您可以通过最多4个磁盘加载来加载全部数据（多达数十MB），然后筛选所有几何图形。在最佳情况下，这可以比1,000个磁盘随机访问快1000倍。但显然，这对您如何将数据存储到网格中具有严格的限制（完全重写或固定大小的bin）。

显然，如果您有足够的RAM来缓存整个数据库，则从那里开始。算法并不那么重要。首先考虑磁盘访问模式。然后是CPU访问模式（您可以扩展CPU，但很难维护磁盘数据的副本）。

- M. Maraist

Answer 8

查询整个数据库表不是高效或可扩展的。考虑使用R-tree以获得更好的性能。

- jack