java - 优化最近公交站的搜索

Question

我想知道是否有更好的方法，给定纬度和经度，找到最近的公交车站，而不是通过完整的 ArrayList :

这是 BusStation 类:

    while(iteratore.hasNext()){    // for the full array size...
        tmp = (BusStation) iteratore.next();
        tmpDistance = getDistance(currentLat, currentLong, tmp.getStopLat(), tmp.getStopLon());
        if(tmpDistance < nearestDistance){  // if the distance is smaller ...
            nearestStop = tmp;  // i save the bus stop
            nearestDistance = tmpDistance;  // i save the distance too
        }
    }

这是效率不高的代码，它有效，但每次调用该方法时都必须< strong>查看具有复数 n 的完整数组。

我们如何使用数据结构作为二叉搜索树来优化它？

该方法的签名应如下所示:

public BusStation search(double currentLat, double currentLong){}

Answer 1

你的核心算法已经尽你所能了。但是，您可以通过首先根据位置将项目分类到存储桶中来减少必须检查的项目数量。例如，您可以为每 1 平方公里的 map 配备一个水桶。

如果你知道 map 上的每个点在 1 公里范围内都有一个公交车站，那么你只需要搜索目标 1 公里广场内的车站及其 8 个邻居 - 因为围绕 map 上的任何点绘制了一个 1 公里半径的圆中心方 block 将完全包含在这 9 个方 block 中。

在许多现实世界的情况下，根据您如何知道止损点分布，您可能会想出一种廉价的方法来选择保证包含您要查找的止损点的一小组正方形。它可以非常简单(“ map 上任何地方距离停靠点都不超过 1 公里，因此坐标周围的 3x3 方格将包含一个停靠点”)或更具技术性(“在城市中心，3x3 搜索保证命中；在郊区我需要 5x5")

如果算法需要更通用，那么您可以从搜索这 9 个正方形开始，然后添加与更大的圆重叠的正方形。

radius = 1
while(true) {
    Set<Square> squares = difference(
         squaresContainedIn(radius), 
         squaresContainedIn(radius - 1));
    busStop = findNearest(coords, squares);
    if(busStop != null) {
        return busStop;
    }
    radius ++;
}

不过要小心；你必须稍微改进这个算法。即使一格外有候选对象，最近的项目也可能在两格外:

a 33333
b 32223
c 32123
d 32223
e 33333

  ABCDE

按笛卡尔距离计算，最近的停靠点可能位于 E,c(第二个“搜索带”)，即使 B,d 的远角有一个项目(第一个“搜索带”)。有多种方法可以让算法处理这个问题:

1. 检查波段时，忽略不在当前半径范围内的停止点。在考虑radius的下一次迭代时，您需要再次查看这些方 block 。
2. 或者，当您找到候选者时，在您还搜索了下一个乐队之前，不要将其视为“最终”项目。

或者，根据现实世界的要求，您可能会认为偶尔错误(但仍然有用)的答案是可以接受的速度权衡。

如果您想扩大这种方法的规模，您可以使用 QuadTree正方形嵌套在较大正方形内的结构。