基于Scala/Spark查找当前位置附近的3个最近公交站点

一、基础实现（适合小体量站点数据） #

如果你的公交站点数据量不大（比如几千条以内），直接计算距离+排序的方案简单高效，无需额外依赖：

• 用欧几里得距离的平方代替真实距离做比较：避免开根号的性能损耗，排序结果完全等价
• 遍历所有站点，计算每个站点到当前位置(X,Y)的距离平方
• 按距离平方升序排序，取前3个站点

代码示例 #

// 可直接用Tuple2存储站点坐标，也可以定义专用类
case class BusStop(x: Double, y: Double)

// 输入数据
val busStopLocations: List[(Double, Double)] = List((1.2, 3.4), (5.6, 7.8), /* 更多站点 */)
val currentX: Double = 2.0
val currentY: Double = 4.0

// 计算距离平方、排序、取前3
val nearestStops = busStopLocations
  .map { case (x, y) =>
    val distanceSq = Math.pow(x - currentX, 2) + Math.pow(y - currentY, 2)
    (distanceSq, x, y)
  }
  .sortBy(_._1)
  .take(3)
  .map { case (_, x, y) => (x, y) }

// 输出结果
nearestStops.foreach(stop => println(s"最近站点：(${stop._1}, ${stop._2})"))

二、优化方案（适合大体量站点数据） #

如果站点数据量达到上万甚至更多，遍历排序的O(n log n)复杂度会成为瓶颈，此时可以用空间索引结构将查询复杂度降到O(log n)：

• KD-Tree：适合高维空间的最近邻查询，Scala可自行实现简易版，或直接调用Java空间库（比如org.locationtech.jts:jts-core）
• QuadTree：专门针对二维平面的空间索引，适合公交站点这类二维坐标场景

核心思路 #

1. 提前将所有公交站点构建成空间索引结构
2. 查询时从索引根节点递归查找，实时记录当前最近的3个站点
3. 剪枝掉不可能包含更近站点的子树，大幅减少计算量

三、场景适配优化 #

• 若站点数据是静态的，提前构建好索引并缓存到内存，避免每次查询重复构建
• 如果是经纬度坐标，必须用**球面距离（Haversine公式）**计算真实地理距离，不能用欧几里得距离：

// Haversine公式计算球面距离（单位：米）
def haversineDistance(lat1: Double, lon1: Double, lat2: Double, lon2: Double): Double = {
  val earthRadius = 6371000 // 地球半径，单位米
  val dLat = Math.toRadians(lat2 - lat1)
  val dLon = Math.toRadians(lon2 - lon1)
  val a = Math.sin(dLat/2) * Math.sin(dLat/2) +
          Math.cos(Math.toRadians(lat1)) * Math.cos(Math.toRadians(lat2)) *
          Math.sin(dLon/2) * Math.sin(dLon/2)
  val c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a))
  earthRadius * c
}

内容的提问来源于stack exchange，提问作者IcePack