10

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

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

我最终希望构建某种能够有效处理这种操作的内存结构 - 以牺牲数据的一些准确性和活跃性（可能每天只重建一次）来换取速度. 我一直在对 kd-trees 进行一些研究，但我还不清楚这可以如何应用于纬度/经度数据（与二维平面中的 x,y 数据相反）。

如果有人有我应该研究的任何想法或解决方案，我将非常感激 - 所以提前致谢。

4

6 回答 6

9

我认为您不应该使用此解决方案。几天前随机想到它，我认为测量与特定点的距离，网格方块的位置将基于圆形而不是统一的网格。离 0,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

数据库中的部分超快，而内存中的部分在较小的集合上工作以使其超准确。

于 2009-02-05T16:26:30.100 回答
4

使用R-Trees.

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

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

这将为您创建一个R-Tree并搜索它。

您可以使用任何Earth Model您喜欢的：WGS84等PZ-90。

于 2009-02-05T16:18:06.357 回答
3

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

于 2009-02-05T16:15:43.540 回答
2

您可以在 Jan Philip Matuschek 的文章“使用边界坐标查找纬度/经度距离内的点”中找到对 Bombe 建议的出色解释。

于 2011-09-27T11:43:23.527 回答
1

您能否提供一个现有昂贵查询的样本？

如果您基于参考点和其他数据点的 sine() 和 cosine() 进行适当的大圆计算，则可以通过将这些 sin/cos 值实际存储在数据库中来进行非常实质性的优化除了纬度/经度值。

或者，只需使用您的数据库来提取一个匹配的经度/经度范围的矩形，然后再过滤掉那些超出真实圆形半径的矩形。

但请记住，高纬度地区的经度比赤道地区的距离要短一些。不过，应该很容易找出该矩形的正确纵横比。如果您需要考虑非常靠近极点的区域，您也会遇到错误，因为矩形选择无法处理与极点重叠的圆圈。

于 2009-02-05T16:16:56.470 回答
1

此 UDF（SQL Server）将为您提供两个纬度/经度点之间的距离：

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
于 2009-02-05T16:26:04.907 回答