scala - 使用 Scala 在内存中运行地理空间查询

Question

有没有办法在 Scala 中运行地理空间查询，给定一组纬度/经度坐标，以找到最近的距离？查询可能需要在内存中运行。

这组值大约是 100 万经纬度坐标。我试图在 Spark 中做到这一点，但我找到的唯一解决方案是 Magellan但我什至无法使其适用于 Spark 1.6 和 Scala 2.11，所以我正在尝试定制解决方案。

查询示例:给定 wgs84 坐标中的一个点和 100 万组 wsg84 坐标，我想要一英里半径内最近的 15 个坐标。

Answer 1

这是一个带有 RTree 实现的库，可用于在 Scala 中索引地理数据:https://github.com/davidmoten/rtree

只需通过边界框矩形为您的点选择，该点将是具有给定半径(在您的情况下为距离)的圆的中心，然后按距离过滤点以去除边界框角落中的误报，然后按以下方式对结果进行排序已经计算出的距离需要最近的 15。

您可以使用“haversine”公式来检查点之间的距离条件(请参阅此处的说明 http://www.movable-type.co.uk/scripts/latlong.html):

import java.lang.Math._
import com.github.davidmoten.rtree.geometry.{Point, Rectangle}
import com.github.davidmoten.rtree.geometry.Geometries._

def distance(p1: Point, p2: Point): Double = {
  val radLon1 = toRadians(p1.x)
  val radLat1 = toRadians(p1.y)
  val radLon2 = toRadians(p2.x)
  val radLat2 = toRadians(p2.y)
  val x = sin((radLon2 - radLon1) * 0.5)
  val y = sin((radLat2 - radLat1) * 0.5)
  val a = y * y + cos(radLat1) * cos(radLat2) * x * x
  atan2(sqrt(a), sqrt(1 - a)) * 12756274 // The Earth diameter in meters
}

对于边界框的计算，请使用以下函数:

def boundingRectangles(c: Point, r: Double): List[Rectangle] = {
  val radLon = toRadians(c.x)
  val radLat = toRadians(c.y)
  val radDist = r / 6378137 // The Earth radius in meters
  val lat1 = toDegrees(radLat - radDist)
  val lat2 = toDegrees(radLat + radDist)
  if (lat1 > -90 && lat2 < 90) {
    val deltaLon = asin(sin(radDist) / cos(radLat))
    val lon1 = toDegrees(radLon - deltaLon)
    val lon2 = toDegrees(radLon + deltaLon)
    if (lon1 < -180) rectangle(-180, lat1, lon2, lat2) :: rectangle(lon1 + 360, lat1, 180, lat2) :: Nil
    else if (lon2 > 180) rectangle(-180, lat1, lon2 - 360, lat2) :: rectangle(lon1, lat1, 180, lat2) :: Nil
    else rectangle(lon1, lat1, lon2, lat2) :: Nil
  } else rectangle(-180, max(lat1, -90), 180, min(lat2, 90)) :: Nil
}

日期更改子午线穿过圆形时所需的矩形列表，因为 RTree 不支持在地球上包裹地理坐标，因此我们按日期更改子午线将该矩形分成两个。

公式和说明在这里 http://janmatuschek.de/LatitudeLongitudeBoundingCoordinates#Longitude

编辑:最后，我们最终得到了我们自己的不可变 RTree 版本，带有 STR 打包，该版本针对平面和球形几何结构上的高效窗口和 knn 查询进行了调整:

https://github.com/plokhotnyuk/rtree2d