优化搜索最近的公交站

Question

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

那是巴士站 Class :

    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
        }
    }

那是 效率不高的代码，有效但每次调用该方法时，它都必须遍历具有复数 n.

的完整数组

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

方法的签名应如下所示：

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

Answer 1

你的核心算法已经尽力了。但是，您可以通过首先根据位置将它们分类到桶中来减少必须检查的项目数量。例如，您可以为每 1 平方公里的地图设置一个桶。

如果您知道地图上的每个点在 1 公里内都有一个公共汽车站，那么您只需要搜索目标 1 平方公里内的站点及其 8 个邻居——因为一个 1 公里半径的圆围绕任何一个绘制中心方块上的点将完全包含在这 9 个方块中。

在许多现实世界的情况下，根据您对止损点分布的了解，您可能会想出一种廉价的方法来 select 一小组保证包含您正在寻找的止损点的方块为了。它可以非常简单 ("Nowhere on the map is further than 1km from a stop, so the 3x3 squares around the coordinates will contain one") 或更技术性 ("in the centre of the city, a 3x3 search guarantees a hit; in the outskirts I need 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（第二个 "search band"），即使 B,d（第一个 "search band"）的远角有一个项目.您可以通过多种方式让算法处理此问题：

检查波段时，忽略不在当前半径范围内的停止点。在考虑 radius.
或者，当您找到候选者时，在您还搜索了下一个波段之前，不要将其视为 "final" 项目。

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

如果您想扩大这种方法，您可以使用 QuadTree 结构，其中正方形嵌套在更大的正方形中。

优化搜索最近的公交站

Optimize the search of the closest bus stop

java

optimization

latitude-longitude

binary-search-tree

data-structures