幾何の計算にコンピュータを使う
　 易しくない計算幾何学

最初のページ

はじめに

1.　座標系と長さの概念

1.1　初等幾何学での作図

1.1.1　作図法の公理は二つしかない

1.1.2　作図法は別に研究されたこと

1.1.3　形と寸法を言葉で伝える方法を考える

1.1.4　コンピュータに作図させるとき

1.2　座標系の約束

1.2.1　碁将棋の記録も座標系が使われる

1.2.2　住所表記も座標系の概念を踏まえていること

1.2.3　幾何学的な国境線は土木技術者が設定したこと

1.2.4　他人に道順を教えるとき

1.2.5　図学で扱う投影面

1.2.6　右手系の直交座標系

1.3　長さの理解

1.3.1　長さは身体の寸法を基準として理解する

1.3.2　１マイルは1000歩の長さであること

1.3.3　メートル法は地球の寸法から決めたこと

1.3.4　測量の基本は歩いて距離を測ること

1.4　コンピュータグラフィックスの座標系

1.4.1　世界座標と擬似的なカメラを考える

1.4.2　ウインドウの概念

1.4.3　グラフィックス装置の制御

1.4.4　装置座標系

1.4.5　ビューポートの定義方法

1.4.6　ウインドウ・ビューポート変換

2.　図形要素の代数的表現

2.1　幾何学要素の数値表現

2.1.1　文字を使って抽象的に表すこと

2.1.2　右手系の直交座標系を使うこと

2.1.3　幾何学的要素を表す型を考えること

2.1.4　寸法の表し方が必要になること

2.1.5　数値計算の精度を決めておくこと

2.2　点とベクトル

2.2.1　複数の数の組を扱う約束が必要

2.2.2　点は次元を持つ量である

2.2.3　ベクトルは代数学的に扱うことが多い

2.2.4　幾何で扱うマトリックスはベクトルの集合とする

2.3　線分・直線・面の表し方

2.3.1　線分は図形要素と考える

2.3.2　直線を代数式で表す種々の方法

2.3.3　直線からの距離が簡単に計算できること

2.3.4　原点からの距離がマイナスｃになること

2.3.5　空間直線は現実感が得にくいこと

2.3.6　幾何学的な平面はもっと実感し難いこと

2.4　簡易投影法

2.4.1　幾何の説明には図が無いと困ること

2.4.2　平面図形も三次元図形の特別な場合とする

2.4.3　球と正六面体とが自然に見えるようにする

2.5　行列を図で表示する方法

2.5.1　行列をベクトルの集合と考える

2.5.2　二次元配列を利用するときに留意すること

2.5.3　変換行列は座標系の定義であること

2.5.4　代入文が作図コマンドになっていること

3.　図形要素間の演算

3.1　定義と宣言

3.1.1　定義とは何をすることか？

3.1.2　宣言無しでいきなり変数を使う

3.1.3　デフォルトの初期値の扱い

3.2　代数式の解釈

3.2.1　代数式は文章を記号化した表現であること

3.2.2　数学書の表記法にこだわらないこと

3.3　代入文の解釈

3.3.1　数学の等式とは意味が違うこと

3.3.2　代入文は数学的に見れば不正確な処理であること

3.3.3　代入規則を感覚的に設計する

3.3.4　図形要素の代表点を考える

3.3.5　図形間の代入文の約束も感覚的に決めたこと

3.4　加算と定数倍

3.4.1　ベクトルの算法でお馴染みである規則

3.4.2　ベクトルの加算は平行移動を行わせる

3.4.3　スカラー倍は原点を中心とした相似な図形変換であること

3.4.4　向きを変えることと(-1)倍とは別の意味で使うこと

3.5　積の約束

3.5.1　掛け算と乗算と積はどう違うか

3.5.2　交換律が成り立たない場合がある

3.5.3　論理積もあること

3.6　連結を扱う演算の約束

3.6.1　線分は2点を結んで作ること

3.6.2　演算結果の通知情報にFLAGを使う

3.6.3　二円の共通接線を求める

3.6.4　連結演算子 @ を論理和でも使う

3.7　干渉の計算

3.7.1　干渉の有る無しを数量化する

3.7.2　干渉結果の性質を通知するパラメータが別に要ること

4.　初等幾何学の作図例題

4.1　基本的な作図法

4.1.1　GBASICは数値計算が主目的であること

4.1.2　GBASICを利用する作図法

4.2　三辺を与えて三角形を作図する

4.3　三角形の垂心を求める

4.4　三角形の内接円を求める

4.5　三角形の傍心を求める

4.6　三角形の九点円

4.7　三角形の六点円

4.8　ミケル（Miquel）の五点円

4.9　高田の五点円

4.10　四面体の外接球を求める

4.11　四面体の内接球を求める

4.12　ボロノイ図の作図

5.　土木工学と曲線

5.1　地球の上の作図

5.1.1　東西南北を正確に合わせる

5.1.2　座標値を求めることは難しい

5.1.3　鉄道や高速道路は大きな曲線を使う

