算法来计算许多地理点之间的距离

我有一个矩阵有大约1000个地理空间点（经度，纬度），我试图找到在1KM范围内的点。算法来计算许多地理点之间的距离

注：“分是动态的，试想一下，1000辆是移动的，所以我不得不重新计算每隔几秒钟，所有的距离”

我做了一些搜索和阅读有关图形算法，如（Floyd- Warshall）来解决这个问题，最后我得到了很多关键字，现在我有点迷路了。我正在考虑性能，由于搜索半径很短，我不会考虑地球的曲率。

基本上，我似乎必须计算每个点到每个其他点之间的距离，然后对从矩阵中每个点开始的距离进行排序，并获取其范围内的点。所以如果我有1000个坐标，我必须执行这个过程（1000^2-1000）次，我不相信这是最佳的解决方案。谢谢。

来源

2012-01-19 Alaa Qutaish

我认为这个问题涉及到最接近的一对点问题，请检查此进一步参考http ：//en.wikipedia.org/wiki/Closest_pair_of_points_problem –

您是否正在寻找距离特定纬度/经度1KM以内的积分，或者您是否正在寻找相互之间1KM以内的积分？ –

每个点都应该找到距离它1KM范围内的所有点。 –

就你而言，你应该看看GeoHash，它允许你快速查询给定距离内的坐标。

仅供参考，MongoDB在内部使用geohash，表现出色。

来源

2012-01-19 07:15:36 qiao

是的，我写了一些关于这个，但不断分散注意力。您可以使用散列查找附近的事物，以便您不必直接比较所有1000. –

此外，您不应该排序任何内容。只需创建一个新的数据结构（最好带有O（1）插入时间 - 如果需要排序的结果，可以使用O（log n）插入树结构），并为每个<1km的所有点保留一个列表点。放下任何> 1公里的东西。 –

有趣的建议，但如果使用geohash，这是什么数据模型？ – Jasonw

您可以在这1000个坐标的每一个周围计算1km范围的地理编码，并检查某些点是否在该范围内。可能不是最佳的，但你可以节省一些排序。

来源

2012-01-19 06:51:09 koressak

如果你与1公里间距的网格上的产品型号名称：

0 1 2 3 
___|____|____|____ 
0 | | | 
    c| b|a | d 
___|____|____|____ 
1 | | | 
    | |f | 
___|e___|____|____ 
2 | |g |

让我们假设你的出发点是一个。如果您的网格的大小为1km，则1km范围内的点必须位于同一个单元格中或8个相邻单元格中的一个（点b，d，e，f）。

每隔一个单元格可以忽略（c，g）。

虽然d与c的距离几乎相同，但c可以提前下降，因为有2个交叉屏障，而a和d位于它们边界的相对区域，因此距离接近2公里从彼此。

对于提前丢弃元素，您可以排除，检查坐标的x或y部分就足够了。由于a属于（0,2），如果x为0或更小，或> 3，则该点已超出范围。

过滤只有少数候选人后，您可以使用穷举搜索。

来源

2012-01-19 07:26:40

我正在考虑类似的事情，但是我们需要得到点的方向，例如，如果我知道（g）距离（f）南1公里并且（a）距北（北）1公里然后，当扫描（a）周围的点时，所有离开（g）到南方的点将被排除。我们只需要在第一时间完成全部搜索以找出所有点与一个点的关系，然后可能性会减少，因为点关系将更加相互连接。“算法从点的位置学习”我不知道还在想什么！ –

如果你想查找每个点与每个点的矩阵，那么你已经有了正确的公式（1000^2-1000）。这个计算没有任何捷径。但是，如果您知道从哪里开始搜索，并且希望在1KM范围内查找点，则可以使用网格或空间算法来加速查找。最有可能的是使用分而治之的算法，而最便宜的是geohash或z曲线。你也可以尝试一个kd-tree。也许这更简单。但是，如果你的观点在奥克利德空间中，那么这里描述的是这种平面方法：http://en.wikipedia.org/wiki/Closest_pair_of_points_problem。

编辑：当我说1000^2-1000那么我的意思是网格的大小，但它实际上是1000 ^（1000-1）/ 2对点，所以很少数学。

来源

2012-01-19 07:42:26 Bytemain

我在我工作的网页上有类似的东西，我想。用户单击地图上的某个位置并输入一个半径，并且函数返回给定半径内数据库内的所有位置。你的意思是你正在试图找到半径内某点的1公里内的点？或者你是否试图找到距离彼此不到1公里的点？我认为你应该做这样的事情。

radius = given radius 
x1 = latitude of given point; 
y1 = longitude of given point; 
x2 = null; 
y2 = null; 
x = null; 
y = null; 
dist = null; 

for (i=0; i<locationArray.length; i++) { 
    x2 = locationArray[i].latitude; 
    y2 = locationArray[i].longitude; 
    x = x1 - x2; 
    y = y1 - y2; 
    dist = sqrt(x^2 + y^2); 
    if (dist <= radius) 
     these are your points 
}

如果你想计算都是在另一个点1公里的点，你可以添加一个外环给X1和Y1的信息，那么这将使得内环测试之间的距离给定点和其他每个点都将给出矩阵中的每个点作为输入。计算不应该花太长时间，因为它非常基础。

来源

2012-01-22 19:21:20

是的，这是基本的蛮力搜索，如果我有1000分，那么我有100万次计算！在我的情况下积分是动态的，所以我必须每隔几秒就执行一百万次计算。这似乎并不是最佳解决方案。对？ –

尝试使用R-Tree。 R-Tree支持查找距离给定点最近的所有点，这些点不会远离给定的半径。执行时间是最优的，我认为它是O（number_of_points_in_the_result）。

来源

2013-02-07 10:36:36

我有同样的问题，但在Web服务开发在我的情况，以避免我用一个简单的除法&征服解决方案的计算时间问题：当时的想法是启动距离的新点和其他人之间的计算在每一个新的数据插入，以便我的应用程序直接访问那些已经计算，并把我的数据库中的距离之间的距离

来源

2014-04-21 13:43:16 BiLL

算法来计算许多地理点之间的距离

回答

相关问题