algorithm - 長方形のカバー

Question

x 軸と y 軸に平行な辺を持つN 個の長方形があります。別の四角形modelがあります。モデルがN 個の長方形で完全に覆われているかどうかを判断できるアルゴリズムを作成する必要があります。

いくつかのアイデアがあります。最初に、長方形を左側で並べ替え ( O(n log n)時間で実行できます)、次に垂直方向のスイープ ラインを使用する必要があると思います。

+------------------------------------------------------------> x
|O
|                  +----+
|   +---------+    |    |
|   |        ++----+--+ |
|   |      +-++----+-+| |
|   |      | |     +-++-+
|   +------+ +-------++
|          +---------+
|
|
|
|y

青い長方形がモデルです。

まず、抽象アルゴリズムが必要です。実現に関して特別な要件はありません。四角形は、点のペア (左上と右下) として表すことができます。

これは、テストの準備のためのタスクの 1 つです。私は、最良のアルゴリズムがO(n log n)時間でこれを実行できることを知っています。

Answer 1

これが分割統治アルゴリズムです。AVERAGEのケースの複雑さは非常に良く、のようなものだと思いますO(n log MaxCoords)。最悪の場合は二次式になる可能性がありますが、そのようなテストを作成するのはかなり難しいと思います。さらに難しくするには、再帰関数呼び出しの順序をランダムにします。たぶん、@Larryが提案したことはO(n log n)平均してこれを達成することができます。

スイープラインの解決策を理解することはできませんが、私が試したテストでは、これは非常に高速です。

基本的に、青い長方形で機能する再帰関数を使用します。まず、青い長方形が他の長方形の1つで完全に覆われているかどうかを確認します。はいの場合、完了です。そうでない場合は、それを4つの象限に分割し、それらの象限で関数を再帰的に呼び出します。4つの再帰呼び出しはすべてtrueを返す必要があります。長方形を描画するC＃コードをいくつか含めています。より大きな値で動作するように変更することもできますが、その場合は描画手順を削除してください。これには永遠に時間がかかります。私はそれを100万個の長方形と、カバーされないように生成された10億個の正方形でテストしました。提供された答え（false）は、クアッドコアで約1秒かかりました。

私はこれをほとんどランダムデータでテストしましたが、正しいようです。それが判明した場合、私はこれを削除するだけではありませんが、おそらくそれはあなたを正しい道に導くでしょう。

public partial class Form1 : Form
{
    public Form1()
    {
        InitializeComponent();
    }

    List<Rectangle> Rects = new List<Rectangle>();

    private const int maxRects = 20;

    private void InitRects()
    {
        Random rand = new Random();

        for (int i = 0; i < maxRects; ++i) // Rects[0] is the model
        {
            int x = rand.Next(panel1.Width);
            int y = rand.Next(panel1.Height);

            Rects.Add(new Rectangle(new Point(x, y), new Size(rand.Next(panel1.Width - x), rand.Next(panel1.Height - y))));
        }
    }

    private void DrawRects(Graphics g)
    {
        g.DrawRectangle(Pens.Blue, Rects[0]);
        for (int i = 1; i < Rects.Count; ++i)
        {
            g.DrawRectangle(Pens.Red, Rects[i]);
        }
    }

    private bool Solve(Rectangle R)
    {
        // if there is a rectangle containing R
        for (int i = 1; i < Rects.Count; ++i)
        {
            if (Rects[i].Contains(R))
            {
                return true;
            }
        }

        if (R.Width <= 3 && R.Height <= 3)
        {
            return false;
        }

        Rectangle UpperLeft = new Rectangle(new Point(R.X, R.Y), new Size(R.Width / 2, R.Height / 2));
        Rectangle UpperRight = new Rectangle(new Point(R.X + R.Width / 2 + 1, R.Y), new Size(R.Width / 2, R.Height / 2));
        Rectangle LowerLeft = new Rectangle(new Point(R.X, R.Y + R.Height / 2 + 1), new Size(R.Width / 2, R.Height / 2));
        Rectangle LowerRight = new Rectangle(new Point(R.X + R.Width / 2 + 1, R.Y + + R.Height / 2 + 1), new Size(R.Width / 2, R.Height / 2));

        return Solve(UpperLeft) && Solve(UpperRight) && Solve(LowerLeft) && Solve(LowerRight);
    }

