1

たとえば、長方形の板からいくつかの長方形の穴を削り取りたいとします。例えば、

状況 1、穴が交差:

穴 0,1,2 を持つボード x、長方形 0 と 1 が交差します。

xxxxxxxxxxx
xxxxxx222xx
x000xx222xx
x00011222xx
x00011xxxxx
xxx111xxxxx
xxxxxxxxxxx

またはより単純な状況 2、穴が交差しない:

xxxxxxxxxxx
xxxxx2222xx
x00xx2222xx
x00xx2222xx
x00x111xxxx
xxxx111xxxx
xxxxxxxxxxx

後者は、「大きな長方形内の一連の長方形を反転する」に似ています。

私の質問は: ボード x を正確にカバーする一連のサブ長方形を計算する方法は? 

Input: a larger rect, and a set of hole rects  
Output: a set of sub rects cover exactly the larger rect with holes

rect 構造体は以下の CCRect が好きかもしれません。調整タイプは float です:

typedef struct {float x; float y;} CGPoint;
typedef struct {float width, float height} CGSize;
typedef struct {CGPoint origin; CGSize size;} CGRect;

素晴らしいアイデアはありますか？

4

1 に答える 1

1

あなたの質問には制約がありません。結果をどのように最適化しますか?できるだけ少ない四角形を求めていますか?

エッジはグリッド上にありますか?

私はこのようにします：

  • 1 つの大きな長方形と 2 つの方法から始めます。1 つは長方形を分割するためのもので、もう 1 つはそれらを結合するためのものです。
  • 穴の四角形の各辺に対してメインの四角形を 2 つに分割します。境界線を可能な限り延長し、この線に沿って平面を分割します。それが完了すると、多くの小さな長方形ができあがります。できるだけ長方形を少なくしたいと思います。
  • 1 つ渡す - 穴を削除 : 小さな四角形ごとに、座標が最初に持っていた穴の四角形の内側を塗りつぶしている場合は、それを破棄します。
  • 2 つ渡す - 残りの四角形を結合します。各四角形について、隣接する四角形を形成できる場合は、それらを結合します

このパス 2 はトリッキーです。そこで行うべき最適化がたくさんあります。簡単な最適化は、垂直方向と水平方向を交互に結合することです。このようにして、より大きな長方形になります。

編集:
パス 1 で BSP ツリーを構築すると、パス 2 を劇的に高速化できます。分割するたびに、2 つの葉が子の四角形である新しいノードが作成されます。パス 2 で近隣を見つけるのがはるかに高速になります。

于 2012-09-18T15:20:47.267 に答える