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

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

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

想象一下，我有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参数在数据库必须执行任何计算之前从结果maximumSearchLongitude排除大多数点。 您可能需要也可能不需要此function。 如果您确实使用了这个，那么您可以选择为这些参数选择的值，因为它取决于您要搜索的内容。

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

使用这种方法的好处是每次都不需要改变但每次都需要的信息只计算一次，而每次执行搜索时计算每行的radiansLongitude ， sinRadiansLatitude ， cosRadiansLatitude的值会非常快速地变得非常昂贵。

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

免责声明：我看了很久以来，我不是GIS专家！

Answer 2

您可以在查询本身而不是客户端执行计算服务器端计算，从而仅检索计算结果。 这里 （后代的存档链接 ）是一个基于Haversine的SQL实现示例（对不起，这篇文章对于我来说太复杂，无法在这里复制+粘贴或总结，虽然它是一篇很棒的文章，很容易阅读）。

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

查询方法虽然更简单，更简洁，但由于初始距离过滤而具有良好的性能。 如果前者由于某种原因无法实现，我只会采用区域方法。

Answer 3

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

 @Transactional public List 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) query.list(); } 

Answer 4

我正在使用hibernate并以这种方式执行此操作：

 public List 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(); } 

查看本文以获取更多信息： Geo（proximity）使用MySQL搜索

Answer 5

你需要多准确？ 使用postgres GIS索引或r-tree索引可以作为起点。然后执行边界框查询..然后在客户端上执行径向距离..这样，FP数学不是由中央服务器完成的（窒息可扩展性）。 我的问题是GIS和rtree是最慢的索引类型（仅由FTS索引精梳）。 所以我通常选择像地理数据一样的一维索引。如果你有点数据，只需将所有内容存储在一个普通的GSD（地面采样距离）中，比如10米或1米或者你有什么……你构建一个’ string’（通常是base-64编码），它是lat-long（每个位交替lat和long）。 这些点作为简单的字符串索引存储在DB中（对于索引和存储非常有效）。 然后对于查询，你必须从你感兴趣的地理散列范围内的搜索点生成一个边界框…除非你有非常大的半径，否则这应该缩小搜索结果…在客户端进行最终过滤（或使用其他人列出的技术之一进行预先计算的三角值）。

然而，问题是通过1M点筛选很快。 进行1,000次随机磁盘访问是不可用的。 所以即使你有一个很好的地理哈希，如果它有很多随机点; 这不会起作用。

我通常做的是在磁盘上存储所有相关的数据块。 因此，地理搜索为您提供了一组有限的磁盘位置…然后在最多4个磁盘负载中加载所有数据（数十MB）。 然后筛选所有几何体。 在最好的情况下，这可以快1000倍（相比1,000磁盘兰特访问）。 但显然对您如何将数据存储到网格中的方式有​​严格的限制（完全重写或固定大小的垃圾箱）。

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

Answer 6

计划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以获得粗略的2D指数。

方案A和B是O(sqrt(N)) ; 计划C是O(1) 。 也就是说，对于计划A和B，如果您将行数增加四倍，则会将时间加倍。 随着你增加N，计划C不会变慢。

Answer 7

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

 public List 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 list = null; list = qry.list(); List idList = new ArrayList<>(); for (Object[] obj : list) { Long id = (Long) obj[0]; idList.add(id); } return idList; } 

Answer 8

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