特別な場合にポリゴン交差が失敗する

Question

Bentley-Ottmann-algorithmを実装して、ポリゴンとポリゴンの交差を検出しました。これは通常非常にうまくいきます：ポリゴンは自己交差していないので、両方のポリゴンの線分の和集合内の線分の交点は、両方のポリゴンが交差していることを示します。

しかし、私はこのケースを見れば：

なしセグメントの交点はありません。しかし明らかに両方のポリゴンが交差しています。

他のポリゴンの各ポリゴンのポイントごとにポイントインポリゴンをチェックし、したがってO（m * n）で実行する純粋なアルゴリズムを使用しないと、このケースをどのように検出できますか？

Answer 1

ヒント：構成は多様であり、場合によっては、伸縮することができるように

例えばエッジまたは2つの重複するエッジ上の頂点のような特殊なケースの取り扱いが（重複いくつかの同一線上のエッジを考える）不安トピックであります。

私の最善のアドバイスは、すべての頂点に内側または外側の状態（他のポリゴンと同じ）を割り当てることで一貫性を強制することです。次に、他のポリゴンとエッジを交差させると、交差点数のパリティは端点状態の変化と一致しなければなりません（同じ状態=>偶数の交差点）。

どのように状態を割り当てるかは指定していませんが、これは特定のアルゴリズムに依存します（実際には状態は割り当てられます）。重要なことは、状態がテストされても、それ以上は変更できないことです。

異常（状態の変化に一致しない交差点の数のパリティ）が発生した場合は、交差点を犠牲にするか、または適切なものを複製することによって修正する必要があります。

例：このサンプルの場合

、緑色ドットは青ポリゴンの外部と見なさ頂点を示し、数字は、対応するエッジに割り当てられた交点の許容される数を示しています。

下の黒いアウトラインは、この状態の割り当てによって生じるユニオンポリゴンを表します。