5.1.4　道順を教えるときにも世界座標と局所座標を使い分ける

5.1.5　道路と鉄道の線形は立体曲線であること

5.2　二次曲線と三次曲線

5.2.1　自由曲線は繋いで作図すること

5.2.2　連続梁の理論が応用されること

5.2.3　定数間に別の条件が要ること

5.2.4　別の媒介変数を使う

5.2.5　三角関数を使わなくても円が描けること

5.2.6　三次曲線の代数式

5.3　緩和曲線

5.3.1　鉄道線路は緩和曲線が入る

5.3.2　高さ方向にも緩和区間が必要であること

5.3.3　勾配の摺り合わせは放物線が使われる

5.3.4　クロソイド曲線

6.　幾何モデリングの序章

6.1　図形を定義する方法

6.1.1　幾何学は土地測量学であること

6.1.2　座標系が必要であること

6.1.3　道具を使う幾何学的な図形描画を用器画という

6.2　立体を表す幾何モデル

6.2.1　現実の形状はすべて立体的であること

6.2.2　曲面を持たない立体形状

6.2.3　幾何モデルを何に使うのか

6.3　幾何モデルの作成

6.3.1　頭の中に想像している形状をデータ化する

6.3.2　図面作成の補助に使う場合

6.3.3　多面体データの準備方法

6.3.4　テキストファイルからデータを読み込む

6.3.5　データ確認にグラフィックスを応用する

6.3.6　三次元モデルから二次元モデルへの変換

6.3.7　展開図の作成も二次元モデルへの変換である

6.3.8　最初から平面図形モデルを作成する

6.3.9　平面図形モデルから立体モデルへの変換

6.3.10　2.5次元モデルの例題

6.4　幾何モデルの応用

6.4.1　平面図形の面積・重心・慣性モーメント

6.4.2　三角形に分割する考え方に自由度があること

6.4.3　立体図形の諸量の計算

7.　コンピュータグラフィックスの基礎

7.1　投影法の原理

7.1.1　正しい図形を描くこと

7.1.2　投影面は座標系を使わない

7.1.3　図学原理的に忠実な投影法は第一角法になる

7.1.4　透視図法では図が歪むこと

7.1.5　工業製図は幾何モデルを作図する

7.1.6　作図装置は装置座標系で制御する

7.2　座標系とカメラの概念

7.2.1　まず世界座標系を理解する

7.2.2　仮想のカメラを考える

7.2.3　カメラ本体に座標系を持たせる

7.2.4　投影変換で画像を得ること

7.2.5　正投影図は組み合わせて利用すること

7.2.6　引き伸ばしとプリントのモデル化を考える

7.2.7　単純に画像を表示するとき

7.3　投影図を作成する手順

7.3.1　カメラを使う撮影手順で考える

7.3.2　立体的な形状は投影変換が必要である

7.3.3　平面図形の位置を変える表示方法

7.3.4　立体図形の表示位置を変える方法

7.4　作図装置の制御

7.4.1　モニタはソフトコピーの道具であること

7.4.2　デバイスドライバ

7.4.3　ユーザが利用する作図命令

7.4.4　デバイスとしてのクセがあること

7.5　しきい値と言う概念

7.5.1　数値計算は技術であること

7.5.2　しきい値を決めておく

7.5.3　しきい値を応用する場面

7.5.4　マンハッタン距離で計算する

7.5.5　「丸め」を理解する

7.5.6　しきい値は丸めの前段階に使う

7.5.7　単位系を変えるときに呼び数を使う

7.5.8　誤差は相対的な値であること

8.　二直線の交点計算と応用

8.1　最も基礎的な算法

8.1.1　中学の算数では代数として表れる

8.1.2　世界座標の範囲を決めておく

8.1.3　無限に伸びる直線を考えない

8.1.4　線分に向きを考える

8.1.5　しきい値を判定に使う

8.2　代数直線の交差判定

8.2.1　直線を表す代数式の形を標準化しておく

8.2.2　二直線の成す角度を求める

8.2.3　距離もしきい値を決める必要があること

8.2.4　面の交わりについても判定が必要

8.3　平面図形の干渉処理

8.3.1　ベン図の処理を行わせる

8.3.2　領域の内外の位置関係を調べる

8.4　ハッチングの作図技法

8.4.1　領域を区別するために使う

8.4.2　ハッチングを作図するアルゴリズム

8.4.3　領域を定義するデータ作成は注意が必要

8.4.4　多面体の透視図にコントラストを付ける

8.5　投影図の隠れ線と隠れ面の処理

8.5.1　投影空間で奥行きを考える

8.5.2　面を視点順に並べ直すこと

8.5.3　コンタアークとの交差を調べる

8.5.4　立体感覚を補う作図

9.　図形の変換の数学

9.1　変換処理の分類

9.1.1　マトリックスは道具であること

9.1.2　次元の変わる変換も扱う

9.1.3　線形と一次とを区別する

9.2　代数学としての変換マトリックス

9.2.1　座標系のデータを変換マトリックスとして使う

9.2.2　幾何学的図形として理解する

