RTree の前のステップ:一連の点を 1 つの点を含む長方形領域に分割します。

Question

現在の位置 (緯度、経度) を考慮して、興味のある点の問題で最近傍をすばやく見つけたいと考えています。そこで、素早い検索を可能にする R-Tree データベースを使用するつもりです。ただし、当然ですが、最初にデータベースにデータを入力する必要があります。したがって、エリアをカバーする長方形の領域を決定する必要があります。各領域には 1 つの注目点が含まれます。

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

/ジョン

Answer 1

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

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

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

---

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

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

分割点の左右(または上下)で長方形に分割します。

新しい四角形に対して、次の方向で同じプロシージャを再帰的に呼び出します (左から右に移動していた場合は、上から下に移動し、その逆も同様です)。

別の投稿者が提供する正方形に分割するアプローチに比べて、この方法の利点は、偏った点分布にうまく対応できることです。

Answer 2

Oracle 空間カートリッジ ドキュメントには、必要なことを実行できるテッセレーション アルゴリズムが説明されています。要するに：

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

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

Answer 3

私はあなたの問題文で欠けている何かを考えます。あなたはすべての点でユニークX-を有し、y座標ようにN個の点（x、y）を有すると仮定する。あなただけのN垂直列に分割して、その後、N個の長方形にお住まいの地域を分割することができます。しかし、それはあなたが簡単に最寄りのPOIの問題を解決する助けにはならない、それはありませんか？だから私はあなたがまだ連接されていない長方形の構造について何かについて考えていると思います。

イラストます：

| | | | |5| | |
|1| | | | |6| |
| | |3| | | | |
| | | | | | | |
| |2| | | | | |
| | | | | | |7|
| | | |4| | | |

の数字は、ランドマークであり、垂直線7つの矩形領域に再分割を示します。しかし、明確に細分化で多くの「面白い」の情報はありません。あなたが言及していない小分けにいくつかの追加的な基準はありますか？