geometry - 線のすべての交点を含む最小の長方形

Question

一連の線のすべての交点を見つけ、O(n log n) 時間ですべての交点を含む最小の四角形を計算するアルゴリズムを見つけようとしています。これまでのところ、双対性と凸包に関係していると推測していますが、実際にこの問題を解決するのにどのように役立つかについてはちょっと固執しています。

誰かがこれについて考えているなら、私に知らせてください。ありがとう ：）

Answer 1

三角形の 3 つの交点を最小限に制限するボックス B[0] から始めましょう。

三角形が見つからない場合は、個別に処理できる次の特殊なケースのいずれかになります。

1. すべての線は平行です。
2. すべての交点は 1 本の線に沿っています。これは、1 本を除くすべての線が平行である場合に発生する可能性があります。
3. すべての線は 1 点で交差します。

したがって、これらのケースは詳細として無視し、三角形を見つけることができ、それを見つけることでアルゴリズムにあまり時間がかからないと仮定しましょう。

フェーズ 1 - ボックスを拡張して、各ラインからの交点を 1 つ含めます。

1. 最初の三角形を形成する 3 つの線にタグを付けます。
2. タグの付いていない線を 1 つ選択し、タグの付いた線との交点 P を見つけます。相互に平行でないタグ付きラインが少なくとも 3 つあるため、これは常に可能です。
3. P を含むようにボックスを拡張します。
4. すべての線がタグ付けされるまで 2 から繰り返します。つまり、すべての線がボックス内に少なくとも 1 つの交点を持ちます。

結果のボックスを B[0] と呼びます。

フェーズ 2 - 線がボックスの外側に交差するかどうかを検出します。

重要な観察事項は次のとおりです。ボックス内で交差する 2 本の線 A と B の場合、ボックスを時計回りに歩くと、線が交互になっていることに遭遇します。たとえば、ABA B。 A. もちろん線がボックスの境界で交差したり、平行になったりする可能性はありますが、それは主なアルゴリズムを説明した後に詳細として扱います。

1. 線の方向を選択します。線が水平でない場合は線を +y 方向に向け、水平線を +x 方向に向けます。線の 1 つが矢印である場合、矢印はすべて、可能な限り上を指すように選択されます。水平の場合は右を指します。この方向では、各線にはボックスへの入口点 (方向線がボックス内を指している場所) と出口点があります。これらは同じ点である場合があります。
2. たとえば、右上隅から始めて、境界の周りを時計回りに EXITING 交差点をたどって、ラインの「終了シーケンス」を作成します。
3. 同様に、ボックスの右上隅から時計回りに ENTERING 交差点をたどって、線の「入力シーケンス」を作成します。
4. すべての交差がボックスの内部にある場合、入力シーケンスと終了シーケンスは互いに循環し、B[i] は交差の最小境界ボックスです。
5. それ以外の場合は、2 つのシーケンスを任意の要素に揃えます (巡回回転によって)。
6. 最初に異なるシーケンス内の要素を見つけます。これらの 2 つの線はボックスの外側に交点 P を持たなければならないので、P を含むように B[i] を大きくして B[i+1] を形成します。
7. 2から繰り返します。

グループ ラインが境界上に共通の入口点または出口点を持っている場合、入口シーケンスと出口シーケンスが明確に定義されていないため、これは完全ではありません。共通の入口点または出口点を持つライン L の各グループについて、L を注文するために少し大きめのボックスを使用します。

このアルゴリズムはすべての交差を出力するわけではありませんが、ボックスにすべての交差が含まれていることを保証します (期待しています)。

Answer 2

O(n log n) 時間で? わお。これが可能だとは思いもしませんでした。

私はまだここで他の答えを見つけていないので、ここに 1 つのアイデアがあります。あなたはそれをあなたが望むものにすることができます。

アイデア: まず、方位または勾配でラインを並べ替えます。他の条件が同じであれば、ほぼ平行な線は離れた点で交差する可能性が高いように見えます。そして、もちろん、あなたが興味を持っているのはその辺境の点です。

凸包のアイデアは正しいように聞こえますが、接線または延長線が関心領域から遠く離れて交差するほぼ平行な側面が包体にある可能性があることを考慮してください。全体として、それは主要なプログラミングの仕事のように思えます。幸運を。