2

重なり合っていない多くの長方形をより大きな長方形に圧縮したいそれらが隣接している場合。

現在のアルゴリズムの疑似コード:

do
   compress horizontally using sweep and prune
   compress horizontal output vertically using sweep and prune
while (this output is small than previous output)

これは、スイープとプルーニングへのリンクです。

これはうまく機能していますが、長方形の出力が少なくなるアプローチがあるかどうかを知りたいです。私が今していることよりも洗練されたものがあると思います。

4

1 に答える 1

5

あなたの問題は、長方形の間に小さな隙間があり、それらが1つのピースにまとめられないことです。スイープ アンド プルーン メソッドのソース コードにアクセスできる場合は、「オーバーラップ」テストにバッファーを追加できますが、R ツリーの使用を検討する方が最適だと思います。これにより、ギャップなどの制限を台無しにすることなく、長方形のスペースにインデックスが付けられます。

Rツリーウィキ

これは、Sellisらによる関連論文です。アル。R+ ツリーの説明:

http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=50ECCC47148D9121A4B39EC1220D9FB2?doi=10.1.1.45.3272&rep=rep1&type=pdf

これは R ツリーの C# 実装です。

http://sourceforge.net/projects/cspatialindexrt/

[編集 - コメント 1 の後]

それでは、現在の問題を捉えることができるかどうか見てみましょう。

  • 長方形は、水平/垂直隣接テストのパスで結合されます。
  • 長方形は、両方の隣接する境界が等しい場合にのみ結合されます。
  • 結合の中間結果も、有効な四角形を形成する必要があります。
  • 結合の順序が異なるため、結果は最適ではありません。

あなたは実際に、直線多角形の長方形への最小の分割を探していると思います。最初のステップは、長方形を形成するかどうかに関係なく、すべての接触する長方形を結合することです。プロセスの各ステップの中間段階でも完全な長方形の分解が必要であり、最適ではない結果につながるという問題に巻き込まれていると思います。それらを 1 つの直線ポリゴンに結合すると、グラフ理論のメカニズムを使用できます。

直線多角形の長方形への最小分割

David Eppsteinの Graph-Theoretic Solutions to Computational Geometry Problemsをご覧ください。

または、 Gareth Reesによる、重なり合うことなく長方形のセットをカバーする最小の長方形を見つけるためのアルゴリズムを調査します。

于 2013-07-21T15:12:08.027 に答える