mieki256's diary



2012/08/01(水) [n年前の日記]

#1 [javascript] 長方形の詰め込み問題をまだ実験中

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

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

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

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

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

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

以上、1 日分です。

過去ログ表示

Prev - 2012/08 - Next
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31

カテゴリで表示

検索機能は Namazu for hns で提供されています。(詳細指定/ヘルプ


注意: 現在使用の日記自動生成システムは Version 2.19.6 です。
公開されている日記自動生成システムは Version 2.19.5 です。

Powered by hns-2.19.6, HyperNikkiSystem Project