スポンサーリンク

グラフィック系アルゴリズムに役立つ「計算幾何学」の入門用ノートPDF (Computational Geometry)


CGやゲーム開発にも役立つ計算・幾何学(けいさん・きかがく)の教科書。

点・線分などの図形を数値計算する時に必要なアルゴリズムを勉強できる。


プログラミングにすごく役立つ。

複雑な図形どうしの関係を,三角形や木構造を使ってシンプルに考えられるようになり面白い。


たとえば…

  • 平面上に,たくさんの点が存在する。点の分布にしたがって領域を分割し,境界線を描画したい。勢力図やテリトリーを生成したい。(=ボロノイ図
  • 複雑な形の部屋で,監視カメラで全体を見渡す。部屋中をもれなく監視するには,どこにいくつカメラを置けばいいか?(=美術館問題,領域の三角形分割)
  • 地図上で,川が国境をまたぐのはどこ?(=線分の交差問題
  • 点とエリアの「当たり判定」をしたい。地図上の1点を選んだとき,その点がどの国に属するのかを高速に求めたい(=点位置決定問題
  • 平面上に,たくさんの点が存在する。すべての点をカバーするようなエリアを定めたい。すべての点を内部に含むような1つの多角形(または円)を作るには?(=凸包問題

こういったグラフィカルな問題を扱うのが計算幾何学。

コンピュータ・グラフィクスの重要な知識だ。


※なお,この手の図形的問題をさらに解析的に扱うためには,積分幾何学のノートもあわせて学習するとよい。

※図形から構造の概念だけを抽出し,グラフ構造として考えることも多い。グラフ理論の教科書を読んでおくとよい。

計算幾何学を勉強するためのテキスト

日本語で学べる資料:

情報科学コース『数理科学特論』ならびに情報科学科3年『応用幾何学』のページ
http://www.kanenko.com/~kanenko/KOUGI...

  • お茶の水女子大。

第1回 凸包の計算.
第2回 線分交又.
第3回 面分交又.
第4回 三角形分割.
第5回 三角形分割から半平面交叉へ.
第6回 線型計画法.
第7回 Kd 木.
第8回 領域探索の続き.
第9回 点の位置特定
第10回 ロボットモーション立案
第11回 ボロノイ図
第12回 ドロネー3角形分割


Blogopolisから学ぶ計算幾何:連載|gihyo.jp … 技術評論社
http://gihyo.jp/dev/serial/01/geometry

  • TopHatenarなどのWebサービスの実装に使われた技術を解説。サンプルコードつき。

第1回 直線の幾何
第2回 線分の幾何
第3回 平面走査法による線分の交差検出(前編)
第4回 平面走査法による線分の交差検出(中編)
第5回 平面走査法による線分の交差検出(後編)
第6回 多角形の幾何(前編)
第7回 (臨時回)線分の交差判定再訪
第8回 多角形の幾何(後編)
第9回 凸多角形の交差計算(前編)
第10回 凸多角形の交差計算(後編)
第11回 ボロノイ図の作成(前編)
第12回 ボロノイ図の作成(後編)


Computational Geometry - Lecture Notes
http://i-health.u-aizu.ac.jp/CompuGeo...

  • 会津大の講義資料スライド。

第一章 基本概念
第二章 線分交差
第三章 凸包
第四章 ボロノイ図
第五章 ドローネ三角形分割
第六章 幾何的領域探索
第七章 多角形の三角形分割



計算幾何学の問題のジャンルがリストになっているページ:

計算幾何学(computational geometry)
http://www.triplefalcon.com/Lexicon/G...

  • 引用:計算幾何学(computational geometry) は、おそらく最も工学上の応用が多い数学分野の一つです。...人間が紙に描くことができる図形上の学問に、計算量的な考察を加えた研究分野全般を計算幾何学という


Computational Geometry
http://isotope.sist.chukyo-u.ac.jp/le...

  • 引用:計算幾何学は,幾何学に計算の複雑さの理論を導入し, 幾何学的な問題に対する効率の良いアルゴリズムを開発,またはその問題の難しさを解析する計算機科学の一分野である.


英語で読める教科書:

Introduction to Computational Geometry - arbintrocgtrichy.pdf
http://www.tcs.tifr.res.in/~workshop/...

  • インドの統計学研究所,106ページのスライド。

1 Introduction
2 Area Computation of a Simple Polygon
3 Point Inclusion in a Simple Polygon
4 Line Segment Intersection: An application of plane sweep
5 Convex Hull: An application of an incremental algorithm
6 Art Gallery Problem: A study of combinatorial geometry


Computational Geometry
http://www.cimec.org.ar/~ncalvo/DeBer...

  • 367ページ。

Lecture Notes | Computational Geometry | Mechanical Engineering | MIT OpenCourseWare
http://ocw.mit.edu/courses/mechanical...

  • MITの講義資料。有限要素法も扱っている。


Computational Geometry
http://www.robots.ox.ac.uk/~ian/Teach...

  • オックスフォード大の講義資料。

Lecture1:Euclidean,similarity,projective transformations. Homo-geneous coordinatesandmatrices. Coordinateframes.
Lecture2:Perspective projection and its matrix representation. Vanishing points. Applications of projective transformations.
Lecture3:Convexity of point-sets, convexhull and algorithms. Conics and quadrics,implicit and parametric forms,computation of intersections.
Lecture4:Bezier curves,B-splines.Tensor-product surfaces.



関連する記事:

ゲーム理論の講義ノートPDF。応用を含めた講義資料 (戦略と意思決定の方法論)
http://language-and-engineering.hatenablog.jp/entry/20140516/GameTheoryPDFNot...


大学の「情報理論」(暗号理論を含む) の講義ノートPDF。代数学を使った情報量・符号化・通信路の理論
http://language-and-engineering.hatenablog.jp/entry/20140519/InformationTheor...


「解析力学」の講義ノートPDF。Webで入手可能なテキスト(演習問題と解答付き)
http://language-and-engineering.hatenablog.jp/entry/20140518/AnalyticalMechan...


「現代制御理論」の教科書PDF。状態方程式を使った制御工学の講義ノート(問題と解答つき)
http://language-and-engineering.hatenablog.jp/entry/20140618/ModernControlThe...