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