12

こんにちは。

私の状況：

  • 二次元空間で。
  • 入力: 長方形のセット(重なり合う長方形も)。
    • 長方形の座標は整数型です。
    • 四角形のサイズと四角形の位置に制約はありません (整数の範囲のみ)。
    • width=0 または height=0 の長方形はありません。
  • 見つける必要があります：入力されたポイントを含むすべての長方形（整数座標）。

入力した点を含む長方形を見つけます。

質問:

  • 長方形を維持するための効率的な構造は何ですか?
  • この場合、どのアルゴリズムが効率的ですか?
    • また、長方形を削除せずに追加する場合にのみ効率的なアルゴリズムは何ですか?

ありがとう ：-）。

4

5 に答える 5

21

R-Treeは、このユースケースに適した最適なデータ構造です。Rツリーは、空間アクセス方法、つまり地理座標、長方形、ポリゴンなどの多次元情報のインデックス作成に使用されるツリーデータ構造です。すべての長方形の情報をツリー形式で保存できるため、検索が簡単になります

ウィキペディアのページ、短いppt、および研究論文は、概念を理解するのに役立ちます。

ここに画像の説明を入力してください

于 2012-04-22T16:18:59.810 に答える
3

長方形のセットが動的である可能性があるようです（「...長方形を追加するため...」）。この場合、2D間隔ツリーが解決策になる可能性があります。

于 2012-04-22T16:21:49.343 に答える
3

Javaでは、shape.containsを使用できます

しかし、一般に、長方形が (x,y,width,height) で定義されていると仮定すると、

if (pt.x >= x && pt.x <= x + 幅 && pt.y >= y && pt.y <= y + 高さ) ...

コレクションにすべての長方形がある場合は、コレクションを反復処理して、ポイントを含むものを見つけることができます

于 2012-04-22T15:25:31.063 に答える
2

これが簡単な解決策です。

  1. 平面にグリッドを定義します。
  2. 各セルは、このセルを完全に覆う四角形と、このセルを部分的に覆う四角形の 2 つのリストを保持します。
  3. 挿入するたびに、対象の四角形の ID を関連するすべてのセル リストに入れます。
  4. 各クエリで、ターゲット ポイントを含むセルを見つけ、完全なカバー リストを出力し、部分的なカバー リストでスキャンを実行します。
于 2012-04-22T16:42:20.460 に答える
2

四角形(left, top, right, bottom)には、 および の場合(x, y)(座標が下向きに増加すると仮定します。これは、私が見たほとんどのハードウェアの場合です。座標が上向きに増加する場合、より伝統的に数学的なケースであるスワップおよび)。テストよりもはるかに効率的になることはありません。left < x < right top < y < bottomtopbottom

四角形が境界線上にもある場合にポイントを「含む」と見なす場合は、すべての を に置き換え<ます<=。

長方形のコレクションをどうするかについては...わかりません。コーナーの座標でソートされたリストは何かをすると思いますが、あまりメリットはありません...せいぜい、チェックするもののリストを平均して半分に削減することになります（最悪の場合でもすべてをチェックする必要があります）。おかしなロット全体の半分でも、まだ全体のロットになる可能性があります。:)

于 2012-04-22T15:29:02.297 に答える