これは二つの方法で接近することができる凸多角形と凹ポリゴンを被覆するための任意のアルゴリズム（穴を含ん）

Question

があります凸多角形

ii）指定された多角形を凸多角形で覆い、それらの和集合 が元の多角形を与えるようにします。この場合、 と凸多角形との間に重複が存在する可能性があります。

パーティショニングはポリゴン全体をカバーしますが、凸多角形の数は2番目の方法で減らすことができます。最小の凸多角形で凹面ポリゴン（第2のアプローチ）をカバーすることは、NP-Hardであることも知られている。

私は特に上記の2番目のアプローチに基づいてアルゴリズムを探していますが、凸多角形の数は最小限ではないかもしれません。

Answer 1

すでにMBoとYves Daoustがコメントにコメントしたように。凸多角形へのポリゴン分解は、三角形分割（または台形分解）によって行うことができます。これは、n-2（内部）の三角形を有するn頂点単純ポリゴンP、すなわち頂点の数が線形である場合に生じる。

凸分解を構成する別の方法は、一般化motorcycle graphを使用することです。私はより単純な方法が必要だと思うだろう！ 主なアイデアは、Pのすべての反射頂点rに対してオートバイmを開始することです。各オートバイmは、与えられた速度で所与の方向に駆動し、トレースを残します。別のオートバイがそのようなトレースに合致すると、それはクラッシュする、すなわち停止するが、トレースを残す。 一般化とは、Pに埋め込むことを指し、ポリゴン境界は、バイクが衝突する壁として機能する。さらに、2つのオートバイが同じ場所で出会う場合、別のオートバイを始める必要があります。すべての二輪車が墜落した後、実際にはPの凸面のテッセレーションであるトレースのグラフがあります。これにはいくつかの論文（one here）がありますが、実装が難しいでしょう。この結果、O（r）凸多角形がPの内部を覆うようになります。

私は最も簡単な方法は、三角形分割または台形分解を行うことです。これらは十分に研究されており、多くのライブラリの実装として利用可能です。

コメントにも記載されています。入力は、O（n）ポリゴンを強制的に生成することができます。 n/2の反射頂点（内角> pi）を持つ星型ポリゴンを考えてみましょう。