8

この例のように、長方形を構成する水平線と垂直線が多数あります。

水平線と垂直線の画像

別の長方形を含まないすべての長方形を見つけることができるアルゴリズムまたはコードはありますか? つまり、この画像の最大の長方形は、その中に他の長方形が含まれているため、探している長方形ではありません。

私が探している長方形は空でなければなりません。(a,b) から (c,d) のような各線の始点と終点のリストがあります。結果として、長方形（x、y、w、h）または同等のリストが必要です。

一部の線には直角に交差する線があることに注意してください。たとえば、この画像の最も幅の広い長方形の一番上の線は、下に向かう交差する垂直線を持つ単一の線です。

4

4 に答える 4

2

この種の質問は、いくつかの標準Computational Geometryアルゴリズムによって大部分が解決されます。vertical sweep lineこの特定の問題に対するアルゴリズムを考えることができます。

長方形が点のペアで表されると仮定すると、(p1, p2)はp1左上隅、p2は右下隅です。p.xまた、ポイントには 2 つの属性があります (およびとしてアクセスできますp.y)。

これがアルゴリズムです。

  1. ポイントのすべてのペアを並べ替えます -O(n log n)
  2. というリストを初期化しますsweep line status。これは、これまでに遭遇したすべての長方形、つまり を保持しますalive。event queueまた、今後のイベントを保持すると呼ばれる別のリストを初期化します。これevent queueは現在、すべての四角形の開始点を保持しています。
  3. の最初の要素から開始して、イベントを処理しますevent queue。
    • イベントが の場合、start pointその長方形をsweep line status(y 座標でソートされた順序でO(log n)) に追加し (時間的に)、その右下のポイントをevent queue適切な位置 (ポイントでソートされた) に追加します (再びO(log n)時間的に)。に追加するときはsweep line status、この点が のすぐ上にある長方形の中にあるかどうかを確認する必要がありますsweep line status。内側にある場合、これは長方形ではありません。そうでない場合は、これを必要な長方形のリストに追加します。
    • イベントが終点の場合は、対応する長方形を から削除するだけsweep line statusです。

実行時間 (n 個の長方形の場合):

  • ソートにはO(n log n).
  • イベント数 = 2*n =O(n)
  • 各イベントにはO(log n)時間がかかります ( への挿入event queueと同様にsweep line status. したがって、合計はO(n log n).

したがって、O(n log n).

詳細については、Bentley–Ottmann アルゴリズムを参照してください。上記は、これを単純に変更したものです。

編集：

入力は線分であることに気付きましたが、それらは常に長方形を形成するため (質問によると)、前処理の線形トラバーサルはそれらを長方形 (点のペア) 形式に変換できます。

于 2013-04-24T18:19:08.940 に答える
2

別の表現が問題の解決に役立つと思います。例として、大きな長方形 (端にブロックがない) を考えてみましょう。4 つの一意の x 座標と y 座標があり、それらを並べ替えてインデックスを付けます。絵的には次のようになります。

ここに画像の説明を入力

座標に長方形の角がある場合は(x_i, y_j)、次のように行列に入れます。

__|_1__2__3__4_
1 | x  x  0  x
2 | x  x  0  0
3 | 0  x  x  x
4 | x  x  x  x

定義により、実空間の四角形は行列座標上の四角形です。たとえば、 に四角形があり(3,2) (3,4) (4,4), (4,3)ますが、サブ四角形が含まれているため、「基本」四角形ではありません(3,3) (3,4), (4,4), (4,3)。再帰アルゴリズムはここで簡単に確認できます。速度を上げるには、メモ化を使用して反復計算を防ぎます。

于 2013-04-24T17:36:08.713 に答える
0

すべての線は x 軸または y 軸に平行ですか? または、すべての線が平行または垂直ですか?

あなたが与えた例から、すべての線が x または y 軸に平行であると仮定しています。このような場合、行は [(a,b), (a,d)] または [(a,b), (c,b)] になります。

いずれにせよ、最初のタスクはコーナーを見つけることです。2 本の垂線が交わる点の集合です。

2 番目のタスクは、長方形を検出することです。角のすべてのペアについて、それらが長方形を形成しているかどうかを確認できます。

3 番目のタスクは、長方形の中に長方形があるかどうかを調べることです。

最初のタスクでは、ラインを垂直と水平の 2 つのセットに分ける必要があります。その後、セットの 1 つを並べ替えます。元。x 軸座標に従って垂直線を並べ替えます。次に、すべての水平線を取得し、バイナリ検索を実行してすべての交点を見つけることができます。

2 番目のタスクでは、コーナーのすべてのペアを検討し、他の 2 つのコーナーが存在するかどうかを確認します。はいの場合は、これらの 4 つのコーナーすべてを結ぶ線があるかどうかを確認します。はいの場合、長方形があります。

3 番目のタスクでは、すべての四角形を間隔ツリーに入れます。その後、2 つの長方形が重なっているかどうかを確認できます。

于 2013-04-24T17:29:17.310 に答える