在R或Python中查找一组对象中的最小距离

Question

我有一组县，以及每个质心的经纬度：

county    lat       lon 
Abiline   32.134   -23.322
Cook      43.324   -32.219
Allegheny 31.949   -30.123

我也有很多医院的名单，每个医院的经纬度。我想找出每个县到最近医院的距离。在

到目前为止，我已经使用ggmap中的geocode（）函数来查找每个县到每个医院的距离，然后选择最小距离。但是，因为我有很多县和很多医院，这个问题很快就会变成高维的，而且可能需要很长时间。在

我不想为此使用arcgis—有没有一种直接的方法用R或Python来实现？在

Answer 1

我想你想要达到的目标是这样的问题 closest pair of points以下是实现相同目的的完整算法和说明：

We are given an array of n points in the plane, and the problem is to find out the closest pair of points in the array. This problem arises in a number of applications. For example, in air-traffic control, you may want to monitor planes that come too close together, since this may indicate a possible collision. Recall the following formula for distance between two points p and q. The Brute force solution is O(n^2), compute the distance between each pair and return the smallest. We can calculate the smallest distance in O(nLogn) time using Divide and Conquer strategy.

算法

下面是O（n（Logn）^2）算法的详细步骤。 输入：n个点的数组P[] 输出：给定数组中两点之间的最小距离。在

作为预处理步骤，输入数组按x坐标排序。在

1. 在排序数组中找到中间点，可以取P[n/2]作为中间点。在
2. 将给定数组分成两半。第一个子数组包含从P[0]到P[n/2]的点。第二个子阵包含从P[n/2+1]到P[n-1]的点。在
3. 递归地找到两个子数组中的最小距离。设距离为dl和dr，求dl和dr的最小值，取最小值d
4. 递归地找到两个子数组中的最小距离。设距离为dl和dr，求dl和dr的最小值，取最小值d
5. 根据y坐标对数组条[]进行排序。这一步是O（nLogn）。通过递归排序和合并，可以将其优化为O（n）。在
6. 在条带[]中找到最小距离。这很棘手。从第一眼看，这似乎是一个O（n^2）的步骤，但实际上是O（n）。从几何上可以证明，对于条带中的每个点，最多只需要检查它之后的7个点（注意，条带是按Y坐标排序的）。在
7. 最后返回上述步骤（步骤6）中计算的d和距离的最小值

实施is here

希望这有帮助：）

资料来源：Geeksforgeeks.org网站在