    private void Go_Click(object sender, EventArgs e)
    {
        Graphics g = panel1.CreateGraphics();
        panel1.Hide();
        panel1.Show();
        Rects.Clear();

        InitRects();
        DrawRects(g);

        textBox1.Text = Solve(Rects[0]).ToString(); 
    }

Answer 2

これが一般的なアルゴリズムです

1. モデル全体をカバーする長方形はありますか？
   はいの場合は完了です
2. モデルを部分的に覆っている長方形がない場合は？
   そうであれば
3. は、長方形とモデルのすべての交点の和集合であり、
   2。または3.が「いいえ」の場合、答えは「いいえ」です。それ以外の場合は「はい」です。

ここで問題となるのは、上記を効率的に行う方法です。上記はすべてのポリゴンに対して単一のループで実行できるため、O（n）時間を調べていると思います。

複数のモデルをテストする効率的なアルゴリズムを作成する必要がある場合、または（データの準備を犠牲にして）可能な限り最速の回答を得るために最適化する必要がある場合は、長方形が交差するかどうかの質問にすばやく回答できる構造を探しています（または含む）長方形。

たとえばkd-treesを使用する場合、これはO（log n）時間で答えられると思いますが、このアルゴリズムで重要な変数は、見つかった長方形の数kでもあります。最終的にはO（k + log n）のようになり、モデルがカバーされているかどうかをテストするために結合部分を実行する必要もあります。

私の推測では、和集合はO（k log k）で計算できるので、kが小さい場合はO（log n）を見ており、kがnに匹敵する場合はO（k log k）である必要があります。

この質問も参照してください。

編集：交差点と和集合の複雑さに対応して。

詳細には、k<<nまたはkがnに匹敵するかどうかに応じて2つのシナリオがあります。

a）k << nの場合、共通部分/和集合の多項式の複雑さを仮定すると（ここで、推測O（k log k）を放棄します）、次のようになります。

• （長方形の）kdインデックスツリーの範囲を見つけるためにnをログに記録します。
• その「ブランチ」内のすべての長方形を取得するためのkステップ、
• f（k）交差と和集合を計算するための多項式時間

合計はO（k + log n + f（k））です。これは、大きなOが最も速く成長する項にのみ依存するため、O（log n）に直接等しくなります。

この場合、アルゴリズムのより重要な部分はポリゴンを見つけることです。

b）nに匹敵するkの場合、交差アルゴリズムと和集合アルゴリズムの複雑さを調べる必要があります（RDBMが選択性に応じてインデックスを使用する方法やテーブルスキャンを実行する方法については、ここで類似していることに注意してください。これも同様の選択です。ここにあるものに）。
kが十分に大きい場合、アルゴリズムは、長方形と交差する長方形を見つけるためのアルゴリズムではなくなり、ポリゴンの和集合を計算するためのアルゴリズムになります。

しかし、kdツリーはセグメントの共通部分（結合を構築するために必要）を見つけるのにも役立つと思います。したがって、アルゴリズムのこの部分でさえ、k^2時間を必要としない可能性があります。この時点で、組合の面積を計算するための効率的なアルゴリズムを調査します。

Answer 3

O(N^2)提起される「ラスター」アプローチに似た些細なアプローチがあります。2Nすべての長方形は軸に平行であるため、最大で明確なx次元とy次元しか存在できません。すべてのxとyを並べ替えて、次のように再マップします x_i -> i。これで、単純なアルゴリズム2N x 2Nを簡単に使用できるマトリックスができました。O(N^2)

Answer 4

私はそれについて考えてきましたが、ようやくスイープラインの@algorithmist意味を理解したと思います. ただし、操作が存在するということは、次のことを意味します。sorting

• O(n log n)平均して
• O(n**2)最悪の場合

スイープライン

まず、並べ替えが必要sweep lineです。これは、順序付けられたセットのウォークから構成されるためです。

この順序付けられたセットは、との間にある限り、各 のtopとbottom行を特徴とします。これにより、スペースが (最大でも)水平方向のストリップに分割されます。redtopbottombluen*2

stripここで、各で の全体がカバーされていることを確認する必要があります。blueこの操作は、複雑さを超えることはできませんO(log n)。(ストリップごとに) カバーされた間隔のリストがあれば、これを実行できます。これが「イベント」の@algorithmist話です

このイベントを処理するために、以下で説明するバイナリ ツリーを使用します。このバイナリ ツリーは、正確なO(log n)操作で四角形の追加または削除を処理し、ツリーによってカバーされる最も右の間隔を生成します。これを使用して、ストリップblueがカバーされているかどうかを判断します。

二分木

まず、red長方形にインデックスを付けます。この関数を使用してそれらを並べ替えます。

def __lt__(lhs, rhs):
  return (lhs.left <  rhs.left)
      or (lhs.left == rhs.left and lhs.right < rhs.right)

次に、専用のバイナリ ツリーを作成します。

• N葉があり、それぞれが長方形redを表し、その存在または不在を示します。それらはインデックスに従って並べられています。
• 各中間ノードには、その子によってカバーされる最も右側の間隔が値として含まれます。

バグ「コードブロックはリストに従うことができません」の処理：

class Node:
  def __init__(self):
    self.interval = []
    self.left  = None
    self.right = None

ここで、2 つの可能性があります。子が と をカバーしている[a,b]とし[c,d]ます。

• の場合c <= b、ノードが保持されます[a,d]
• そうでなければそれは保持します[c,d]

なぜ機能するのですか？4 つのリーフを使用した例を見てみましょう。