9.2.3　逆変換は局所座標系から世界座標系を見ること

9.2.4　記号の並べ方に約束が増えること

9.3　回転の分類

9.3.1　移動と回転と変形とに分ける

9.3.2　回転の指定は理解が混乱すること

9.3.3　カメラを構えて被写体を狙う方法

9.3.4　一回の回転操作で済ますことができる

9.3.5　座標系の約束が違うことで混乱が起きる

9.3.6　非対称のマトリックス成分になること

9.4　変形の合成

9.4.1　弾性体の変形で考える

9.4.2　一方向に拡大または縮小させる変形

9.4.3　全体として拡大または縮小させる変形

9.4.4　固有値解析との関係

9.4.5　図形の嵌め込み問題

9.4.6　扱い易いコマンドに集約する

9.5　射影変換

9.5.1　透視図は射影変換の応用である

10.　幾何モデルのデータ構造の概説

10.1　文書にするときの書式

10.1.1　人が理解するためには文書にする

10.1.2　表の形に座標値のデータを並べる場合

10.1.3　言語によって左右が違うこともある

10.1.4　EXCELを使って表を作るとき

10.2　リストの意味

10.2.1　表を扱うときの呼び方

10.2.2　配列の寸法と基底番号を理解しておく

10.2.3　 表のデータは二次元配列を使う

10.2.4　同じメモリ領域を別の名前で参照したいとき

10.2.5　メモリの使い方を論理的に理解する

10.2.6　型の違うデータ集合を扱うとき

10.2.7　リストセルは最長バイト数を使う変数の集合で設計する

10.2.8　ポインタは住所番号に当たること

10.3　幾何モデルで使うリストセル

10.3.1　オイラーの多面体公式を踏まえる

10.3.2　頂点・辺・面ごとに個別のリストセルを設計する

10.3.3　セルの動的な利用を考える

10.3.4　食堂のお皿の使い方で理解する

10.3.5　目次に相当するスタックを準備する

10.3.6　スタックを出発点としてポインタをたどる

10.3.7　Ｃ言語はポインタ技法が使えますが…

10.4　ツリー構造の具体的な応用例

10.4.1　個別の部品をツリー構造で関連付ける

10.4.2　移動や回転もツリー構造でまとめて処理する

11.　二平面の交差計算と応用

11.1　立体幾何学の感覚的な理解

11.1.1　平面を感覚的に理解する

11.1.2　平面を理解したいときは紙状のモデルを描く

11.1.3　空間の線分を投影しても判じ絵になる

11.2　面の交差

11.2.1　多面体の干渉処理の基本は面の交差計算である

11.2.2　二平面の交差を代数式で扱う場合

11.2.3　ベクトル量を使って表す方法を考える

11.2.4　面にも向きの約束を付けること

11.2.5　二平面の交差でできる直線をベクトルの計算で求める

11.3　二面の交差線を計算するアルゴリズム

11.3.1　面の交差は有限寸法の図形の干渉で扱うこと

11.3.2　世界座標の範囲を決めておく

11.3.3　トポロジー的な構成則を保存する注意を払う

11.3.4　頂点座標は別に計算して頂点セルを作成する

11.3.5　予備的に箱の干渉で調べる

11.3.6　二面が平行であるときの判定は次章で扱う

11.3.7　交差直線と交差辺とを区別して使う

11.3.8　頂点と面との相対的な位置関係を判定する

11.3.9　辺と面との相対的な位置関係を判定する

11.3.10　交点・頂点・交差点を区別する

11.3.11　辺の交差位置の座標と区間ステータスコードを求める

11.3.12　辺の分割と交差辺の追加処理

11.4　面を周回する辺構造の調整（概説）

11.4.1　面には穴ループを持つことがある

11.4.2　干渉が生じた面についてだけループを再構築する

11.4.3　複数のループが見つかる場合がある

11.4.4　標準構造を持つループ単位で面のループをまとめる

11.4.5　紙風船単位での入れ子関係も検査する

12.　積み木モデルでの面の干渉

12.1　辺を共有する面の接触

12.1.1　現実的な合成方法をモデル化する

12.1.2　二面の干渉状態の分類をする

12.1.3　二面の交わりに凹凸の種類がある

12.1.4　凸の面接続があるときは工夫が必要になる

12.2　交差線に接続する面の判定

12.2.1　同じ辺を２回検査することになること

12.2.2　二面の交差を交差直線の向きで見る

12.2.3　どの面の対が交差辺の左右にくるか

12.3　面を周回する辺構造の調整

12.3.1　干渉が生じた多面体を一つに合わせる

12.3.2　交差線のデータが無いとき

12.3.3　交差線のデータがあるとき

12.3.4　どの面の対が交差辺の左右にくるか

12.3.5　辺ループの入れ子関係をツリー構造に組み立てる

12.3.6　ツリー構造に組み上げる手順の説明

12.3.7　面単位のツリー構造に分解する

12.4　紙風船構造としての調整

12.4.1　紙風船単位のモデル構造を考える

12.4.2　CFG構造への変換と復元