mieki256's diary

とりあえず、BLF法(Bottom-Left-Fill)については動いた。

_長方形詰込み問題のテスト用ページ (2013/10/06 リンク先をDropboxから自宅サーバ内ページに変更)

最初、 _こちらの講義資料のページ のサンプルプログラムを、意味も分からず書き写したのだけど。説明用pdfを、自分が分かるように写経(?)したら、何をやってるか理解できた。写経したpdfは以下。

_BL安定点候補についての説明pdf
_BL法チェックについての説明pdf

ただ、問題があることも分かったわけで。以下が結果画像だけど。



赤い点が、BL安定点候補の座標。 *1

明らかに、「そこにはもう矩形が置けないだろう… (´･ω･｀)」という場所に、BL安定点候補が作られてる。

そして、この全ての候補群に対し、矩形が置けるか、置いたとして他の矩形と重なってないか、てなことを判断していくわけだから…。矩形の数が少ない場合は、他の方法と比べてそんなに処理時間は違わないのだけど。配置済みの矩形が増えるにつれて、どう見てもモリモリと遅くなっていくはずで。

どうせ扱う矩形数は少ないのだからこれでいいじゃん、という気もするのだけど。しかし、もうちょっとどうにかならんか、BL安定点候補を減らせないか、という気もしてきたり。

さて、どうすればいいんだろう？

ちょっと思いつくのは…。

• メモリが贅沢な環境なら、配置先と同じ大きさの、「矩形が既に描かれてるか否か」だけを判定する画像領域を作って、そこにも矩形を書き込んでいく。BL安定点候補が見つかった際に、その座標には既に矩形が描かれてるなら、BL安定点候補から外す。
• 新しく置いた矩形から線分を伸ばして、配置済み矩形の線分、もしくは配置済み矩形から伸びた仮想の線分との交差座標を記録。新しく置いた矩形から近い順に交差座標を見ていって、仮想線分との交差座標はそのままにして、実際の線分と交差したらそれ以後のBL安定点候補は、候補から外す。

とか。でも、前者はともかく、後者はかえって遅くなるんじゃないのかという気も。新しく置いた矩形の上下左右に4回その処理を行うから、4回ソートすることになるだろうし。うーん。

◎ とんでもない勘違いをしてた。 :

◎ JavaScriptの乱数は初期化ができないのか。 :

---

ニュース番組や教養番組を流してほしい…。

_米食品医薬品局　韓国製海産物の回収を求める: The Voice of Russia という記事を見て、「恐ろしいなあ」と思ったのだけど。ふと、そもそも食品に人糞が入ってるか、どうやって検査するのだろう？ てな疑問が湧いたりもして。出したてホヤホヤのブツがちょこんと置いてあったらさすがに見た目で分かるだろうけど、たぶんその手の話はそういう状態ではないのだろうし…。仮に、有効な検査方法が無いのであれば、もしかするとデマだったりしないか、という不安も。

てなわけで、検索。

_ペストコントロールについて

なるほど、大腸菌検査をすれば、確実に大まかな状況が分かるらしい。ということは、件のニュースは、やっぱりそういうことなのかな。

ソレとは別に。人糞入りの食品と、セシウム入りの食品、どっちがマシなのかなあ、という疑問も湧いてきた。

人糞、というか大腸菌/ノロウイルスの類も、加熱すればある程度どうにかなるらしいけど。すると、ちょっとやそっと入っていても、火を通すなら食えなくはない、という話になってしまうのだろうか。

世の中には、「この程度の食品中の放射性物質量なら人体に影響はない」と喝破する人達が居るわけだけど。同じ論理で、「この程度の食品中の人糞なら加熱することで人体に影響はない」と喝破できそうでもあるな、と考え始めて、さてどっちがマシなのかと悩んでしまったり。 *1

考えてみたら、昔は人糞を肥料にしていたのだったか。ううーん。

人糞を肥料に、というのもなかなかデンジャラスで。母方の叔父は、子供の頃に寄生虫が腹の中にいたそうで、虫下しを飲んだら洗面器一杯に出てきた、てな話を聞いた記憶があり。人糞を肥料にしていると、そういうサイクルが出来てしまう、と何かの本で読んだ記憶も。なので、昔はそういう生活だったのだから何の問題もない、とは一概に言えないよな。ううーん。

---