        _ [1,9] _
       /         \
   [1,7]         [6,9] <-- Special node merge
   /   \         /   \
  /     \       /     \
[1,3] [2,7]   [3,5] [6,9]

[3,5]右端の間隔ではないため、特別なノードは無視されます。理由は、長方形が順序付けられているためです。

• の右側の四角形は、欠落している間隔[6,9]をカバーしません。[5,6]6
• [3,5]begin beforeの左側にある四角形は3、欠落している部分をカバーする場合、とにかく[5,6]カバーします[3,5]

ルートは、カバーされる間隔の正確なセットを示さない場合があります。カバーされる一番右の間隔のみです。ただし、blue完全に覆われているかどうかを判断するだけで十分です。

このツリーで使用できる操作は 2 つあります。

• 長方形を存在としてマークする
• 長方形を不在としてマークする

それぞれが似ています：

• 長方形がすでにこの状態にある場合は、何もしません
• それ以外の場合は、その状態を切り替えてから、その親間隔を更新します (再帰的に、ルートまで)

再帰ビットはO(log n). これは、平衡二分木の古典的な特性です。そして、それが完了すると、ルートによってカバーされる最も右側の間隔が得られます。これは、blueセグメントが完全にカバーされているかどうかを判断するのに十分です.

複雑

アルゴリズムの複雑さは単純です。

• O(n)イベントがあります
• 各イベントはO(log n)

これによりO(n log n)、コア部分が得られます。

sortただし、次の 2 つの操作があることも忘れてはなりません。

• イベントを分類するための 1 つ (スイープ ライン用)
• もう 1 つは四角形を分類します (バイナリ ツリー用)。

それぞれO(n log n)がaverageO(n**2)を受け取りますが、使用される並べ替えアルゴリズムによっては、最悪の場合に縮退する可能性があります。

Answer 5

あなたはスイープラインで正しい軌道に乗っています. 概念的には、モデルとスイープ ラインの交点が他の長方形によってカバーされていないことを検出したいと考えています。高レベルのテンプレートでは、各長方形を「左端」イベントと「右端」イベントに分割し、イベントを x 座標で並べ替えます (長方形が閉じている場合は左を右に、開いている場合は左を右に置きます)。次に、各イベントを O(log n) 時間で処理します。これは基本的に宿題なので、これ以上は言いません。

Answer 6

さて、この問題について考えているので、夜も眠れないようです...しかし、平均的なケースでは、最終的にO（n log n）の解決策を得たようです（ただし、病理学的な問題が発生する可能性は低くなりますと比較した入力)。@lVlad

