長方形間の最適な負のスペースアルゴリズム？

Question

大きな矩形Rの内側に矩形r []がある場合、r []間に "negative space"を埋め込む最小矩形数を決定するための最適な高速アルゴリズムがありますか？例えば

、紫色の四角形の内部これら三つの青色の長方形所与：

どのようにして迅速に最適な構成ではないことがある（以下緑色にこのような長方形のリストを決定することができます、したがって、私のポスト）：説明は何oosterwal

Answer 1

が台形分解の特殊なケースで、computatiでプリミティブ十分に理解平面的な細分化におけるポイント位置のために典型的に使用されるオンナルジオメトリ。それは、妥当な定数を用いて時間O（n log n）で実施することができる。

矩形が一般的な位置にあるときは、＃緑色の矩形= 3 *＃青色の矩形+1で「矩形化」を返します。これは最適です。各青い隅のL字型の近傍は、一方向または他の緑色のセグメント（一般的な位置：2つの青色の長方形には同じセグメントを使用できません）で切断する必要があります。したがって、青色の各矩形に対して、 4つの緑色のエッジ 8つの緑色のエッジと4つの頂点（4つの新しいエッジと4つの細分化）。多面体式の結果は、さらに3つの面（長方形）です。

V-E + F = 1 +＃接続コンポーネント。

---

例：私たちは、上から下へのスイープラインを実行している

abc 
0+-----------+ 
1|   | 
2| +--+  | 
3| |R | +-+ | 
4| +--+ |S| | 
5|  | | | 
6| +--+ | | | 
7| |T | +-+ | 
8| +--+  | 
9+-----------+ 

。イベントは、我々は、部分的に構築され、緑色の四角形を保持しているxで注文した二分探索木を設定

# (y, whichside, xmin, xmax) 
(2, top, 3, 6) # R 
(3, top, 8, a) # S 
(4, bot, 3, 6) # R 
(6, top, 2, 5) # T 
(7, bot, 8, a) # S 
(8, bot, 2, 5) # T 

です。私はそれをリストとして書きます。

# (xmin, xmax, ymin) 
(0, c, 0) 

ここでイベントの処理を開始します。最初は（2、top、3、6）です。これまでの唯一の緑色の矩形内にネストされています（xmin = 0、xmax = c、ymin = 0、ymax = 2）。 （青の間隔は常に限り青い矩形が交差しないよう入れ子にします。）我々は2つの新しい緑の四角形、青の長方形の各側に1つを起動し、検索ツリーは

(0, 3, 2) (6, c, 2) 

が含まれている今、私たちは（処理します3、上、8、a）。インターバル（8、A）内部巣（6、C）、私たちは別の四角形を終える（XMIN = 6、XMAX = C、YMIN = 2、YMAX = 3）と2つ以上を起動：

(0, 3, 2) (6, 8, 3) (a, c, 3) 

今（4、bot、3、6）を処理します。これにより、左と右の緑色の四角形が終了します。（xmin = 0、xmax = 3、ymin = 2、ymax = 4）、（xmin = 6、xmax = 8、ymin = 3、ymax = 4）検索ツリーは

(0, 8, 4) (a, c, 3) 

です。この時点では明らかになるはずです。

abc 
0+-----------+ 
1|   | 
2+--+--+-----| 
3| |R |-+-+-| 
4+--+--+-|S| | 
5|  | | | 
6+-+--+--+ | | 
7| |T +--+-+-+ 
8+-+--+------+ 
9+-----------+ 

音符縮重取り扱い上：ここで完成rectangulationであるとトップイベントの前に置く底イベントは同じy座標、およびゼロ領域で矩形を抑制する。より複雑なイベントプロセッサが避けることができる「不要な」矩形がまだ残っています（与えられたy座標ですべてのイベントを一度に処理することによって）。