定性計算幾何学の提案

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

本研究では,2次元空間における,線分,多角形を対象として,点の定量的座標値ではなく,座標値同士の大小関係に基づく定性的な計算幾何アルゴリズムを考案した.これによって,点の座標が数値的に確定していない状態でも,定性的な条件に基づいて,点と直線の位置関係判定,線分同士の交差可能性判定,多角形による点の包含可能性判定等が行なえることを示した.また,座標値の大小関係のみでは,図形要素同士の関係が一意には確定しない場合も存在するため,適切な場合分けを行い,仮定,分岐,後戻りを含めた非決定的処理を行なうアルゴリズムを考案した.これによって,従来の定量的な計算幾何学で行なわれているような,座標の条件から図形の関係を判定するだけではなく,図形の関係が与えられれば,それを可能にする座標の定性的条件を生成することも可能になった.これは,設計仕様として与えられた条件を満足する機器の配置や部品の形状を生成する設計問題の支援等において,特に有効と考えられる特長である.次に,考案した定性的アルゴリズムを計算機上にライブラリ・プログラムとして実装した.処理の大部分が,数値的計算ではなくパターン・マッチングを中心とした記号的推論となり,並列的に処理可能な定性的場合分けを生じるという点を考慮し,プログラム言語として第五世代コンピュータプロジェクト研究成果である並列論理型言語KL1を用いた.実装した定性計算機何ライブラリを,定性的レイアウト問題,定性的障害物回避経路探索問題,線分の交差に基づき列車運行を計画する定性的列車ダイアグラム問題に適用した.その結果により,提案した定性計算幾何および実装した定性計算幾何ライブラリの有効性を検証した.さらに,今後の展開の可能性および問題点,考えられる応用分野などについて考察を行なった.