合并 GPS 点以加速计算

Question

我有一个应用程序可以在用户每次签到时注册 GPS 坐标。如果用户回来重新签到，作为一种节省速度的选项，我们将显示他签到的最近的地点。

每次签到都会保存用户的当前位置，不管是第一次签到还是第100次签到。

一段时间后，我们有一个庞大的坐标列表，每次都需要检查。

如何折叠这些信息？我想将大量经纬度列表转换为一个或多个多边形，以便加快距离计算。

# So this
1:0 100:200 2:0 2:2 2:1 1:1 2:1 0:1

# Could become this
100:200 1:1

# Or this
100:200,100:200 0:0,2:2

Answer 1

这称为最近邻搜索问题。你可以看看 Wiki article which mentions faster algorithms. It seems that space partitioning with an R-Tree is the best approach.

Combine GPS points to speed up calculations