GCフレンドリーな凸クリッピング（ユニオンと差分）アルゴリズム

Question

私は凸多角形を他の凸多角形に基づいて切断するアルゴリズムを探しています。破壊可能な地形（diff）とゲームの2Dマップで地形（union）を作成するためのものです。

アルゴリズムはガベージコレクタフレンドリでなければならず、必要なブール演算はUnionのみです。&差異。

私はいくつかの研究を行い、いくつかのgithubプロジェクトがありますが、それらはすべて多かれ少なかれいくらかのゴミを生成します。

https://github.com/tmpvar/2d-polygon-boolean

https://github.com/w8r/GreinerHormann

私は最善の解決策は、これらのいずれかを学び、それ私の方法を再作成することですね。しかし、私のニーズに合ったものについて聞いたことがありますか？

ありがとうございました。

Answer 1

この問題は、二つの副問題

1. は、2つの輪郭

2. との交点を見つけることを含む接合するMUS頂点を結合。

1.凸部を利用することができます。両方のポリゴンを2つのモノトーンチェーンとして見ることができます。 xを大きくするなどして二重ポリゴンの連鎖を同時に移動させると、縦座標が2つの横軸の間で交差するときに交点が検出されます。

2.合併または差異は、1つのポリゴンと他のポリゴンの間で交互に変化するアウトラインの部分であることに注意してください。

違いの場合、いくつかの切断された部分があることに注意してください。

私はあなたがすべてで任意の割り当て/割り当て解除せずに（ただし、出力ポリゴンのため）これを実装できることを推測します。