移動視点からの多角形可視部分計算

概要

論文の詳細を見る
本文では並列的に配置された凸多角形物体の列に沿って移動する視点を考える。まず、視点からの多角形可視部分を計算するための簡単化された基本的なモデルとそれに関する可視性問題を設定し、次いで、それらの問題を解くアルゴリズムと計算結果を示す。凸多角形は頂点と頂点をむすぶ辺から構成されるので、その可視部分を求めるのは、頂点の可視性を考え、辺の可視性は頂点の可視性に基づいて計算すればよい。従って、可視性計算のための基本的モデルとして、xy平面においてy軸に平行に配置された半直線物体の列およびそれらの半直線物体と交差しない線上を移動する視点から構成されるというモデルを考える。さらに、それらの半直線物体の可視性は、特定の半直線物体に対して視点からの視線を遮る半直線物体はどれかを求めるという問題に帰着できるので、この問題を解く線形時間アルゴリズムを示す。また、解を可視木と呼ばれるデータ構造に構成する。ランダムな半直線物体列に対して得られた計算結果は極めて特徴的なものである。
一般社団法人情報処理学会の論文
1995-03-17