複数の凸多角形交差

Question

私は交差する複数の凸多角形を持っています。私はそれらの多くが交差する地域を探したい。 イメージでは、それを「ピーク」と考えることができます。私は地元のピークを探しています。

私は2つのポリゴンを交差させるソフトウェアを持っています。今私は可能なすべての交差点（指数関数時間！）を計算することなく、ピークを計算する方法を考えています。

誰かがヒントを持っていますか？

Answer 1

与えられた凸多角形。すべてのポリゴンの境界がn個の線分の形で与えられていると仮定しよう。各線分は、それが属するポリゴンとその内側を参照します。線分の頂点をx座標でソートしましょう。今度は、左から右にラインスイープを開始します。

ほとんどのO（k）回の掃引中に、すべてのポリゴンが凸面であるため、ポリゴンの開始と終了が行われます。このような開始イベントでは、掃引線の状態を調べ、他のポリゴンがどれくらい多くのポリゴンを囲むかを判断します。どちらがO（n）時間かかります。

n個のセグメントについて、ラインスイープは、O（n log n + k^2 + kn）時間を取得した開始イベントの処理を追加して、O（n log n + k^2）線分の参照を使用して、現在カバーしているポリゴンの数をすべての領域（線分）に割り当てることが可能でなければなりません。