algorithm - 2Dポリゴンをより小さなポリゴンに最適に細分化（テッセレーション/分割）するためのアルゴリズム？

Question

それぞれ時計回りの座標のリストとして、いくつかの2Dポリゴンがあります。ポリゴンは 単純で（つまり、凹面の場合もありますが、交差していません）、互いに重なりません。

サイズの制約に合うように、これらのポリゴンをより小さなポリゴンに分割する必要があります。元のポリゴンと同じように、小さいポリゴンは単純（自己交差しない）である必要があり、制約は、それぞれが1つの「単位正方形」内に収まる必要があることです（簡単にするために、1x1と見なすことができます）。

重要なのは、これを可能な限り効率的に行う必要があるということです。ここで、「効率的」とは、結果として得られる（小さい）ポリゴンの数が可能な限り少ないことを意味します。計算時間は重要ではありません。

このためのスマートなアルゴリズムはありますか？最初は、各ポリゴンを再帰的に細分化する（水平または垂直のどちらか大きい方の方向に分割する）ことを考えましたが、これでは最適な結果が得られないようです。何か案は？

Answer 1

初期ポリゴンの初期点の1つの中心と、目的の長さ制約の半径を使用して円を描画します。

円は2点で少なくとも2本の線と交差します。これで、最初の三角形が可能な限り大きくなりました。次に、それらの交差点を次のターゲットとして選択します。外側に最初のポイントがなくなるまで行います。三角形をできるだけ大きくします（できるだけ少なくします）

• 作成済みの三角形のエッジを交点として考慮しないでください。
• 結果として得られるポリゴンは、必ずしも三角形であるとは限りません。四角形にすることもできます。たぶんもっと大きなポイント数も！
• それらはすべて、希望するサイズとほぼ同じです。

内部部品を微調整するには、いくつかの計算が必要になります。

Answer 2

以下を使用することをお勧めします。

1. たとえば、スイープラインアルゴリズムを使用して、ポリゴンを三角形分割します。

2. すべての三角形が制約に違反していないことを確認してください。制約に違反している場合は、最初にエッジフリップを試して修正します。違反していない場合は、最も長いエッジで細分割します。

3. 動的計画法を使用して、制約を維持し、隣接するポリゴンのみを結合しながら、三角形を結合します。