単純凸と単純非凸多角形の差

Question

Pが凸であるがQがない単純な2つのポリゴンPとQが与えられると、PがnとQを持つ場合、PとQの差分$ P - Q $をどれくらい速く計算できるかm個の頂点を持ちますか？

ポリゴンは、時計回りの順序で並べられた頂点のリストとして与えられます。

Answer 1

「速い」は多くのパラメータに依存するので、私たちは最初にそれを行う方法から始めなければならないと思います。

まず、ポリゴンが同じ平面にあると仮定します。 Pの各行とQの各行との有限交差点を計算することから始めます。交差点が存在し、交差点が交差線上にある場合（開始点と終了点の間であり、それらの間ではありません）反復的な線交点次に、セグメントの中間点を持つポリゴン計算のポイントを使用して、各線分を分類します（必要に応じて分割されているため、それらをセグメントとして呼び出すことができます）.Inner、OuterまたはOnthePolygon ... Qの外側にあるPのラインとPの内側にあるQのラインからの新しいポリゴンです。ここで、あなたの課題は、お互いにある公差とラインを扱うことです。一見して、全体的なアルゴリズムはこのようです..

このアルゴリズムは、範囲（各軸の最小値と最大値）を計算して線やポリゴンを削除することで改善できます。ハードウェア、プログラミング言語、またはデータ処理パラメータを除いて、この操作の速度は入力ポリゴンとその向きに依存します。