我有大约1000个点，想要根据距离将这些点分组。我正在使用Haversine公式，但它似乎非常慢。在Android上，处理1000个点需要4秒，在我的本地环境中只需60毫秒。
我不关心精度，而且这些点之间的距离不超过25公里。
是否有其他公式可以使用？
在Android中如何快速计算多个点之间的距离
4
- Federico
4
那么对于每一个千个点，您需要计算到每一个其他点的距离吗？您想要实现什么目标？ - ninesided
另请参阅Nick Johnson的Dijkstra帖子-如果这是您感兴趣的内容，那里有非常详细的信息。https://dev59.com/gHRC5IYBdhLWcg3wCMnX#432854 - Marvin Pinto
不，它不是每个点到每个其他点的距离。它是每个点到所有聚类的距离。对于第一个(s)点(0s)，聚类列表为空，因此创建一个新聚类。然后比较距离，如果小于X，则将其添加到聚类并重新计算聚类中心，否则创建新聚类。对于1000个点，它不是1000的平方，而更像是1000乘以4。 - Federico
1你可以选择使用Dijkstra算法。这里有一个好的描述：https://dev59.com/xVkS5IYBdhLWcg3w8ai-#39256428 - Alex Filatov
4个回答
6
首先，对于彼此靠近的物品，地球的曲率不会太重要。因此，您可以将其视为平面，在这种情况下，您正在查看距离的勾股定理（x/y距离平方和的平方根）。
其次，如果你只是在排序/分组，你可以省略平方根计算，直接在距离的平方上进行排序/分组。在缺乏浮点协处理器的设备上，例如前几代Android手机，这将非常有用。
第三，您没有指示您用于点的坐标系，但如果您可以使用定点数学进行计算，则这也将提高性能，特别是在没有协处理器的设备上。这就是为什么Android的Google Maps附加组件使用GeoPoint和微度而不是从LocationManager中获取的Java double度数中的Location。
- CommonsWare
4
我喜欢这个方法，但我需要能够说将所有距离不到5公里的东西分组。如果我使用勾股定理，有没有一种方法可以得到以米、千米等为单位的结果，而无需考虑地球曲率以提高准确性。还有其他实现相同目标的方法吗？ - Federico
@Federico：如果您的X和Y单位是米，那么两者平方和的平方根单位也将是米。如果您的X和Y单位是秒差距，那么两者平方和的平方根的单位将会是秒差距。以此类推。 - CommonsWare
@Federico：如果你的经度和纬度是以度为单位的，它们差值平方和的平方根也将以度为单位。如果你的经度和纬度是以微度为单位的，它们差值平方和的平方根也将以微度为单位。 - CommonsWare
1对于纬度度数，它们在地球尺度的周长上；而经度度数则基于纬度在周长上。为了将它们结合起来，以便使用勾股定理制作等效距离，您需要将其中一个缩放以匹配另一个。我的答案意味着如果不接近极点，则只需要计算一次缩放因子。 - Ifor
2
只要您不需要在极地附近处理，并且可以使用近似值进行分组，那么您就可以计算出纬度度数和经度度数之间的相对比例，并将其用于每个直角坐标系X平方+y平方的计算中。对于相对距离，您可以跳过平方根。
如果您使用度数来缩放它们以使纬度和经度具有相同的相对距离，则应使用纬度的cos值。我会将纬度缩放到经度，然后每个度数都映射到一个已知的良好距离，计算将类似于：
(lattitude差异for两个点)* 1 / cos（latitude）
假设纬度在样本集上没有太大变化，您只需一次计算出1 / cos（latitude）即可适用于所有点。
如果您使用度数来缩放它们以使纬度和经度具有相同的相对距离，则应使用纬度的cos值。我会将纬度缩放到经度，然后每个度数都映射到一个已知的良好距离，计算将类似于：
(lattitude差异for两个点)* 1 / cos（latitude）
假设纬度在样本集上没有太大变化，您只需一次计算出1 / cos（latitude）即可适用于所有点。
- Ifor
1
@lfor：你能解释一下如何缩放经纬度以便使用勾股定理吗？ - Federico
2
也许可以去除计算地球曲率的部分吗？如果您的应用程序功能允许，则请这样做。
这种格式总是成立的。给定两个点，您总是可以绘制它们、画直角三角形，然后找到斜边的长度。斜边的长度就是两点之间的距离。由于这种格式总是有效的，因此可以将其转化为公式：
距离公式：给定两点（x1，y1）和（x2，y2），这些点之间的距离由以下公式给出：http://www.purplemath.com/modules/distform.htm 距离= sqrt((x2-x1)^2 + (y2-y1)^2)
更新正确的符号:
这种格式总是成立的。给定两个点，您总是可以绘制它们、画直角三角形，然后找到斜边的长度。斜边的长度就是两点之间的距离。由于这种格式总是有效的，因此可以将其转化为公式：
距离公式：给定两点（x1，y1）和（x2，y2），这些点之间的距离由以下公式给出：http://www.purplemath.com/modules/distform.htm 距离= sqrt((x2-x1)^2 + (y2-y1)^2)
更新正确的符号:
double distance = Math.sqrt(Math.pow(x2 - x1, 2) + Math.pow(y2 - y1, 2));
- wurde
1
工作时，请牢记正确的安卓符号以获得有效结果：double distance = Math.sqrt(Math.pow(x2 - x1, 2) + Math.pow(y2 - y1, 2)); - Pelanes
0
据我所知，解决这个问题的最佳方法是使用图论，其中包括Dikstra's algorithm，在我所了解的算法中，它是处理这种任务最快的算法。
学习它真的很值得，可以优化工作效率。
学习它真的很值得，可以优化工作效率。
- Eimantas Kasperiūnas
1
由于某些原因，我的链接无法推送，请将其原样复制到您的浏览器中。 - Eimantas Kasperiūnas
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接