3

かなり具体的な空間検索を行う必要があります。基本的に、2 つの位置を持つオブジェクト (obj1 と呼びましょう) を持ち、それらを点 A と点 B と呼びましょう。

次に、それぞれ独自の A と B の場所を持つオブジェクトのコレクション (それぞれを obj2 と呼びましょう) があります。

次の基準でソートされたコレクションから上位 10 個のオブジェクトを返したい:

(obj1A から obj2A までの距離) + (obj1B から obj2B までの距離)

何か案は？ありがとう、ニック

更新: ドキュメントの詳細と、それらを比較する方法を次に示します。

ドメイン モデル:

Listing: ListingId int タイトル文字列 Price double 出発地 場所 目的地 場所

場所: 郵便番号文字列 緯度 10 進 経度 10 進

私がやりたいことは、リスト オブジェクト (データベースにはありません) を取得し、それをデータベース内のリストのコレクションと比較することです。クエリで、出発地からのカラスの距離と目的地からのカラスの距離でソートされた上位 12 (または x) 件のリストを返すようにします。

出発地から目的地までの距離は気にしません。出発地から目的地までの距離と、目的地から目的地までの距離だけです。

基本的に、開始場所と終了場所が近いリストを見つけようとしています。

もっと明確にできるかどうか教えてください。ありがとう！

4

4 に答える 4

0

箱から出してすぐに解決策が見つかるとは思いません。

バウンディング ボックスの代わりにバウンディング 球体を使用してオブジェクトを指定すると、はるかに効率的になります。 http://en.wikipedia.org/wiki/Bounding_sphere

     C = ( A + B)/2 and R = distance(A,B) /2

比較したいデータの量を正確に把握していません。また、最も近いオブジェクトまたは最も遠いオブジェクトのペアを見たい場合。

どちらの場合も、3D を使用している場合は C 座標を octtree のパスとしてエンコードし、2D を使用している場合は quadtree をエンコードする必要があると思います。 http://en.wikipedia.org/wiki/Quadtree

これは最初のドラフトであり、これで十分でない場合はさらに情報を追加できます。3D に慣れていない場合は、2D から始めると簡単に始められます。

私はあなたの最新の追加を示しています。あなたの問題は干渉検出アルゴリズムに非常に似ているようです。

「終点」の座標系を「始点」を基準とした極座標で変更するとよいと思います。半径座標を許容範囲 (x マイル) に丸め、この値で並べ替える場合。

于 2010-12-31T13:19:57.067 に答える
0

ライドシェアのウェブサイトを構築しているようですね。:)

要するに、クエリ結果を表面距離で並べ替えるには、データベース エンジンに組み込まれた空間インデックスが必要です。ここでのオプションは、 OpenGIS 拡張機能を備えた MySQL (既に言及されています) またはPostGIS を備えた PostgreSQLだと思います。ravenDB でも可能のようです: http://ravendb.net/documentation/indexes/sptial

しかし、それができない場合は、他の方法がいくつかあります。問題を単純化して、場所 A までの距離でデータベース レコードを並べ替えたいだけだとします。これを 2 回実行して結果を合計しているだけだからです。

最も簡単な解決策は、データベースからすべてのレコードを取得し、場所 A までの距離を 1 つずつ計算してから、コードで並べ替えることです。問題は、多くの冗長な計算を実行し、クエリごとにテーブル全体を取得することになります。

もう一度単純化して、チェビシェフ (最大) 距離のみを気にするふりをしましょう。これは、より正確になる前に、データベース内の範囲を狭めるために機能します。近くのレコードの「バイナリ検索」を実行できます。返される最も近いレコードのおおよその数を決定する必要があります。10としましょう。次に、関心のある場所の周りの緯度 1 度、経度 1 度 (約 60x60 マイル) としましょう。関心のある場所が lat,lng=43.5,86.5 であるとしましょう。次に、データベースクエリは SELECT COUNT(*) FROM locations WHERE (lat > 43 AND lat < 44) AND (lng > 86 AND lng < 87) です。緯度/経度フィールドにインデックスがある場合、それは高速なクエリになるはずです。

私たちの目標は、ボックス内で合計10をわずかに超える結果を取得することです。ここで「二分探索」の出番です。結果が 5 件しかない場合は、ボックスの領域を 2 倍にして、もう一度検索します。100 件の結果が得られた場合は、領域を半分に分割して再度検索します。その直後に 3 つの結果が得られた場合は、ボックス領域を (100% ではなく) 50% 増やして再試行し、目標の 10 件の結果に十分近づくまで続行します。

最後に、この扱いやすい一連のレコードを取得し、対象の場所からのユークリッド距離を計算し、コードで並べ替えます。

幸運を！

于 2011-01-06T05:57:38.947 に答える
0

アルゴリズムの観点からは、バウンディング ボックスの中心を見つけてから、半径が大きくなる候補を選択して、十分な数を見つけます。

また、地球上のカラスの飛行距離はピタゴラス距離ではなく、別の式を使用する必要があることを思い出してください。

public static double GetDistance(double lat1, double lng1, double lat2, double lng2)
{
    double deltaLat = DegreesToRadians(lat2 - lat1);
    double deltaLong = DegreesToRadians(lng2 - lng1);

    double a = Math.Pow(Math.Sin(deltaLat / 2), 2) +
        Math.Cos(DegreesToRadians(lat1))
        * Math.Cos(DegreesToRadians(lat2))
        * Math.Pow(Math.Sin(deltaLong / 2), 2);

    return earthMeanRadiusMiles * (2 * Math.Atan2(Math.Sqrt(a), Math.Sqrt(1 - a)));
}
于 2011-01-06T00:04:12.747 に答える
0

このような問題を解決する方法は次のとおりです。

mysql 4.1 &

mysql 5。

mysql 4.1 からのリンクは非常に役立つようです。最初の例は、あなたが求めていることのほとんどです。

しかし、これがあまり役に立たない場合は、obj1 または obj2 のいずれかで対応するテーブルに対してループしてクエリを実行する必要があると思います。

于 2011-01-05T03:56:32.737 に答える