以最佳方式对 GPS 坐标进行分组的正确算法是什么？

Question

我需要一种算法来对最近的 GPS 坐标进行分组。

我目前正在使用 OSRM 来管理它，但由于其限制（每个请求 100 个项目），我将不得不自己进行本地实现。

我读过有关 Dijkstra's、A*（其变体）、收缩层次结构等的内容……据我了解，大多数（如果不是全部）都需要点之间有联系，这就是我的问题所在。在我的场景中，所有坐标都相互“连接”。你可以通过任何人到达任何人。我只想将它们按最接近的分组。

下图中显示了一个示例（请持保留态度，这只是尝试解释我的问题的视觉表示）：

在上图提出的场景中，我有 187 个坐标，并要求它们以 5 个最接近的坐标为一组。考虑到使用真实地图需要大量内存，我想只使用点之间的距离，忽略边缘、道路和剖面（步行、驾驶等 - 尽管步行是最佳选择）。

我知道，如果不使用真实地图，我会遇到诸如“最近的 GPS 坐标需要过河”之类的问题，但目前我可以接受这一点。

鉴于上述解释，我的问题是：

1 - 除了提到的算法之外，还有其他算法可以帮助我解决该问题吗？

2 - 如果 Dijkstra 是可行的方法，我可以在坐标之间创建手动连接，以便它们可以工作吗？它与 Dijkstra 的效果如何？

希望我能够清楚地解释问题，但如果没有，请向我询问您可能有的任何问题，以便我改进。

1. 我正在使用OSRM
2. 我使用 .NET 迁移到本地（不稳定）解决方案

   .Distance

3. 我读到了 Dijkstra、A*（其变体）和收缩层次算法

Answer 1

我会研究K-means，它非常适合这个应用程序：

import numpy as np
from sklearn.cluster import KMeans
import matplotlib.pyplot as plt

np.random.seed(10)
gps = np.random.rand(500, 2) * 100

clusters = 7

kmeans = KMeans(n_clusters=clusters, random_state=0).fit(gps)

lbs = kmeans.labels_
ctr = kmeans.cluster_centers_

for i in range(clusters):
    cluster_points = gps[lbs == i]

plt.scatter(gps[:, 0], gps[:, 1], c=lbs, cmap='viridis')
plt.scatter(ctr[:, 0], ctr[:, 1], s=300, c='black')
plt.show()

打印

来自维基

另请参阅凸包