大きいポリゴンに内接する最大面積ポリゴンを見つける

Question

大きなポリゴンにフィットする拘束の中でスケールアップできるポリゴンの大きさを最大にするポリゴンの回転と位置を探したいと思います。

現在の考え方は、スケーリングパラメータを最大化するために、位置と回転のパラメータを最適化するためscipy optimization routinesを使用することで、shapelyはポリゴンが含まれている制約を追加します。これは遅く、特にエレガントではないようです。

他のアイデア？

Answer 1

この問題は、NP-Hardのように聞こえます。候補ソリューションがあれば、それが最良の解決策であるとは確信できません。何らかのインクリメンタルなランダム検索を使用する必要があるようです。

Answer 2

内部ポリゴンが最大限に拡大されている場合、頂点がエッジ上にある「内部頂点 - 外部エッジ」または「外部頂点 - 内部エッジ」が少なくとも4ペアあります。

4つの頂点とエッジのペアをすべて取りましょう。すべての点について、2つの参照点の座標に対する線形方程式のシステムを得る。それには1つの解がある場合、交点がないことを確認し、OKであれば内部ポリゴンの座標とサイズを覚えています。

これは正確な解決策ですが、遅いです。他方、scipy最適化ルーチンは、グローバルなものではない局所的な最大値を見つける可能性が高い。