私たちは皆、分割統治法を知っています。確実にO(n log n)使用するために、通常は次の 2 つのポイントに焦点を当てています。

• 分割とマージは_O(n)
• C > 1 が存在し、各ステップで部分問題のサイズが係数 C で縮小されます (問題全体で一定)。

これらの制約を念頭に置いて、次のアルゴリズムを作成しました。これは を連想させるqsortため、同じ落とし穴 (つまり、フラクタル入力) に悩まされています。

アルゴリズム

1. クリッピングred:と交差するa の部分のみを考慮しblue、それらは重複を削除するために HashSet に挿入されます -->O(n)
2. ピボット選択: 詳細は後述 -->O(n)
3. パーティション: ピボットを作成したら、スペースを 3 ^dゾーンに細分化します。そのうちの 1 つがピボットで、d はディメンションです (セグメントの場合は d = 1、長方形の場合は 2、立方体の場合は 3 など...)。
4. Repartitionred :クリッピング手法を適用してパーティションに入れます。与えられredたものが異なるパーティションにいくつかのチャンクを与えることになるかもしれないことに注意してください
5. 再帰: 各パーティションに (ステップ 2 から) 再帰的に適用します。最も人口の少ないパーティションから始めて、カバーされなくなるとすぐに停止します。

ピボット選択はアルゴリズムの要であり、パーティションの調整が適切でない場合、必要な複雑さを実現できません。また、 で実行する必要がありますO(n)。これまでのところ、2 つの提案があります。

• Maximum Area: 後でパーティションの面積が最小になることを意味するため、面積が最大の長方形を使用しますが、切り札になりやすいという欠点があります。
• Median of 3: qsort に基づいて、3 つの要素を選択し、中央値 (3 つの中心の重心に近い中心を持つもの) を選択します。

私はそれらを次のように混同することを提案します:

• 面積が最大の 3 つの要素をピックアップし、中央値を選択して、ピボットで使用します
• 再分割後、分割の 1 つに N/C (カスタマイズする) 要素を超える要素が取り込まれていることが判明した場合は、ランダムに 3 つの要素を選択し、中央値を選択して、再分割を行います (ここではチェックしません)。

実装のもう 1 つの側面は、再帰の末尾です。qsortアルゴリズムが small に対して非効率的である可能性が高いようnです。1 まで行く代わりに、次のintrosortトリックを使用することを提案します。12nよりも小さい場合は、代わりに次のアルゴリズムを使用します。

• 各軸について、それぞれredを軸に射影し (エッジのみ)、それらを並べ替えます (ala introsort)
• ^{これは n d}ゾーンのラスターを定義し、それぞれがカバーされていることを確認します

次元にとらわれない

アルゴリズムは、平均 O(n log n)で、同じ漸近的複雑さを持つ任意の次元に適用できるように正式に定義されています。これにより、次元 1 でテストして病理学的入力を特定する機会が得られます。

病理学的入力

モデル化されているものと同様qsortに、階乗入力に敏感です。階乗入力とは、次のことを意味します。

1.......6...9.11.13

間隔の平均を選択するときはいつでも、その片側にすべての要素があります。

このような入力では、3 の中央値を選択しても、非常に良いカットが得られる可能性は低いです。

