複数のポリゴンと交差する方法は？

Question

次の入力と出力を含むアルゴリズムを探しています。

入力：平面内のポリゴンのセット。たとえば、p1 ... pnおよびS.（p1 ... pnは凹面で、sは凸です。）

出力：Sの違いとP1の結合に等しいこの平面内のポリゴンのセットの面積... Pn。

2つのポリゴンを交差またはマージするアルゴリズムを見つけました。しかし、これらの操作のそれぞれがいくつかのポリゴンを生成する可能性があるため、私がそれを素朴にした場合、私は大量のポリゴンを作成します。

だから：複数のポリゴンの交差点を処理する方法は？

すべてのポリゴンが一緒に接続されている場合は大丈夫でしょう。その地域だけが私が望んでいるので。私の考えは、指示されたポリゴンを使用して穴をシミュレートすることでしたが、nが爆発する可能性があるため、「最小限の表現」があるかどうかを調べる問題が再びあります。 [私が話していることを理解していますか？とても奇妙です...）

Answer 1

すべてのエッジを一緒にaに投げ込むことができます スイープラインアルゴリズム. 。それは最適ではないかもしれません（？）が、少なくともあなたが探している最小限の表現を得るでしょう。

Answer 2

1つの解決策は、各ポリゴンを三角形の束に変換することです。それを行うと、三角形で同じ機能を簡単に実行できるため、一連の領域間で組合/交差/差を見つけるのはかなり簡単です（2つの三角形の結果には最大6つの三角形が含まれる場合があります）。

Answer 3

最も簡単なアプローチは、凹面のポリゴンを凸型のポリゴンに分解することです。次に、2つの凸ポリゴンと交差することはほぼ些細なことです。