検出もれのない代数曲線の追跡法

概要

論文の詳細を見る
本論文では,平面代数曲線を検出もれなく求めるための新しい算法を提案する.従来の曲線追跡法には,ノl、さなループや孤立点を検出しそこなったり,特異点の近辺で追跡に破綻をきたしたり,曲線の接続関係を誤って抽出したりするなどの欠点があったのに対して,ここに提案する算法はそれらの欠点を克服するものである.本手法では,特徴点と呼ばれる特殊な点を定義して,曲線追跡の際の出発点・終端点として用いる・これは代数曲線上に有限個存在し,代数方程式を解いて求めることができるもので,特に出発点として用いることのできる特徴点が各分枝に少なくとも1個ずつ存在することが証明できるため,検出もれの逆いことが保証される.また,追跡の際のステップ幅の自動調整機構を持つため,大きさの非常に異なる構造が混在していても,それらを効率よく検出できる.本手法の浮動小数点演算による実装法を検討し,それに基づいて試作したシステムが,多くの曲線に対して正しく追跡が行えることを示す.さらにその算法を利用して,二つの代数曲面の交線を求める算法を構成する.最後に本手法のソリッドモデリング,等高線図の描画,代数曲面の描画への応用について例とともに述べる.
1992-10-15