私はある種の切断問題があります。穴がない不規則なポリゴンと、長方形タイルの標準サイズとその値のリストがあります。ポリゴンの内部に長方形をフィッティングするアルゴリズム
このポリゴンに適合する単一の最高値のタイルを見つける効率的なアルゴリズムが必要です。単一のタイルがポリゴンの内部に収まるかどうかを示すアルゴリズムだけです。また、頂点数が100未満の不規則なポリゴンについては、確定的な時間内に実行する必要があります。
ポリゴンとタイルを回転できることを考慮してください。 凸ポリゴンと非凸ポリゴンの両方のヒントを理解できます。
を、私はこの問題の任意の特定のアルゴリズムが存在しないと思います。私が見つけたまでthis old paper about polygon containment problem.
これは、nポイントのポリゴンがmポイントのポリゴンに収まるかどうかを検討する本当に良いアルゴリズムです。
2つの搬送可能かつ回転可能な2Dポリゴンに対して、アルゴリズムは一般的にO（n^3 m^3（n + m）log（n + m））です。
計算幾何学のような不規則なアルゴリズムを探しているのなら、それがお役に立てば幸いです。
免責事項：私はこれについての文献は一度も読んだことがないので、これを行うより良い方法があるかもしれません。この解決策は、私があなたの質問を読んだ後に考えたことです。
長方形は、2回の重要な測定を持っている - それは、高さだと私たちは、多角形や四角形で始まるかどうかは今
幅です：
1：ポリゴンの周囲に移動して、長方形の高さはポリゴンに収まるすべての場所をメモを取る（あなたは、ポリゴン*としてこれを保存することができます）：
2：あなただけを作り、長方形の幅はポリゴンに収まるすべての場所をメモを取る新多角形の周囲に行く（再び、あなたは多角形としてこれを保存することができます） ：
3： - ない長方形長方形は、この新たな多角形に収まる必要があります（ただこれは多角形であるとして、あなたが、正しく多角形の内側に長方形を配置するように注意してください。
4：矩形が収まる領域が見つからない場合は、カップルでポリゴンを回転させます（矩形の左上のノードをこの新しいポリゴンの左上のノードに揃えます）次のようにして再試行してください。
*注：一部のポリゴンに、あなたは長方形を装着することができる複数の場所を取得します：多くの絶望的な検索後
あなたの答えをありがとう。それは私が望むものではありません。 矩形問題によるポリゴン包含問題**を解決するアルゴリズムが必要です。 – aisa
@aisa私のアルゴリズムは、与えられた回転ごとにポリゴンの内部に矩形がいくつあるかを示します。したがって、場所の数がゼロの場合、その回転で長方形が収まりません。場所の数が0より大きい場合、長方形はその回転で収まるでしょう。したがって、簡単な条件文を使用すると、必要なものを確認できます。公差が非常に狭いので実際にこの問題を解決しない限り、アルゴリズムの反復ごとにあなたのシナリオに向かう度数を調整できるはずです。 – stormCloud
これは役に立ちます。これは、Java
[ポリゴンの内側の四角形]でGoogle検索が、この研究論文を含め、いくつかの興味深い結果を返すhttp://cgm.cs.mcgill.ca/~athens/cs507/Projects/2003/DanielSud/
ご協力ありがとうございます。しかし、ポリゴンは回転することができると述べました。それは必ずしも凸型のものではありません。とにかく、あなたのリンクにもう一度感謝します。 – aisa
を書かれたソースコードが付属しています：http://www.mpi-inf.mpg.de/~ jeschmid/public/Knauer2012.pdf、いくつかのSO質問：http://stackoverflow.com/q/610462/56778、およびhttp://stackoverflow.com/q/10214829/56778 –
多角形が不規則であると述べました。彼らは凸ですか？ – phs
もちろん私は以前にそれをグーグルで見つけました。しかし、あなたの指導に感謝します。そして問題を編集しました。 – aisa