10

緯度/経度のペアで表されるポイントの大規模なセットを使用しています (ポイントは必ずしも一意であるとは限りません。セット内に同じ場所にある複数のポイントが存在する可能性があります)。ポイントはデータベースに保存されます。

私がしなければならないことは、検索を効率的に実行して、任意の点から指定された半径 (たとえば 25 マイル) 内にある点の数を取得する方法を見つけることです。カウントは 100% 正確である必要はありません。さらに重要なことは、それが高速で、正しいカウントにかなり近くなければならないということです。SQL でこれを行うには、WHERE 句で三角関数を使用したクエリを使用して、基準点までの距離でポイントをフィルタリングします。残念ながら、このクエリは非常に高価であり、場所が非常に分散しているため、キャッシュはあまり役に立ちません。

私は最終的に、この種の操作を効率的に処理できるある種のインメモリ構造を構築することを目指しています-速度と引き換えに、データの正確さとライブネスの一部をトレードオフします（おそらく1日に1回だけ再構築します） . 私は kd ツリーについていくつかの調査を行ってきましたが、これが緯度/経度データ (2 次元平面の x、y データとは対照的に) にどの程度適用できるかについてはまだ明確ではありません。

誰かが私が検討すべきアイデアや解決策を持っている場合は、本当に感謝します-事前に感謝します.

4

6 に答える 6

9

私はあなたがこの解決策を使うべきではないと思います。数日前にランダムに考えたのですが、特定の点からの距離の測定は、均一なグリッドではなく、円に基づいて行われると思います。0,0から離れるほど、精度は低くなります。

私がしたことは、PostalCodeクラスに2つの追加の値を設定することでした。郵便番号の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);
}

これで、DBの各行のグリッド参照0,0からのx、yグリッド距離（マイル単位）が得られました。長さ/緯度が5マイルのすべての場所を検索する場合は、最初にX、Yグリッド参照（たとえば25,75）を取得し、次にDBで20..30、70..80を検索します。を使用してメモリ内の結果をフィルタリングします

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

インDB部分は超高速であり、インメモリ部分はより小さなセットで動作して超正確になります。

于 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 の記事 " Finding Points Within a Distance of a Latitude/Longitude Using Bounding Coordinates " で、Bombe の提案に関する優れた説明を見つけることができます。

于 2011-09-27T11:43:23.527 に答える
1

既存の高価なクエリのサンプルを提供してもらえますか？

参照ポイントと他のデータポイントのsine（）とcosine（）を取得することに基づいて適切な大円計算を行っている場合は、これらのsin / cos値をデータベースに実際に保存することで、非常に大幅な最適化を行うことができます。 lat/long値に加えて。

または、データベースを使用して、一致する緯度/経度の範囲の長方形を抽出し、その後、真の円形半径の外側にある長方形を除外します。

ただし、経度の1度は、赤道よりも高緯度の方がやや短い距離であることに注意してください。ただし、その長方形の正しいアスペクト比を簡単に把握できるはずです。極に非常に近い領域を考慮する必要がある場合にもエラーが発生します。これは、長方形の選択では、極に重なる円に対応できないためです。

于 2009-02-05T16:16:56.470 に答える
1

このUDF（SQL Server）は、2つの緯度/経度ポイント間の距離を取得します。

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 に答える