私は一種の切断の問題を抱えています。穴のない不規則な多角形と、標準サイズの長方形タイルとその値のリストがあります。
このポリゴンに収まる最も価値の高いタイルを 1 つ見つける効率的なアルゴリズムが必要です。または、単一のタイルがポリゴン内に収まるかどうかを示すアルゴリズム。また、頂点が 100 未満の不規則なポリゴンの場合、決定論的な時間で実行する必要があります。
ポリゴンとタイルを回転できることを考慮してください。凸多角形と非凸多角形の両方の回答/ヒントをいただければ幸いです。
8684 次
3 に答える
7
免責事項：これに関する文献を読んだことがないので、これを行うためのより良い方法があるかもしれません. この解決策は、あなたの質問を読んだ後に私が考えたものです。
長方形には、高さと幅の 2 つの重要な測定値があります。
多角形と長方形から始めると、次のようになります。
1: 多角形の周囲を回って、長方形の高さが多角形に収まるすべての場所をメモします (これを多角形として保存できます*):
2:作成したばかりの新しい多角形の周囲を回って、長方形の幅が多角形に収まるすべての場所をメモします (これも多角形として保存できます)。
3: 長方形は、この新しい多角形内に収まる必要があります (これは多角形であるため、長方形を多角形内に正しく配置するように注意してください。長方形ではありません。長方形の左上のノードを、この新しいポリゴンで問題ありません)
4: 四角形が収まる領域が見つからない場合は、多角形を数度回転させてから、もう一度やり直してください。
*注意: 一部のポリゴンでは、四角形を配置できる場所が複数ある場合があります。
于 2013-04-09T20:18:15.723 に答える
2
これは役立つかもしれません。Javaで書かれたソースコードが付属しています
http://cgm.cs.mcgill.ca/~athens/cs507/Projects/2003/DanielSud/
于 2013-10-11T04:45:11.133 に答える
2
絶望的な検索を何度も行った結果、この問題に対する特定のアルゴリズムはないと思います。それまでは、ポリゴンの包含問題に関するこの古い論文を見つけました。その言及された記事では、 n 個のポイントを持つポリゴンがm個のポイントを持つポリゴンに適合する
かどうかを検討するための非常に優れたアルゴリズムを提示します。アルゴリズムは、一般に、2 つのトランスポータブルおよび回転可能な 2D ポリゴンに対して O(n^3 m^3(n+m)log(n+m)) です。
計算幾何学でそのような不規則なアルゴリズムを探しているなら、それがあなたの助けになることを願っています.
于 2013-08-13T20:13:16.233 に答える