6

我有两个 ArrayList,Double 数据类型,1.latitudes 2.longitudes,每个都有 200 多个元素

假设我给出一个随机的测试坐标,比如说 (1.33, 103.4),格式是 [latitude, longitude]

是否有任何算法可以轻松找到最近点,还是我必须蛮力计算每个可能的点,找到斜边,然后比较 200 多个斜边以返回最近点?谢谢

4

3 回答 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 回答