精度保証機能を有する幾何アルゴリズムの開発

点击翻译按钮获取中文摘要

計算結果の精度保証を有効に行うには,誤差の過大評価を避けることがポイントとなる.従来,頂点・線分など個々の図形要素に対して精度属性を持たせる手法が知られている.しかし,この方法を多角形の集合演算に用いた場合は誤差の過大評価が発生しやすい.さらには精度属性を持った図形要素同士は相対的な位置関係が明確に定まらないため,図形の位置関係が明確に定まるものとして設計された幾何アルゴリズムを適用するのは困難である.安定して動作する幾何アルゴリズムを設計するには図形要素間の位置関係が明確に定まることが不可欠であるという観点から,多角形の各図形要素に精度属性を持たせて間接的に精度保証を行うのではなく,精度保証された多角形が表す境界を明示的に求めるという手法について基礎検討を行った.この手法では,図形要素の位置が明確に定まることから安定した幾何アルゴリズムを設計することが可能となり,また誤差の過大評価を避けられることも分かった.本年度は昨年度に行った検討に基づき,多角形の集合演算で精度保証を行うために必要となるデータ構造・基本演算について基礎的な実装を行った.精度保証計算の基本手続きとなる「多角形頂点の丸め演算」を幾何アルゴリズムライブラリCGAL・LEDAを用いて実装し、考案法が動作することを確認した.また実装した結果から、計算精度を高くした場合の実行速度の低下が著しいことが分かり,実装レベルでの更なる工夫が必要であることも判明した.研究結果については順次とりまとめ次第発表する予定である.