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

Question

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

我想找到从顶点 v“可见”的同一多边形的任何其他顶点 u。我所说的可见是指 v 和 u 之间的线段完全位于多边形内。

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

一项快速研究表明，对于给定的多边形和该多边形内的任何点，visibility polygon可以在 O(N) 中构造。我认为找到单个可见顶点应该更容易。

Answer 1

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

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

Joe 和 Simpson 在 1985 年发表了一篇非常好的论文，“从一个点看简单多边形的可见性”，其中提供了经过仔细验证的伪代码:(PDF download link)。从那以后，这肯定已经用多种语言实现了很多次。例如，the Wikipedia article on the topic 处有一个链接.