1. 序章

このチュートリアルでは、長方形の重なりの問題を解決するための手法に焦点を当てています。 私たちの目標は、与えられた数の長方形の重なり合う領域を計算することです。 例として、マイクロプロセッサ設計の分野でのアプリケーションがあります。 マイクロプロセッサの設計では、特定の領域とワイヤが交差することは許可されていないか、特定の程度だけ交差することが許可されています。

2. 問題の説明

まず、問題は非常に簡単に思えます。長方形の数が有限であり、それらのオーバーラップを計算したい。 さらに、長方形には、-軸または-軸に平行な辺があります。 目標は、交差のジオメトリを無視して、長方形が交差する領域を単純に計算することです。

 

この例では、3つの長方形が表示されています。 赤と青だけが重なっています。 さらに、それらの共有領域である1を計算します。

3. 簡単な解決策

簡単な解決策は、2つの長方形を一度に比較して、どの領域が重なっているかを確認することです。

3.1. 理論的アプローチ

私たちは彼らの側から間隔を作ることによってこれを実現します。 1つはx方向に、もう1つはy方向にあります。これは、長方形ごとに2つの間隔を意味します。 次に、2つのx方向の間隔とy方向の間隔の交点を計算します。 2つの交差点を組み合わせると、長方形のオーバーラップの2つの辺が作成されます。

3.2. 実装

私たちの方法は非常に単純な原理に従いますが、同様に非常にコストがかかります。 前に説明した別のアルゴリズムは、長方形が重なっているかどうかをチェックするだけです。

4. ラインスイープ方式

ラインスイープアルゴリズムは垂直線を使用します座標系で左から右に移動するe。

4.1. アルゴリズム

移動中に、x方向のみで長方形の開始点を収集します。 次に、対応する長方形を1次元のデータ構造に追加します。 これは、データ構造内の長方形のいずれかと交差するかどうかを確認するために使用されます。 長方形の右端を垂直線が「スイープ」すると、データ構造から長方形が削除されます。 したがって、一度に相互に比較する長方形の数を減らします。

4.2. 例–長方形の追加

アルゴリズムをよりよく理解するために、次の簡単な例を見てみましょう。

写真でわかるように、4本の線はラインスイープの4つのステップを表しています。 最初のステップ（A）は、青い長方形のエッジを間隔のリストに追加することです。 さらに、エッジにも長方形への参照が含まれていることが重要です。 次に、2番目のステップ（B）で、赤い長方形のエッジをリストに追加します。 それを追加している間、私たちはリストにすでにエッジがあることに気づきます。 したがって、2つの長方形を相互に比較し、存在する場合はそれらのオーバーラップを計算します。

4.3. 例–長方形の削除

さらに、3番目のステップ（C）で、青い間隔の終点に遭遇します。 これは単に、リストからそのエッジを削除することを意味します。 最後に（D）、最後のステップで赤い長方形のエッジを使用して同じことを行います。

4.4. 実装

ここでも、forループのセクション3の関数「Compare」を使用します。

5. 最適化と複雑さ

最初の方法では、すべての長方形を相互に比較します。 したがって、アルゴリズムには複雑さがあります。ここで、は長方形の数です。 ラインスイープ法を使用する場合でも、時間の複雑さが残ります。 では、複雑さをさらに軽減するために何ができるでしょうか。

「スイープ」をさらに単純化することはできないため、長方形を保存するデータ構造を最適化することが唯一のチャンスです。 この目的のために、二分探索木（BST）を使用して、スイープによって取得した間隔を保存します。 いわゆる区間木。 区間木を使用すると、の長方形を挿入および削除できます。 このためには、擬似コードのの基になるデータ構造を変更するだけです。 これは、長方形の数であるという複雑さにつながります。

6. 結論

この記事では、長方形のセットのオーバーラップを計算する2つの方法について説明しました。 この問題に最初に遭遇したとき、私たちは非常に単純ですがコストのかかるアルゴリズムを使用しました。 2番目のアプローチでは、「スイープ」の方法を使用して、2次元の問題を1次元の問題に減らします。 さらに、インターバルツリーを使用して複雑さを軽減しました。