6

私の現在の位置（緯度、経度）を考えると、関心のある問題で最も近い隣人をすばやく見つけたいと思っています。したがって、迅速な検索を可能にする R-Tree データベースを使用するつもりです。ただし、最初にデータベースにデータを入力する必要があります - もちろんです。したがって、領域をカバーする四角形の領域を決定する必要があります。各領域には 1 つの対象ポイントが含まれます。

私の質問は、データをどのように前処理するか、つまり、領域をこれらの長方形のサブ領域に分割するにはどうすればよいかということです。（より一般的なボロノイ領域とは対照的に、RTreeに簡単に追加できるため、長方形の領域が必要です）。

/ジョン

4

3 に答える 3

2

Oracle Spatial Cartridgeのドキュメントでは、必要なことを実行できるテッセレーション アルゴリズムについて説明しています。要するに：

  • すべてのポイントを正方形で囲みます
  • 正方形に 1 つの点が含まれる場合 - インデックス正方形
  • 正方形に点が含まれていない場合 - 無視します
  • 正方形に 1 つ以上の点が含まれる場合
    • 正方形を 4 つの等しい正方形に分割し、新しい正方形ごとに分析を繰り返す

結果は次のようになります:
代替テキスト http://download-uk.oracle.com/docs/cd/A64702_01/doc/cartridg.805/a53264/sdo_ina5.gif

于 2009-02-15T22:01:58.843 に答える
2

編集:以下のアプローチは機能しますが、R ツリーの重要な機能を無視します。つまり、R ツリー ノードの分割動作は明確に定義されており、(B ツリーのようなプロパティを通じて) バランスの取れたツリーを維持します。実際、あなたがしなければならないことは次のとおりです。

  1. 1 ページあたりの長方形の最大数を選択する
  2. シード長方形を作成します (互いに最も離れた点、重心などを使用します)。
  3. ポイントごとに、それを配置する長方形を選択します
    1. すでに単一の長方形に収まっている場合は、そこに入れます
    2. そうでない場合は、最小に拡張する必要がある長方形を拡張します (「最小」の出口を測定するさまざまな方法 -- 領域の動作)
    3. 複数の四角形が適用される場合 -- どれくらいいっぱいか、または他のヒューリスティックに基づいて 1 つを選択してください
  4. オーバーフローが発生した場合 -- 二次分割を使用して物事を移動します...
  5. などなど、R ツリー アルゴリズムを教科書からそのまま使用します。

最初のシード長方形を見つけるには、以下の方法で問題ないと思います。しかし、R ツリー全体をそのように設定したくはありません。スプリットとリバランスを常に行うと、少しコストがかかる可能性があるため、以下の KD アプローチを使用して、かなりの量の作業を行うことをお勧めします。すべての作業ではありません。

KD アプローチ: すべてを長方形で囲みます。

長方形内のポイントの数が > しきい値の場合は、ポイントの半分をカバーするまで方向 D にスイープします。

分割点の左右（または上下）で四角形に分割します。

次の方向で、新しい四角形で同じ手順を再帰的に呼び出します (左から右に移動する場合は、上から下に移動し、その逆も同様です)。

これが別のポスターによって提供された正方形に分割するアプローチよりも優れている点は、歪んだポイント分布によりよく対応できることです。

于 2009-02-15T22:10:13.567 に答える