編集：

@lVlad少しあいまいであると述べたように、少しスキームを使用してパーティションのアイデアを示します。

+----------------+----+---------+
|       1        | 2  |   3     |
+----------------+----+---------+
|       8        | P  |   4     |
+----------------+----+---------+
|       7        | 6  |   5     |
+----------------+----+---------+

これで、カバレッジをチェックする長方形が 9 つのサブ長方形に分割されました。P は無視します。これがピボットです。

redここで、各サブ長方形が未満で覆われることを本当に望んでいNます。ピボットは中心の重心として選択されます。したがって、「ランダムな」選択が正しい場合red、ピボットの各方向に約 s 個の中心があることを意味します。

いくつかの特別な構成により、1 つのステップでほとんどゲインが得られない可能性があるため (たとえば、すべての長方形の中心が同じで、小さい方を選択しただけです)、混乱が生じるため、次のステップは次のようになります。異なる。

私はコンピューター科学者ではなくエンジニアであり、私の数学は遅れています...

Answer 7

OK、私は十分な質問をしました。ここに答えがあります...

データがラスターとして表される場合、1 つのアルゴリズムは自明です。

1. モデル (つまり、青) の四角形を表すブール配列を作成します。すべての要素を FALSE に設定します (「対象外」を表します)。
2. 赤の四角形ごとに (青と重ならないものは無視してください)、配列のすべての要素が赤の四角形内にある場合はそれらを TRUE に設定します。
3. 最後に、配列のすべての要素が TRUE に設定されているかどうかを確認します。

データがベクトルの場合は、もう少し複雑です。最初に、2 つの長方形の交点 (存在する場合) を表す長方形を返す関数を定義します。これは簡単です。次に進みます：

1. 青色の四角形と同じになるように初期化される「UnCoveredRectangle」という変数を作成します。

2. 繰り返しますが、青の長方形と交差する赤の長方形だけを気にしてください。赤の四角形ごとに、四角形と UnCoveredRectangle の交点を計算します。交差点は、次のいずれかの状況になります。

   2.1 交点は UnCoveredRectangle に等しい。仕事は終わった。

   2.2 交点は、CoveredRectangle から四角形のチャンクを「食い込み」ます。残りの UnCoveredRectangle は、長方形、L 字型のピース、または U 字型のピースのいずれかになります。長方形自体の場合は、UnCoveredRectangle を残りの長方形に設定し、手順 2 に進みます。UnCoveredRectangle が L 字型または U 字型の場合は、2 つまたは 3 つの長方形に分割し、手順 2 から再帰します。

3. UnCoveredRectangle (の一部) の領域が 0 に送信される前に赤い四角形を使い果たした場合は、完了です。

OK、このアルゴリズムの複雑さについての手がかりはありませんが、長方形の数が膨大でない限り、あまり心配していません. そして、私は多くの詳細を省略しました。そして、@den のように素敵な図を描くことはできないので、自分で図を描く必要があります。

Answer 8

ラスター化を使用せずに、つまり純粋な数値のみを使用してこれを行う方法を次に示します。

注: これは O(n log n) ではなく、O(n^2) に似ています。ただし、これは解決策です。それが答えであるかどうか、おそらく O(n log n) が要件である場合はそうではありません。

1. 左端と右端のすべての一意の X 座標のリストを作成します (同じリスト内)。
2. このリストを作成するときは、座標ごとに長方形のリストも関連付け、このリストで、リストが関連付けられている X 座標が長方形の左端または右端のどちらであるかを示します。
3. 左から右に昇順になるように座標のリストを並べ替えます
4. 長方形の新しいリストを作成します。最初は空です
5. 座標のリストを実行し、関連する長方形のリストを処理します
6. 関連付けられたリスト内の、座標が左端であると示されているすべての長方形を、4 で作成したリストに追加する必要があります。
7. 座標を右端とするすべての長方形を削除する必要があります。
8. 追加と削除の順序は、実際には逆の順序で行う必要があります。最初に右端の長方形を削除し、次にすべての左端の長方形を追加します。
9. ここで、4 で作成したリストから長方形を削除する前に、それらを処理したいと考えています。それらを「サブ長方形」として処理して処理します。それらの「新しい」左端座標は、ループの前の反復 (5) で処理した X 座標であり、新しい右端は現在処理中の X 座標です。
10. アルゴリズムの出力は、座標ペア (左右の 2 つの X 座標) のコレクションであり、各ペアには関連する長方形のリスト (垂直ストリップ) があります。

