このページの次の疑似コードでBentley–Ottmannを試すことができます
Bentley-Ottmann アルゴリズム
Bentley-Ottmann アルゴリズムの入力は線分 Li の集合 OMEGA={Li} であり、その出力は交点の集合 LAMBDA={Ij} になります。このアルゴリズムは、「スイープ ライン」SL という別のラインを持ち、コレクション OMEGA をスイープし、個々のセグメント Li を通過するときに情報を収集する操作として視覚化できるため、「スイープ ライン アルゴリズム」と呼ばれます。SL の位置ごとに収集される情報は、基本的に、現在 SL と交差している OMEGA 内のすべてのセグメントの順序付きリストです。この情報を保持するデータ構造は、「スイープ ライン」とも呼ばれます。このクラス構造は、交差を検出すると、交差も検出して出力します。交差点を発見するプロセスは、アルゴリズムとその効率の核心です。
スイープ ロジックを実装するには、最初に OMEGA のセグメントを線形に並べ替えて、SL がセグメントに遭遇する順序を決定する必要があります。つまり、すべてのセグメント Li の端点 {Ei0,Ei1}i=1,n を順序付けする必要があるため、SL が OMEGA の各セグメントとの交差を開始および停止するタイミングを検出できます。伝統的に、エンドポイントは、最初に x を増やし、次に y 座標値を増やすことによって順序付けられますが、線形の順序でも構いません (最初に y を減らし、次に x を増やすことを好む作成者もいます)。従来の順序では、図に示すように、スイープ ラインは垂直で、各セグメントに遭遇すると左から右に移動します。
ピックスイープライン
アルゴリズムの任意の時点で、スイープ ライン SL は、一方の端点が左 (または上) にあり、もう一方の端点が右にあるセグメントのみと交差します。SL データ構造は、これらのセグメントの動的リストを次のように保持します。(1) セグメントの左端が検出されたときにセグメントを追加し、(2) セグメントの右端が検出されたときにセグメントを削除します。さらに、SL はセグメントのリストを「上-下」関係で順序付けます。したがって、セグメントを追加または削除するには、リスト内のその位置を決定する必要があります。これは、リスト内の現在のセグメントの最悪の場合の O(log-n) 二分探索によって行うことができます。さらに、セグメントの追加または削除以外に、リスト構造を変更する別のイベントがあります。つまり、2 つのセグメントが交差するたびに、順序付けられたリスト内の位置を交換する必要があります。2 つのセグメントを考えると、
これらすべてを整理するために、アルゴリズムは順序付けられた「イベント キュー」EQ を維持し、その要素によって SL セグメント リストが変更されます。最初に、EQ はすべてのセグメント エンドポイントのスイープ順リストに設定されます。ただし、セグメント間の交差が検出されると、それらはエンドポイントに使用されたのと同じスイープ順序で EQ にも追加されます。ただし、重複する交差がイベント キューに挿入されないようにテストする必要があります。上の図の例は、これがどのように発生するかを示しています。イベント 2 では、セグメント S1 と S2 により、交差 I12 が計算され、キューに入れられます。次に、イベント 3 で、セグメント S3 が S1 と S2 の間に来て分離します。次に、イベント 4 で、S1 と S3 がスイープ ライン上の位置を交換し、S1 が再び S2 の隣に置かれ、I12 が再度計算されます。ただし、交差点ごとに 1 つのイベントしか存在できません。I12 を 2 回キューに入れることはできません。そのため、交差がキューに入れられるとき、キュー内で潜在的な x ソートされた位置を見つけ、それがまだそこにないことを確認する必要があります。任意の 2 つのセグメントの交点は多くても 1 つであるため、交点をセグメントの識別子でラベル付けするだけで、交点を一意に識別することができます。これらすべての結果として、イベント キューの最大サイズ = 2n+k.le.2n+n2 となり、挿入または削除は O(log(2n+n2)) = O(log-n) で実行できます。 ) 二分探索。
しかし、これらすべてが、セグメントの交差の完全なセットを効率的に見つけることとどのような関係があるのでしょうか? セグメントが SL セグメント リストに順次追加されると、他の適格なセグメントとの可能な交差が決定されます。有効な交差点が見つかると、イベント キューに挿入されます。さらに、EQ の交差イベントがスイープ中に処理されると、SL リストの再順序付けが発生し、交差も出力リスト LAMBDA に追加されます。最終的に、すべてのイベントが処理されると、LAMBDA にはすべての交差点の順序付けられた完全なセットが含まれます。
ただし、アルゴリズムの心臓部である 1 つの重要な詳細については、まだ説明する必要があります。つまり、有効な交差をどのように計算するのでしょうか? 明らかに、2 つのセグメントは、ある時点でスイープ ライン上で同時に発生する場合にのみ交差できます。しかし、これだけではアルゴリズムを効率的にするには不十分です。重要な点は、交差する 2 つのセグメントは、スイープ ライン上ですぐ上下に隣接している必要があるということです。したがって、考えられる交差を計算する必要がある制限されたケースはわずかです。
セグメントが SL リストに追加されると、それが上下の隣接セグメントと交差するかどうかを判断します。
セグメントが SL リストから削除されると、以前の上下の隣接が新しい隣接としてまとめられます。したがって、それらの可能な交点を決定する必要があります。
交差イベントでは、2 つのセグメントが SL リスト内の位置を切り替え、それらの新しい隣接セグメント (それぞれに 1 つ) との交差を決定する必要があります。これは、EQ の任意の 1 つのイベント (エンドポイントまたは交差点) の処理について、行う必要がある交差点の決定が多くても 2 つあることを意味します。
1 つの詳細が残っています。つまり、SL 構造からセグメントを追加、検索、交換、および削除するのに必要な時間です。これを行うには、SL をバランスの取れたバイナリ ツリー (AVL、2-3、または赤黒ツリーなど) として実装できます。 SL リストの最大サイズです。したがって、(2n+k) 個のイベントのそれぞれには、最悪でも O(log-n) 個の処理が必要になります。初期ソートとイベント処理を合計すると、アルゴリズムの効率は O(nlog-n)+O((2n+k)log-n)=O((n+k)log-n) になります。
擬似コード: Bentley-Ottmann アルゴリズム
これらすべてをまとめると、Bentley-Ottmann アルゴリズムを実装するための最上位ロジックは、次の疑似コードで与えられます。
Initialize event queue EQ = all segment endpoints;
Sort EQ by increasing x and y;
Initialize sweep line SL to be empty;
Initialize output intersection list IL to be empty;
While (EQ is nonempty) {
Let E = the next event from EQ;
If (E is a left endpoint) {
Let segE = E's segment;
Add segE to SL;
Let segA = the segment Above segE in SL;
Let segB = the segment Below segE in SL;
If (I = Intersect( segE with segA) exists)
Insert I into EQ;
If (I = Intersect( segE with segB) exists)
Insert I into EQ;
}
Else If (E is a right endpoint) {
Let segE = E's segment;
Let segA = the segment Above segE in SL;
Let segB = the segment Below segE in SL;
Delete segE from SL;
If (I = Intersect( segA with segB) exists)
If (I is not in EQ already)
Insert I into EQ;
}
Else { // E is an intersection event
Add E’s intersect point to the output list IL;
Let segE1 above segE2 be E's intersecting segments in SL;
Swap their positions so that segE2 is now above segE1;
Let segA = the segment above segE2 in SL;
Let segB = the segment below segE1 in SL;
If (I = Intersect(segE2 with segA) exists)
If (I is not in EQ already)
Insert I into EQ;
If (I = Intersect(segE1 with segB) exists)
If (I is not in EQ already)
Insert I into EQ;
}
remove E from EQ;
}
return IL;
}
このルーチンは、すべての交点の完全な順序付きリストを出力します。
