如何使用纬度/经度数据进行有效范围搜索+计数？

Question

我正在处理由纬度/经度对表示的大量点(这些点不一定是唯一的,集合中可能有多个点位于同一位置).这些点存储在数据库中.

我需要做的是找出一种有效执行搜索的方法,以获得位于任意点的给定半径(例如,25英里)内的点数.计数不需要100%准确 - 更重要的是,它必须快速,并且合理地接近正确的计数.通过在WHERE子句中使用带有一些三角函数的查询来过滤点到参考点的距离,可以使用SQL执行此操作.不幸的是,这个查询非常非常昂贵,并且缓存不太可能提供很多帮助,因为位置将非常分散.

我最终希望构建某种内存结构,能够有效地处理这种操作 - 牺牲一些数据的准确性和活力(可能每天仅重建一次)以换取速度.我一直在研究kd-tree,但我还不清楚这可以应用于纬度/经度数据(与2d平面中的x,y数据相对).

如果有人有任何想法或解决方案我应该调查,我真的很感激 - 所以提前谢谢.

Answer 1

我认为你不应该使用这个解决方案.几天前我已经随机考虑过这个问题,我认为测量网格方块位置的特定点的距离将基于圆而不是统一的网格.距离0越远,你就越不准确!

我所做的是在PostalCode类上有2个额外的值.每当我更新PostalCode上的Long/Lat时,我会计算距离Long 0,Lat 0的X,Y距离.

public static class MathExtender
{
    public static double GetDistanceBetweenPoints(double sourceLatitude, double sourceLongitude, double destLatitude, double destLongitude)
    {
        double theta = sourceLongitude - destLongitude;
        double distance =
            Math.Sin(DegToRad(sourceLatitude))
            * Math.Sin(DegToRad(destLatitude))
            + Math.Cos(DegToRad(sourceLatitude))
            * Math.Cos(DegToRad(destLatitude))
            * Math.Cos(DegToRad(theta));
        distance = Math.Acos(distance);
        distance = RadToDeg(distance);
        distance = distance * 60 * 1.1515;
        return (distance);
    }


    public static double DegToRad(double degrees)
    {
        return (degrees * Math.PI / 180.0);
    }

    public static double RadToDeg(double radians)
    {
        return (radians / Math.PI * 180.0);
    }
}

然后我像这样更新我的课程:

private void CalculateGridReference()
{
    GridReferenceX = MathExtender.GetDistanceBetweenPoints(0, 0, 0, Longitude);
    GridReferenceY = MathExtender.GetDistanceBetweenPoints(0, 0, Latitude, 0);
}

所以现在我的数据库中每行的网格参考0,0都有一个x,y网格距离(以英里为单位).如果我想找到5英里长/纬度的所有地方,我会首先得到X,Y网格参考(例如25,75),然后我会在数据库中搜索20..30,70..80,并进一步使用在内存中过滤结果

MathExtensder.GetDistanceBetweenPoints(candidate.Lat, candidate.Long, search.Lat, search.Long) < TheRadiusOfInterest

数据库中的部分超快,内存部分可以在较小的集合上工作,使其更加精确.

Answer 2

对空间数据使用某种搜索树，例如四叉树。“另请参阅”下引用了更多此类数据结构。