Entry

今日買った本 - 『計算幾何―理論の基礎から実装まで』

2009年01月11日

仕事……でもないんだけれども,画像解析をゴニョゴニョやっていることもあって購入。

計算幾何―理論の基礎から実装まで (アルゴリズム・サイエンスシリーズ―数理技法編)
浅野 哲夫
共立出版
売り上げランキング: 138569
おすすめ度の平均: 1.0
1 タイトルに偽りあり

Amazon では,実装の詳細がないとかいった,甘ったれた評価があるけれども,この手の本を読む人は,理屈を聞いて実装に起こせる人が当然対象になっているわけで,ミスマッチだったと言わざるをえません。実装の詳細を手取り足取り教えてもらいたい方は,別の本で下積みする必要があるんだと思います。どんぴしゃ(死語)な書籍は思い浮かばないのだけれど,ゲームプログラミング関連のあたり書籍が,割と丁寧に実装の仕方を説明しています。

ゲームプログラマになる前に覚えておきたい技術
平山 尚(株式会社セガ)
秀和システム
売り上げランキング: 265
おすすめ度の平均: 5.0
5 初級プログラマが一人でゲームをつくれるようになるための本。
5 良書です。が、ある程度のプログラミングスキルが必要

「計算幾何」という分野は,モノゴトの幾何的な性質を利用して,効率のいいアルゴリズムを開発したり,アルゴリズムの評価をしたりする研究分野です(p1)。数学にいう幾何学とは,ちょっと違う。直接的な応用としては,例えば,「プリント基板の効率のいい配線方法を見つけるアルゴリズムを開発する」なんてお題に適用できます。素朴に考えて,O(n2) で解いてもいいんですけれど,もっと効率的なやり方がある。もっとも,幾何的な問題に解決できれば適用できる分野なので,問題系が画像処理に限られるわけじゃありません。

本書では,平面幾何が対象としている基本的な問題群とその考え方について,概説的に説明しています。Amazon の書評では,実装の詳細がないとかいったぼやきがあるけれども,扱っている問題群に関する限り,基本的なアルゴリズムの検討があるので,実装に起こすのは難しくないはず。丁寧に説明しているところでは,C に類似した擬似言語で説明されているし,むしろ親切だと思うくらいです。

一方,個人的に記述が不足していると思ったのは,第5章の「基本的なアルゴリズム設計技法」の箇所。再帰やDP(動的計画法)が説明されているんですけれど,DP ですら7ページしか記述がない。もっとも,ここら辺はまともに扱うと1冊本ができてしまうので,いずれにしろ詳細は他書をあたる必要があるんだと思います。他の参考文献については,冒頭でしっかりこの分野の文献を紹介してくれているので,本書を読んだ後の道筋はしっかりついています。

あたしが今何をやってるのかというと,計算幾何のお題に沿っていうと「線分の交点列挙問題」をゴニョゴニョやっていたりします。いくつかの線分が与えられているところで,それぞれの線分がどこに交点を持つか(あるいは持たないか)を列挙する問題です。人間の目でみたら簡単に分かるんですけどね。コンピュータで解くとなると,コレ,ほんとに難しい。素朴に総当りでやると実用にならないし,どうにかならんのかと思っていたのでした。

この点,本書では Bentley-Ottmann のアルゴリズムが紹介されていて,そのものズバリの解法を与えています。この箇所を中心に読んでるんですけれど,いやはや……世の中には頭のいい人がいるもんだ。この他にも,この手の話になると必ずと言っていいほど問題となる,メモリ構成の話もあって(第10章),内容は十分実践的です。

ページ数の割にちと価格が高いのが難だけれども,この手の話の導入には格好の本になるはずです。

Trackback
Trackback URL:
Ads
About
Search This Site
Ads
Categories
Recent Entries
Log Archive
Syndicate This Site
Info.
クリエイティブ・コモンズ・ライセンス
Movable Type 3.36
Valid XHTML 1.1!
Valid CSS!
ブログタイムズ

© 2003-2012 AIAN