1

n個の長方形の障害物があるバウンディングボックス領域にスペースの長方形を描く方法について誰か助けてもらえますか? 軸平行な長方形の障害物はいくつでも存在する可能性がありますが、これは特殊なケースではなく、さまざまなコーナー ケースを考慮する必要があります。最大水平ストリップアルゴリズムを使用するのが最善ですか? そしてどうやって？

問題の説明:

1. SUB1 と SUB2 は障害物であり、SUB1 と SUB2 の内部には触れません。すべての SUB の外側にすべての空き領域を見つけて、それらから長方形を作成する必要があります。

2. SUB と交差せずに左から右にスイープして、フリー エリアの四角形で可能なすべての四角形を見つける必要があります。

この場合の最大水平スペース長方形の総数は 7 または一般に 3n+2 (n は障害物の数) である必要があります: alt text http://img25.imageshack.us/img25/452/pic1gts.png

代替テキスト http://img22.imageshack.us/img22/3417/pic2h.png

代替テキスト http://img16.imageshack.us/img16/5818/pic3h.png

代替テキスト http://img13.imageshack.us/img13/2151/pic4.png

クリックして画像を表示: http://img25.imageshack.us/img25/452/pic1gts.png http://img22.imageshack.us/img22/3417/pic2h.png http://img16.imageshack.us/img16 /5818/pic3h.png http://img13.imageshack.us/img13/2151/pic4.png

4

3 に答える 3

1

最も単純なアルゴリズムを探していますか、それとも最適に最小の分割長方形を見つけるアルゴリズムを探していますか？

ベースラインとして最もコーディングしやすいアルゴリズムから始めます。これは、多くのアプリケーションだけで十分である可能性があります。これは、書きやすく、理解しやすいものです。

長方形のリストを初期化して、画面の長方形を1つだけ含めます。

ここで、障害物ごとに、長方形のリストを繰り返し処理します。長方形が障害物と交差する場合は、リストから長方形を削除し、障害物を回避する新しい小さな長方形を挿入します。これは小さなサブ問題であり、障害物のどの部分が長方形と交差するかを確認するだけで簡単に解決できます。最終的に0、1、2、3、または4つの新しいサブ長方形になる可能性があります。（障害物が1つのコーナー、2つのコーナー、すべてのコーナー、コーナーなし、エッジなし、コーナーなし、1つのエッジ、コーナーなし、2つのエッジと交差する6つのケースを考慮してください。）

すべての障害物について繰り返します。障害物にぶつかることなく自分の領域をカバーする分割された長方形のリストが残ります。最適な数ではありませんが、開始して10分でコーディングするのに適した場所です。

于 2009-03-14T01:44:03.887 に答える
0

はい、最適な最小の分割四角形を見つけようとしています。

あなたの提案について少し説明を求めたいと思います。「長方形のリストを初期化して、画面の長方形のみを含めます」。

画面の四角形とは、外側の境界キャンバスを意味しますか? 次に、Rectangle List には 1 つの長方形しかありません。

「ここで、障害物ごとに、長方形のリストを反復処理します。長方形が障害物と交差する場合は、リストから長方形を削除し、障害物を回避する新しい小さな長方形を挿入します。」

上記を進めるには、障害物の同一線上の各エッジ (4 つのエッジ - 左、右、上、下) に基づいて比較する必要がありますか? つまり、4 つのコーナー ポイントにある SUB1 と SUB2 の各エッジが、互いに交差するか、キャンバスのバウンディング ボックスと交差するかを調べます。これは正しいですか？

于 2009-03-14T02:04:23.837 に答える
0

角縫いデータ構造は、これを行うことができます。ただし、オープンソースの実装については知りません。これに関する元の、または少なくとも標準的な論文は、Ousterhout (Tcl で有名) です: http://www.eecs.berkeley.edu/Pubs/TechRpts/1983/6352.html

于 2009-03-14T03:39:05.217 に答える