这是一个带有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
}
计算边界框,请使用以下函数:
def boundingRectangles(c: Point, r: Double): List[Rectangle] = {
val radLon = toRadians(c.x)
val radLat = toRadians(c.y)
val radDist = r / 6378137
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