幾何計算でお困りの方へ
幾何計算のソフトウエアを作ったはずなのに、
うまく動かなくて落ち込んでいる方へ
ご心配なく、落ち込む必要はありません。
うまく動かないのは、あなたのせいではありません。理論家の
責任なのです。
「計算幾何学」という名のもとに作られているアルゴリズムは、
そのままプログラムに書きなおしても、正常に走るわけではありません。
なぜなら、それらのアルゴリズムは、「誤差は生じない」と
仮定した架空の世界で設計されているからです。誤差の生じる
現実のコンピュータで動作が保証されているわけではありません。
だから、そんなアルゴリズムをそのままプログラムへ翻訳しても、
うまく走らないのは当たり前です。プログラミングの腕が悪いからでは
ありません。
正常に動作するソフトウエアを作るためには,
誤差を考慮した別の技法が必要です。
実際、二つの強力な方法があります。
その１ 誤差も例外もない世界を作る方法
（厳密計算と記号摂動の利用）
多倍長計算を利用して、誤差の発生しない閉じた世界を作ります。
さらに、無限小を表す記号を導入して、例外のない世界を作ります。
したがって、誤差も例外もないと思って、一般の場合の
プログラムを作るだけで十分です。出来上がったプログラムは、
例外があっても安定して動作します。ただし、多培長計算を
使うので、処理速度は落ちます．これは、初心者向け技術と言えるでしょう。
解説書
- 杉原厚吉：「FORTRAN 計算幾何プログラミング」, 岩波書店，東京，1998.
- 杉原厚吉：「計算幾何工学」，培風館．東京，1994.
- 杉原厚吉：幾何アルゴリズムの数値誤差対策．伊理（監）、腰塚（編）：「計算
幾何学と地理情報処理」，第２版，共立出版，東京, 1993, pp. 259-269.
- 佐々木，今井，浅野，杉原：「計算代数と計算幾何」．岩波講座応用数学，方法９，
岩波書店，東京，1995 pp. 146-152.
適用例
- 多面体の集合演算
杉原、伊理：計算誤差による暴走の心配のないソリッドモデラの提案．
情報処理学会論文誌, vol. 28 (1987), pp. 962-974.
- ２次元ボロノイ図の構成法
K. Sugihara: A simple method for avoiding numerical errors and degeneracy
in Voronoi diagram construction. IRICE Transactions on Fundamentals of
Electronics, Communications and Computer Sciences, vol. E75-A (1992), pp. 468-477.
- ３次元凸の構成法
K. Sugihara:
- ４次元凸の構成法
K. Sugihara:
- そのほかにも，参考文献はありませんが，２次元ラゲールボロノイ図，球面ボロノイ図、
３次元ドロネー図などに適用したプログラムソースコードを
幾何計算ソフトウエア
で公開しています．
その２ 誤差が発生しても正常に動くプログラム（位相優先設計法）
対象の位相的性質の保持を、数値計算結果より優先させることに
よって、破綻を防ぎます。浮動小数点計算が使えるので、計算速度が
早いという利点をもっています。ただし、対象の位相的性質を
抽出しなければなりませんから、問題ごとの個別の工夫が必要です。
中級技術といえます。
解説書
- 杉原厚吉：「計算幾何工学」，培風館．東京，1994.
- 杉原厚吉：幾何アルゴリズムの数値誤差対策．伊理（監）、腰塚（編）：「計算
幾何学と地理情報処理」，第２版，共立出版，東京, 1993, pp. 259-269.
- 杉原厚吉：幾何アルゴリズムの位相優先設計法．室田（編）：「離散構造と
アルゴリズム III」，近代科学社，東京，1994, pp. 35-76.
- 佐々木，今井，浅野，杉原：「計算代数と計算幾何」．岩波講座応用数学，方法９，
岩波書店，東京，1995, pp. 152-157.
適用例
- ２次元ボロノイ図の逐次添加構成法
K. Sugihara and M. Iri: Construction of the Voronoi diagram for "one million"
generators in single-precision arithmetic. Proceedings of the IEEE, vol. 80 (1992),
pp. 1471-1484.
K. Sugihara and M. Iri: A robust topology-oriented incremental algorithm for
Voronoi diagrams. International Journal of Coputational Geometry and Applications,
vol. 4 (1994), pp. 179-228.
- ２次元ボロノイ図の分割統治構成法
Y. Oishi and K. Sugihara: Topology-oriented divide-and-conquer algorithm for
Voronoi diagrams. Computer Vision, Graphics, and Image Processing, vol. 57 (1995),
pp. 303-314.
- ２次元線分ボロノイ図の構成法
今井，杉原：誤差による破綻の心配のない線分Voronoi図の構成算法．情報処理学会
論文誌，vol. 35 (1994), pp. 1966-1977.
- ２次元一般図形ボロノイ図の構成法
K. Sugihara: Approximation of generalized Voronoi diagrams by ordinary Voronoi
diagrams. Computer Vision, Graphics, and Image Processing, raphical Models and
Image processing, vol. 55 (1993), pp. 522-531.
- ３次元凸包の分割統治構成法
T. Minakawa and K. Sugihara
- ３次元凸包の包装法
K. Sugihara: Robust gift wrapping for the three-dimensional convex hull.
Journal of Computer and System Science, vol. 49 (1994), pp. 391-407.
- ３次元ボロノイ図・ドロネー図の構成法
稲垣，杉原，杉江：３次元ボロノイ図構成のための数値的に安定な逐次添加法．情報処理
学会論文誌，vol. 35 (1994), pp. 1-10.
稲垣，杉原：３次元ドロネー図の構築における退化に起因する問題点とその対策．電子
情報通信学会論文誌, vol. J79-D-II (1996), no. 10, pp. 1696-1703.
- 凸多面体の平面切断
K. Sugihara: A robust and consistent algorithm for intersecting convex polyhedra.
Computer Graphics Forum (EUROGRAPHCS'94, September 1994, Oslo, Norway), vol. 13
(1994), pp. C45-C54.
現場でお困りのソフトウエア技術者の皆さん、
どうぞ、気軽にご相談ください。
杉原厚吉 sugihara@mist.i.u-tokyo.ac.jp