したがって、出力は次のようになります。

1. X=1..2、長方形=A
2. X=2..3、Rects=A、B
3. X=3..4、Rects=A、B、C
4. X=4..5、Rects=A、C
5. X=5..6、長方形=C

ここまでの流れを説明します

+-------------------+
|A                  |
|        +----------+-----+
|        |C         |     |
|  +-----+----+     |     |
|  |B    |    |     |     |
|  |     +----+-----+-----+
|  |          |     |
+--+----------+-----+
   |          |
   +----------+

^  ^     ^    ^     ^     ^
1  2     3    4     5     6  <-- X-coordinates

関連する長方形:

1. 左：A、右：（なし）
2. 左：B、右：（なし）
3. 左：C、右：（なし）
4. 左：（なし）、右：B
5. 左：（なし）、右：A
6. 左：（なし）、右：C

空のリスト を作成しL=[]、座標と関連する四角形の処理を開始します。

X=1

リストは空です。処理するものはありません。削除するものはありません A を追加: L=[ A ]

X=2

リストには四角形が含まれ、左端が X=1、右端が X=2 (これまでに処理した 2 つの座標) の四角形としてリストを処理し、元の上部と下部の座標を使用します。削除するものはありません。B を追加: L=[ A, B ]

X=3

リストには四角形が含まれ、リスト (A と B の両方) を同じ方法で処理し、それらを一時的に左右の座標を X=2 と X=3 として扱い、元の上下の座標を使用します。削除するものはありません C を追加: L=[ A, B, C ]

X=4

上記と同じ方法で 3 つの長方形を処理します。一時的な左右の座標は X=3 と X=4 B を削除: L=[A, C ] 追加するものはありません

X=5 および X=6

これらをまったく同じ方法で処理します。

これは、次のような長方形の「ストリップ」になることを意味します (ストリップであることを明確に示すために少し引き離していますが、元の図のように連続して並んで配置されています)。

+--+ +-----+ +----+ ------+
|A | |     | |    | |     |
|  | |     | +----+ +-----+ +-----+
|  | |     | |C   | |     | |     |
|  | +-----| +----+ |     | |     |
|  | |B    | |    | |     | |     |
|  | |     | +----+ +-----| +-----+
|  | |     | |    | |     |
+--+ +-----+ +----+ +-----+
     |     | |    |
     +-----+ +----+
^  ^ ^     ^ ^    ^ ^     ^ ^     ^
1  2 2     3 3    4 4     5 5     6

わかりました。これで、座標ペアのコレクションである出力が得られました。各ペアには、関連付けられた四角形のリストがあります。

今、私たちはトリックをします。垂直ストリップをまったく同じ方法で処理しますが、今回は区切り文字として Y 座標を使用します。上記の 3 と 4 の間のストリップを処理しましょう。ストリップの左右の座標は 3 と 4 であることに注意してください。

ストリップは次のようになります。

^     +----+ <-- 1
A     |    |
|   ^ +----+ <-- 2
|   C |    |
| ^ | +----+ <-- 3
| B | |    |
| | V +----+ <-- 4
| |   |    |
V |   +----+ <-- 5
  |   |    |
  V   +----+ <-- 6

長方形を含む座標のリスト:

