如何使用经纬度数据进行高效的范围搜索和计数？

Question

我正在处理一个由纬度/经度对表示的大量点集（这些点不一定是唯一的，可能存在多个位于相同位置的点）。 这些点存储在数据库中。

我需要做的是找出一种有效的方法，在给定半径（例如25英里）内找到位于任意点附近的点的数量。计数不需要100％准确 - 更重要的是，它必须快速，并且与正确计数相当接近。使用SQL可以实现此操作，通过在WHERE子句中使用三角函数来按距离过滤点以参考点。但不幸的是，这个查询非常昂贵，并且缓存可能无法提供太多帮助，因为位置会非常分散。

最终，我想建立某种内存结构，能够高效地处理此类操作 - 在速度方面进行权衡（也许只重建一天一次数据），以换取一些数据的准确性和及时性。 我已经研究了kd树，但我还不清楚如何将其应用于纬度/经度数据（而不是2D平面中的x，y数据）。

如果有人有任何想法或解决方案，我会非常感激 - 提前致谢。

- mpobrien

---

如果您提供更多关于您将在哪个平台上执行此操作的信息，会更有帮助... - alphadogg

如果你想使用k-d树，你需要将笛卡尔距离查询转换为纬度和经度范围（或者进行计算，看看分割纬度/经度平面是否与你的查询相交）。但此答案太短，无法作为一个真正的回答。 - MSN

Answer 1

我认为你不应该使用这个解决方案。几天前我随意想了一下，认为测量从特定点到网格方格的位置将基于圆而不是统一的网格。离0,0越远，精度就越低！

我的做法是在我的PostalCode类上有两个额外的值。每当我更新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);
}

现在，我在我的数据库中为每一行拥有一个距离(以英里为单位)的x,y网格距离，以从网格参考0,0开始计算。如果我想查找所有距某个经纬度5英里范围内的地点，我首先会得到X,Y网格参考点(比如25,75)，然后在数据库中搜索20..30，70..80，并进一步使用内存过滤结果。

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

数据库部分非常快，而内存部分在较小的数据集上工作，使其更加准确。

- Peter Morris

---

谢谢，这是我在这类问题上看到的最清晰的答案，大多数人基本上建议您获取Oracle、MS SQL或深入专业数据结构，而对于许多目的来说，这是快速的（比我尝试过的大多数解决方案，商业或免费的都要快），易于实现并且非常有效。它可以轻松地进行微调，以适应您可能遇到的所有情况。 - CharlesS

你不应该使用这个解决方案。它会测量从特定点的距离，这意味着网格方块将基于圆而不是统一的网格。离原点（0，0）越远，精度就越低！ - Peter Morris

Answer 2

使用R树。

在Oracle中，使用Oracle Spatial，您可以创建索引：

CREATE INDEX ix_spatial ON spatial_table (locations) INDEXTYPE IS MDSYS.SPATIAL_INDEX;

这将为您创建一个R-Tree并在其上进行搜索。

您可以使用任何地球模型，例如：WGS84、PZ-90等。

- Quassnoi

Answer 3

在处理空间数据时，可以使用某种搜索树，例如四叉树。更多此类数据结构可参见“相关链接”。

- starblue

Answer 4

你可以在Jan Philip Matuschek的文章《使用边界坐标找到距离给定纬度/经度一定距离内的点》中找到Bombe建议的详细���释。

- ankostis

Answer 5

这个SQL Server中的UDF将会帮助你得到两个经纬度点之间的距离：

CREATE FUNCTION [dbo].[zipDistance] (
    @Lat1 decimal(11, 6),
    @Lon1 decimal(11, 6),
    @Lat2 decimal(11, 6),
    @Lon2 decimal(11, 6)
)
RETURNS
    decimal(11, 6) AS
BEGIN

    IF @Lat1 = @Lat2 AND @Lon1 = @Lon2
        RETURN 0 /* same lat/long points, 0 distance = */

    DECLARE @x decimal(18,13)
    SET @x = 0.0

    /* degrees -> radians */
    SET @Lat1 = @Lat1 * PI() / 180
    SET @Lon1 = @Lon1 * PI() / 180
    SET @Lat2 = @Lat2 * PI() / 180
    SET @Lon2 = @Lon2 * PI() / 180

    /* accurate to +/- 30 feet */
    SET @x = Sin(@Lat1) * Sin(@Lat2) + Cos(@Lat1) * Cos(@Lat2) * Cos(@Lon2 - @Lon1)
    IF 1 = @x
        RETURN 0

    DECLARE @EarthRad decimal(5,1)
    SET @EarthRad = 3963.1

    RETURN @EarthRadius * (-1 * ATAN(@x / SQRT(1 - @x * @x)) + PI() / 2)

END

显然，你可以在单独的查询中使用这个功能，例如：

SELECT * FROM table WHERE [dbo].[zipDistance] < 25.0

- alphadogg

---

刚刚意识到你不想要 SQL？将其转换为其他语法应该很容易。但是，根据使用情况，这对我的应用程序来说还是相当不错的。 - alphadogg

但仍是我提议存储正弦和余弦而不是经纬度的好例子。这样做可以将此函数减少到每行只有一个三角函数，而不是五个 - 最后一个余弦项取决于点1 和 点2。 - Alnitak

有趣。不知道为什么我得研究一下。它可能会帮助我处理这个收集邮政编码区域数据的大型数据库... - alphadogg

Answer 6

你能提供一下你现有的昂贵查询的样本吗？

如果你正在进行基于参考点和其他数据点的正圆计算，那么可以通过在数据库中实际存储这些sin/cos值以及经纬度值来进行非常实质性的优化。

或者，只需使用数据库提取与真实圆形半径匹配的经纬度范围的矩形，然后再过滤掉超出该范围的点。

但请记住，在高纬度地区，一度经度的距离要比赤道短得多。不过，应该很容易确定该矩形的正确长宽比。如果需要考虑非常靠近极点的区域，则会出现错误，因为矩形选择无法处理重叠极点的圆形。

- Alnitak