幾何計算でお困りの方へ
幾何計算のソフトウエアを作ったはずなのに、 うまく動かなくて落ち込んでいる方へ
ご心配なく、落ち込む必要はありません。
うまく動かないのは、あなたのせいではありません。理論家の 責任なのです。
「計算幾何学」という名のもとに作られているアルゴリズムは、 そのままプログラムに書きなおしても、正常に走るわけではありません。 なぜなら、それらのアルゴリズムは、「誤差は生じない」と 仮定した架空の世界で設計されているからです。誤差の生じる 現実のコンピュータで動作が保証されているわけではありません。
だから、そんなアルゴリズムをそのままプログラムへ翻訳しても、 うまく走らないのは当たり前です。プログラミングの腕が悪いからでは ありません。
正常に動作するソフトウエアを作るためには, 誤差を考慮した別の技法が必要です。
実際、二つの強力な方法があります。
その１ 誤差も例外もない世界を作る方法 （厳密計算と記号摂動の利用）
多倍長計算を利用して、誤差の発生しない閉じた世界を作ります。 さらに、無限小を表す記号を導入して、例外のない世界を作ります。 したがって、誤差も例外もないと思って、一般の場合の プログラムを作るだけで十分です。出来上がったプログラムは、 例外があっても安定して動作します。ただし、多培長計算を 使うので、処理速度は落ちます．これは、初心者向け技術と言えるでしょう。
解説書
杉原厚吉：「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
杉原のホームページへ