1. 上=A、下=(なし)
2. 上=C、下=(なし)
3. 上=B、下=(なし)
4. 上=(なし)、下=C
5. 上=(なし)、下=A
6. 上=(なし)、下=B

新しい空のリスト L=[]

座標を処理します。

Y=1

処理するものなし (L=[]) リストに A を追加、L=[ A ]

Y=2

一時的に Y=1 と 2 の上部座標と下部座標を持つプロセス A (また、X=3 と 4 の一時的な左右座標もあることに注意してください) C、L=[ A, C ] を追加します。

Y=3

プロセス A と C、両方とも (3, 2)-(4, 3) の一時座標を持ち、B を追加、L=[ A, B, C ]

Y=4

プロセス A、B、および C、すべて (3, 3)-(4, 4) の座標を持つ C を削除、L=[ A, B ]

Y=5

プロセス A と B、座標 (3, 4)-(4, 5) A を削除、L=[ B ]

Y=6

プロセス B、座標 (3, 5)-(4, 6)

最終出力:

四角形が関連付けられた Y 座標のペア (一時的に新しい X 座標も取得しています):

• (3, 1)-(4, 2) - A
• (3, 2)-(4, 3) - A, C
• (3, 3)-(4, 4) - A、B、C
• (3, 4)-(4, 5) - A, B
• (3, 5)-(4, 6) - B

ここで、次の質問をしたいとします: B は、他のすべての長方形の組み合わせによって完全に覆われていますか?

答えは次のように計算できます。

1. 上記の最終リストのすべての長方形をループします
2. B が関連付けられた四角形の一部でない場合、この四角形を無視します
3. 座標に関連付けられた元の長方形が他にある場合、B のこの部分はその/それらの長方形によってカバーされます。
4. 座標に関連付けられた元の四角形が他にない場合、B のこの部分はカバーされません。

上記の例では、最後のリストの 3 番目と 4 番目の四角形に B が含まれていますが、他の四角形も含まれているため、B のこれらの部分がカバーされていますが、リストの最後の四角形にも B が含まれていますが、他の四角形は含まれていません。したがって、この部分はカバーされていません。

元の図によると、最終結果には次のような四角形が含まれます (各内の文字は、元の四角形がこの新しい四角形に関連付けられていることを示します)。

+--+-----+----+-----+
|A |A    |A   |A    |
|  |     +----+-----+-----+
|  |     |AC  |AC   |C    |
|  +-----+----+     |     |
|  |AB   |ABC |     |     |
|  |     +----+-----+-----+
|  |     |AB  |A    |
+--+-----+----+-----+
   |B    |B   |
   +-----+----+

元の図をもう一度見てみると、上記のアルゴリズムで B が含まれているが、他の四角形が含まれていないことが判明した部分に網掛けが施されています。

+-------------------+
|A                  |
|        +----------+-----+
|        |C         |     |
|  +-----+----+     |     |
|  |B    |    |     |     |
|  |     +----+-----+-----+
|  |          |     |
+--+-----+----+-----+
   |#####|####|
   +-----+----+

中央の垂直バーは、垂直ストリップが作成された方法により、その位置で分割された 2 つの長方形としてパーツが返されることを示しています。

ここで自分自身を理解してくれることを真剣に願っています。座標のリストの各実行の実装に役立つコードがいくつかありますが、ここでは真夜中過ぎの 01:21 であり、就寝しますが、実際のコードを確認したい場合はコメントを残してください。 .

または、それを自分で実装するのは素晴らしい練習になるでしょう:)

問題のメソッドを含むクラスへのリンクは次のとおりです: RangeExtensions.cs。

メソッドはメソッドですSlice。ページを検索してください。問題の型である Range は、基本的にある値から別の値への範囲であるため、上記のアルゴリズムに加えて、データの構築と保守が少し必要です。

Answer 9

あなたが探しているものを知るのは難しいですが、Rツリーが機能するように思えますか?

Answer 10

O(n lg n) でスイープラインを機能させる方法は次のとおりです。BST がどのように機能するかのトリッキーな部分に焦点を当てます。

