可視多角形アルゴリズム

概要

論文の詳細を見る
可視多角形とは、多角形の内部の点から見える点の集合で星状多角形を成しているものである。ここでは、単純な多角形の内点からの可視多角形を求めるアルゴリズムを述べる。単純な多角形において、内点からの可視多角形を求める問題は、一般にO(n)の処理時間を有する算法が知られている。それらの算法の中で、アルゴリズムが単純でかつ、効率がよいとされるLEEの算法では、多角形を一巡しながら、その時点までの可視多角形を求める方式をとっている。そのため、最終的には隠れてしまう、見える領域と見えない領域の境界点(視線と辺との交点)をも求めてしまう。また、可視点の探索は、視線と辺との交差判定により行っている。一方、本アルゴリズムでは、前処理により、各頂点に多角形の構造的な情報を与えることによって、可視点の探索を外積計算のみで行えるようにした。そのため、手間はO(n)であるが、LEEの算法と比較した結果、多角形の頂点数が増加していった場合の処理時間の増分をLEEの算法より少なくすることができた。本論文では、はじめにLEEの算法とその問題点を示し、次に本アルゴリズムを述べる。
一般社団法人情報処理学会の論文
1989-10-16