我有两个 ArrayList，Double 数据类型，1.latitudes 2.longitudes，每个都有 200 多个元素
假设我给出一个随机的测试坐标，比如说 (1.33, 103.4)，格式是 [latitude, longitude]
是否有任何算法可以轻松找到最近点，还是我必须蛮力计算每个可能的点，找到斜边，然后比较 200 多个斜边以返回最近点？谢谢
问问题
3318 次
3 回答
2
沿一个轴对点数组进行排序。然后，沿该轴定位数组中最接近所需点的点并计算距离（使用适合问题拓扑和规模的任何度量）。
然后，沿着数组在两个方向上搜索，直到到这些点的距离大于迄今为止的最佳结果。最短距离点就是答案。
这可能导致必须搜索整个数组，并且是一种受问题几何约束的分支和边界形式。如果这些点在您正在搜索的点周围合理地均匀分布，那么扫描将不需要多次试验。
备用空间索引（如四叉树）将提供更好的结果，但您的少量点会使准备索引的设置成本比简单排序大得多。您将需要跟踪由排序引起的位置变化，因为您的其他数组不会以相同的方式排序。如果将数据更改为单个点数组，则排序将同时重新排序整个点。
于 2013-12-22T17:12:07.613 回答
0
不应该选择最接近的纬度（或经度）值来搜索长（或纬度）轴，实际上您可以停留在纬度（或经度）线上但远离经度（或纬度）值
所以最好的方法是计算所有距离并对它们进行排序
于 2015-02-19T09:22:55.130 回答
0
如果您的数组已排序，您可以使用二进制搜索来查找请求点在数组中的位置。找到索引后，您应该检查四个附近的点以找到最接近的点。
1）假设你有两个排序数组经度和纬度
2）您搜索第一个并找到两个附近的点
3）然后你搜索第二个并找到两个点
4）现在你有两到四个点（结果可能相交）
5）这些点将围绕目标点形成一个正方形
6）找到最近的点
于 2013-09-23T18:16:24.987 回答