現在のスイープラインと交差する各長方形の始点と終点を含むバランスの取れた BST を維持します。BST の各ノードには、minOverlap と deltaOverlap の 2 つの補助フィールドが含まれています。通常、フィールド minOverlap には、そのノードのサブツリーがカバーする間隔内の任意の点と重なる長方形の最小数が格納されます。ただし、一部のノードでは値がわずかにずれています。ルートまでのすべてのノードの minOverlap と deltaOverlap の合計が、ノードのサブツリー内の領域と重なる長方形の真の最小数を持つという不変条件を維持します。

四角形の開始ノードを挿入するときは、常にリーフに挿入します (場合によってはリバランスします)。挿入パスをたどると、ゼロ以外の deltaOverlap 値が挿入されたノードのアクセス パスの子に「プッシュ ダウン」され、アクセス パス上のノードの minOverlap が更新されます。次に、すべてのノードをツリーに挿入されたノードの「右側」に O(lg n) 時間でインクリメントする必要があります。これは、挿入されたノードのすべての正しい祖先の minOverlap フィールドをインクリメントし、挿入されたノードの正しい先祖のすべての正しい子の deltaOverlap をインクリメントすることによって達成されます。長方形を終了するノードの挿入、および点の削除についても、同様のプロセスが実行されます。ローテーションに関係するノードのフィールドのみを変更することで、リバランス操作を実行できます。スイープの各ポイントでルートをチェックして、minOverlap が 0 かどうかを確認するだけです。

座標の重複などの処理の詳細は省きました (簡単な解決策の 1 つは、同じ座標の閉じた四角形ノードの前に、開いた四角形ノードを並べることです)。

Answer 11

長方形の和集合の領域O(nlogn)に対する通常の最悪の場合のアルゴリズムを知っていますか?

ここで行う必要があるのは、2 つの領域を計算することだけです。

1. N 個の長方形の面積
2. N 個の長方形とモデルの面積

これらの面積が等しい場合、モデルは完全に覆われていますが、そうでない場合はそうではありません。

Answer 12

これは、メモリを使用する O(n lg n) ランタイム アプローチです。

例を使用します。

「モデル」長方形を含むシーンのサブパーツのみに関心があります。この例では、「モデル」長方形は1,1 -> 6,6

   1 2 3 4 5 6

1 +---+---+
   | | | |   
2 + A +---+---+
   | | | | ビ |
3 + + +---+---+
   | | | | | | | | | |
4 +---+---+---+---+ +
               | | | |
5 + C +
               | | | |
6 +---+---+

1)モデル長方形の境界内(左右両方) にあるすべての x 座標をリストに収集し、それを並べ替えて重複を削除します

1 3 4 5 6

2)モデル長方形の境界内(上と下の両方) にあるすべての y 座標をリストに収集し、それを並べ替えて重複を削除します。

1 2 3 4 6

3) 一意の x 座標間のギャップ数 * 一意の y 座標間のギャップ数で 2D 配列を作成します。これはセルごとに 1 ビットを使用でき、効率的な表現のために C++ STL の bit_vector() を使用することを検討できます。

4*4

4) すべての長方形をこのグリッドにペイントし、それが発生するセルをペイントします。

   1 3 4 5 6

1 +---+
   | | 1 | 0 0 0
2 +---+---+---+
   | | 1 | 1 | 1 | 0
3 +---+---+---+---+
   | | 1 | 1 | 2 | 1 |
4 +---+---+---+---+
     0 0 | 1 | 1 |
6 +---+---+

5) ペイントされていないセルがある場合、モデルが完全に遮られていないことがわかります (または、テストしているものは何でも)。

収集座標と描画ステップは O(n) であり、座標の並べ替えは O(n lg n) です。

これは、私の回答の 1 つから改作されています: What is an Efficient algorithm to find Area of​​ Overlapping Rectangles