algorithm - 正多角形の効率的なパッキングアルゴリズム

Question

正多角形を長方形と直角三角形に縮小するパッキングアルゴリズムを探しています。アルゴリズムは、そのような形状をできるだけ少なくしようとし、実装が比較的簡単である必要があります（チャレンジの難しさを考えると）。

可能であれば、この質問への回答は、提案されたアルゴリズムで使用される一般的なヒューリスティックを説明する必要があります。

Answer 1

正多角形の答えはかなり簡単だと思います。

対称軸を見つけて、各頂点とそのミラーの間に線を引きます。これにより、ポリゴンが台形に分割されます。各台形は、長方形と2つの直角三角形に変えることができます。

Answer 2

特に長方形+直角三角形ではありませんが、多角形のテッセレーションを調べるための優れた研究ポイントは、ボロノイ図とドロネー三角形図、およびこことここです。

実際、「ちょうど直角三角形」で十分であれば、これらは三角形化されることが保証されており、本当に必要な場合は、いつでも任意の三角形を2つの直角三角形に分割できます。または、三角形の「先端」を切り取って、直角三角形と直角三角形からいくつかの長方形を作成することもできます。

かなり規則的なポリゴンがあることがわかっている場合は、放射状にスイープするか、「最大の凸状チャンクを切り取る」ことによって、耳の切り取りを試すこともできます。次に、残りの各三角形を2つに分割して、直角三角形を作成します。

_{（出典：eruciform.com）}

一方向にスイープしてから他の方向にスイープして台形を作成し、別の方法で分割することで、中断を少なくすることができますが、スイープラインが別のラインと交差していないことを確認する必要があります。実際にフラクタルなものでも、いつでもイヤークリップできます。

ただし、これにより非常に細い三角形が作成されることがあります。エッジに沿って連続的にクリッピングする代わりに、「最大を取る」などのヒューリスティックを実行できますが、O（n ^ 2）に近づくと、より時間がかかります。Delaunay / Vornoiは、ほとんどの場合、よりスリムな三角形ではなく、より迅速にそれを実行します。

Answer 3

ポリゴンに収まる最大の長方形を「切り取って」 、残り物を残してみることができます。三角形のピースになるまで、残りの長方形の切り抜きを繰り返します。次に、必要に応じて、それらを2つの直角三角形に分割できます。これにより、長方形と直角三角形の量が最小になるソリューションが常に得られるかどうかはわかりません。