＜集大成＞アルゴリズム大辞典

＜集大成＞アルゴリズム大辞典 at TECH

474:デフォルトの名無しさん
08/09/20 11:26:32
すまん、図形描画アプリみたいなものを作ってるんだが･･･
次のようなもので悩んでます。
１．複数の矩形があるときに同じところを再描画しないように無駄なく描画する矩形を計算するにはどうしたらいいか?
場合によっては複数矩形を包含する矩形で一度に描画した方がいい場合も含む。
総当たり以外でエレガントな方法というとどんなんざんしょ?
２．同じような話なのかもしれんが、矩形と線分(曲線含む)が混在してる場合で描画する矩形にかかる部分だけの線分を描画する効率のいい方法。

教えてエロイ人･･･

475:デフォルトの名無しさん
08/09/20 12:15:00
メモリが許せば、思い切って座標にオブジェクトを持たせるとか。

476:デフォルトの名無しさん
08/09/20 12:15:42
>>475は>>468にです。

477:468
08/09/20 18:05:06
お返事ありがとうございます。

>>472
空間分割とかいうやつですかね？
しかしこれは「最も近い点を取得する」という場合に
やはりお察しのように問題がありまして、
結局こちらの方法は諦めたのであります。
一応この最も近い点を探す距離も制限されてはいるのですが、
結構範囲が広いのでその表現は省かせていただきました。

>>475
これはその空間分割の究極ですね・・・
しかしこれはまた違う方向で膨大な判定量になりそうな気がします。

478:デフォルトの名無しさん
08/09/20 19:00:54
>>477
472の亜種だと思うけどＸ，Ｙ軸上でソートして、各軸上の分布をクラスタとして扱うっていうのがGameProgrammingGEMに載っていた。

479:デフォルトの名無しさん
08/09/20 21:40:57
>>474
問題が明確じゃないのだけれど，

(1)
『描画する』条件は，単に『別の矩形に包含されないこと』でよい？
それとも，矩形間に上下関係（例: Windowsのウインドウ）がある？

(2)
『描画する』条件は (1) と共通ということでよい？
それと，曲線はどのような形で与えられる？（例：ベジエ曲線）

何にせよ平面走査型のアルゴリズムが有力に動くと思う．

480:デフォルトの名無しさん
08/09/21 11:23:34
ナップサック問題とは、価値と重量があるものを、入れられる重量に制限がある箱に
一番価値が高くなるように効率よくいれるにはどういれたらよいかの手順を考える問
題ですよね。

これに、価値が高くなることに加えて、入れる順番も重さがあるものから入れる、あるいは
軽い順に入れるなどの制限が加わった場合にどのようにすればよいかという解法は
存在しますか？

481:デフォルトの名無しさん
08/09/21 11:59:36
>>480
入れるものを決めた後で重量でソートすればいい

482:474
08/09/21 12:35:56
>>479
不明確ですいません･･･orz
1．矩形間に上下関係有りです。ただその辺含めてまとめて”無駄な矩形を省く”というかたちでまとめられないかと。
２．描画の段階ではパラメトリック曲線から計算された連続した直線になると仮定しています。

平面走査型ちょっくらぐぐってきます。

483:デフォルトの名無しさん
08/09/22 00:32:18
>>481
書くべき事がたりませんでした。。。
では更に、例えば前に入れたものよりn単位以上軽いものは配置してはいけない
というような、ソート後にだめだという事がわかってしまう場合はどうでしょうか？

484:デフォルトの名無しさん
08/09/22 02:43:01
DP使うしかないんじゃない？

485:デフォルトの名無しさん
08/09/23 09:49:23
>>480
状態を (現在の重さ，最後に入れた重さ，現在の価値) という三つ組みで持つ．

重さが自然数であれば，品数を n，重さの最大値を W としたとき
普通の動的計画法に基づく O(n W) アルゴリズムを修正すれば
O(n^2 W) のアルゴリズムが簡単に作れる．

重さが実数であれば，基本的には枝刈り探索しかないのだから，
上の三つ組みを持って適当に探索する．
本気を出すなら，品数や重さなどによって適切な探索法が変わるけど
そこまでがんばるかい？

486:デフォルトの名無しさん
08/09/23 11:07:05
>>482
もうググって見つけたかもしれないけれど，
1 に関しては平面走査型アルゴリズム（plane sweeping）が考えられる：
・y 軸に平行な直線を考える（走査線と呼ぶ）
・走査線を x = -∞ → +∞ に移動させていく．
・走査線に新たな矩形が乗ったら走査線上の矩形とだけ描画判定を行う．

走査線は y 座標でソートされた二分探索木を用いると，
描画判定を行うべき矩形を O(log n + k) 程度で列挙できる．
二分探索木を管理するのが面倒ならリストで持ってもよいが，
これだと列挙に O(n) かかる．
（矩形がそれなりに散らばっていれば，現実的には相当改善する）

こういうのは「線分交差列挙」などで調べると参考になると思う．
ちなみに矩形が動的に増えたり減ったりするような状況設定なら，
空間分割木などの幾何データ構造を使うことになる．

2 に関しては，描画の段階でなくて，データの段階でどうなるかが問題．

もしデータの段階で「連続した線分の集まり」と思ってよいなら，
1 の平面操作型アルゴリズムに走査線に線分が交わったら云々を追加するだけ．

それがダメなら，扱う曲線のデータ構造が分からないと，どうしようもない．
たとえば『曲線の方程式 (x(t), y(t)) が与えられる』くらいだと，
曲線と矩形の交差を全チェックするしかない．

487:デフォルトの名無しさん
08/09/25 01:27:20
ポリオミノ自動生成アルゴリズムって、起点を中心にどんどん成長させていって、
それぞれ検証する意外に、もっと早そうな根本から違うアルゴリズムって有るかな。

488:デフォルトの名無しさん
08/09/25 19:54:18
自動生成って何？

指定したサイズのもの全てとか、小さい順とかで列挙すること？
それとも、条件を満たすもののサンプリング？

489:デフォルトの名無しさん
08/09/25 21:02:22
nの数を与えて、その全パターンを出すアルゴリズムです。
n=7なら、108通り全部とか。

490:デフォルトの名無しさん
08/10/19 01:32:31
あげ

491:デフォルトの名無しさん
09/01/18 20:54:29
age

492:デフォルトの名無しさん
09/01/19 19:28:43
良スレの予感

493:デフォルトの名無しさん
09/01/19 23:10:09
DBMについて興味があり、最近書籍やウェブなどをあたっていました。
B-Treeなどのアルゴリズムについてなんとなく理解したのですが、
それをどのように外部記憶上に保存するのかについてあまり見つかりませんでした。
C言語で実装されているソースの解説などどこかにあるでしょうか。
もう少し実力があればTokyoCabinetなどを解析すればよいのでしょうが、
ちょっと敷居が高いです。

494:デフォルトの名無しさん
09/01/20 01:02:00
いきなりF1に乗ろうとする奴っているよね。