一种线性时间算法,用于查找从其他顶点可见的多边形的任何顶点

假设有一个没有孔的多边形和由n个顶点定义的自交叉(即简单多边形).选择此多边形的反射顶点v.

我想找到从顶点v“可见”的同一多边形的任何其他顶点.通过可见我的意思是,v和u之间的线段完全位于多边形内.

是否有算法在O(N)时间或更好的时间做到这一点?是否有算法可以在O(N)时间内找到所有可见顶点?

一项快速研究表明,对于给定的多边形和该多边形内的任何点,可以用O(N)构造visibility polygon.我假设找到一个可见的顶点应该更容易.

这个问题在30年前解决了:

ElGindy and Avis, “A linear algorithm for computing the visibility polygon from a point”, J. Algorithms 2, 1981, p. 186–197.

乔和& amp;有一篇非常好的论文. Simpson,1985,“一个简单多边形的可见性”,提供经过仔细验证的伪代码:
(PDF download link).
自从多种语言以来,这肯定已经实施了很多次.
例如,the Wikipedia article on the topic有一个链接.

相关文章
相关标签/搜索