mieki256's diary

BLF法(Bottom-Left-Fill法)なる方法もあると _こちらの講義資料のページ で知り、JavaScript で書いてみたりしているところ。

それはそれとして。空き領域を管理しながら詰める方法を眺めていて、なんだか断片化してるソレみたいだなと。 薄いピンクの色が、空き領域として管理されている領域を示しているのだけど。

どう見ても、そこの隙間に入れられるだろ！ って感じ。しかし、領域がバラバラになっているから、そこに入れられると判断できない状態になっていて。これってどうにかならんものか…。

1次元の空き領域なら、単純にくっつけてしまう・結合してしまえばいいけれど。2次元の空き領域って、結合しようにも…。例えばの話、以下のような空き領域があったとしても。 何通りかの矩形領域になってしまう。

いっそ、矩形じゃなくて、多角形にして管理できないかしら。でも、多角形の中に矩形が入るのかを、どうやって判定すればいいのやら。仮に判定できたとしても、その矩形を収めた後の空き領域をどうやって作ればいいのやら。

そのへん考えていくと、ドローツールの類はどうやって処理をしているんだろうと。図形に対して、交差、差分、結合、色々できる。どういう処理をしているのだろう…？