algorithm查找距给定Lat Lng位置一定距离内的所有纬度经度位置
给定纬度+经度位置的数据库，例如40.8120390，-73.4889650，我将如何find特定位置给定距离内的所有位置？
从数据库中select所有的位置，然后逐个地通过它们，从起始位置开始，看看它们是否在指定的距离内，似乎效率不高。 有没有一种很好的方法来缩小数据库中最初select的位置？ 一旦我有了（或者没有？）一个缩小的位置，我还是一个接一个地检查距离，还是有更好的办法？
我这样做的语言并不重要。 谢谢！
首先比较纬度之间的距离。 每个纬度的距离大约是69英里（111公里）。 由赤道68.703英里（110.567公里）到极点69.407（111.699公里），范围变化（由于地球略椭球形状）。 两个地点之间的距离将等于或大于纬度之间的距离。
请注意，这不是经度 – 每个经度的长度取决于纬度。 但是，如果你的数据是有限的（例如，一个国家），你也可以计算经度的最小和最大范围。
继续将假定球形地球的低精度，快速距离计算：
坐标{lat1，lon1}和{lat2，lon2}两点之间的大圆距d由下式给出：
d = acos(sin(lat1)*sin(lat2)+cos(lat1)*cos(lat2)*cos(lon1-lon2)) 一个math上等价的公式，在短距离上较小的舍入误差是：
d = 2*asin(sqrt((sin((lat1-lat2)/2))^2 + cos(lat1)*cos(lat2)*(sin((lon1-lon2)/2))^2))
d是以弧度表示的距离
distance_km ≈ radius_km * distance_radians ≈ 6371 * d
（6371公里是地球的平均半径 ）
这种方法的计算要求是最小的。 但是，对于小距离，结果是非常准确的。
那么，如果它是在一个给定的距离，或多或less，使用更准确的方法。
GeographicLib是我所知道的最准确的实现，尽pipe也可以使用Vincenty的逆公式 。
如果您正在使用RDBMS，请将纬度设置为主键，将经度设置为辅助键。 如上所述查询纬度范围或纬度/经度范围，然后计算结果集的精确距离。
请注意，所有主要RDBMS的现代版本都支持原生地理数据types和查询。
基于当前用户的纬度，经度和距离你想find，SQL查询如下。
SELECT * FROM( SELECT *,(((acos(sin((@latitude*pi()/180)) * sin((Latitude*pi()/180))+cos((@latitude*pi()/180)) * cos((Latitude*pi()/180)) * cos(((@longitude - Longitude)*pi()/180))))*180/pi())*60*1.1515*1.609344) as distance FROM Distances) t WHERE distance <= @distance
@latitude和@longitude是这个点的纬度和经度。 纬度和经度是距离表的列。 pi的价值是22/7
PostgreSQL的GIS扩展可能会有所帮助，因为它可能已经实现了许多你正在考虑实现的function。
尝试这个好的解决scheme： 地理定位search
坦克瑜珈
我在我的数据库中有一个来自Open Streep Maps的表格，我testing成功了。
距离工作罚款米。
SET @orig_lat=-8.116137; SET @orig_lon=-34.897488; SET @dist=1000; SELECT *,(((acos(sin((@orig_lat*pi()/180)) * sin((dest.latitude*pi()/180))+cos((@orig_lat*pi()/180))*cos((dest.latitude*pi()/180))*cos(((@orig_lon-dest.longitude)*pi()/180))))*180/pi())*60*1.1515*1609.344) as distance FROM nodes AS dest HAVING distance < @dist ORDER BY distance ASC LIMIT 100;
您可能会发现这些问题有帮助：
- 计算地理邻近度的公式
- 小数纬度/经度的最大长度？
正如biziclop提到的，某种度量空间树可能是您最好的select。 我有使用kd-trees和四叉树做这些types的范围查询的经验，他们非常快， 他们也不难写。 我build议看看这些结构之一，因为它们还可以让你回答其他有趣的问题，比如“我的数据集中的最接近点是什么？
你需要的是空间search。 您可以使用Solr空间search 。 它也有内置的经纬度数据types， 请点击这里 。
您可以将经度 – 纬度转换为UTM格式，这是可以帮助您计算距离的公制格式。 那么你可以很容易地决定点是否落入特定的位置。
既然你说任何语言都可以接受，那么自然的select就是PostGIS：
SELECT * FROM places WHERE ST_DistanceSpheroid(geom, $location, $spheroid) < $max_metres;
如果你想使用WGS数据，你应该把$spheroid设置$spheroid 'SPHEROID["WGS 84",6378137,298.257223563]'
假设你有geom列索引的places ，这应该是合理的效率。
你可以检查这个等式，我认为这会有所帮助
SELECT id, ( 3959 * acos( cos( radians(37) ) * cos( radians( lat ) ) * cos( radians( lng ) - radians(-122) ) + sin( radians(37) ) * sin( radians( lat ) ) ) ) AS distance FROM markers HAVING distance < 25 ORDER BY distance LIMIT 0 , 20;
