線分によってポリゴンを 2 つのセット (左/右) に分割するための優れた (堅牢な) アルゴリズムが必要です。私のポリゴン表現は、単に整数座標のリスト（時計回りに並べられ、自己交差することはありません）であり、線分は始点と終点で表されます。線は常にポリゴンの外側で開始および終了します。つまり、ポリゴンと偶数回交差します。
次に例を示します。
アルゴリズムの出力は、2 つのセット (時計回りに移動) である必要があります。
- 左：HABCH、FGDEF
- 右：HCDGH、BAB、FEF
ポリゴンを反復処理し、ポリゴン セグメントが線と交差しているかどうかを確認し、境界のケースを尊重することで、ポイント AH を特定できます。各マルチラインがどちらの側に属しているかを判断することもできます。しかし、私の人生では、これらのセグメントをどのようにつなぎ合わせるかを決めることはできません.
汎用のクリッピング ライブラリを提案する前に: ポリゴンを互いにクリッピングするのに非常に優れたブースト ポリゴンを使用していますが、線分に対してポリゴンをクリッピングできるライブラリが見つからず、一般的には不可能です。線分をポリゴンに変換して、クリップできるようにします。
編集：FEFと、ポリゴンが線分の両側にパーツを持つことができるという事実を見逃していました。