整合的な公差に基づく多角形の頑健な集合演算

概要

論文の詳細を見る
与えられた2つの多角形の集合和や積,差を計算する集合演算は,図形処理における基本的な演算のひとつである.図形処理では,幾何的な諸量の算出や判定を,浮動小数点演算を用いて行う.浮動小数点演算では,数値誤差の発生が不可避なため,得られた結果に矛盾が生じやすく,最悪の場合処理が破綻してしまう. このような矛盾の多くは,近接した幾何要素の順序を取り違えることで生じる.そこである微小な公差値よりも接近している2要素を一致していると見なし,順序の逆転を防止することが経験的に行われている. しかし従来の手法では,公差の導入が新たな矛盾の原因となる場合が多く,問題の解決になっていなかった.多角形の集合和が計算できれば,積や差の計算は容易である.そこで集合和を計算するための位相的な条件を導出し,処理に必要な幾何的判定の手続きを, この条件を満たすように定義した.そしてこの判定を,辺と頂点に定義された公差域に基づいて,整合的に行うように拡張することで,多角形の集合和を安定に計算する手法を開発したので報告する.実際にプログラムを作成し,数値実験により手法の有効性を検証した.
1996-06-15