n 顶点定义的自相交（即简单的多边形）。选择该多边形的反射顶点 v 。 我想找到顶点可见的相同多边形的任何其他顶点 u v 。可见，我的意思是， v 和 u 之间的线段完全位于多边形内。
是否有一种算法可以在 O（N）时间或更好的时间内执行此操作？有没有一种算法可以在 O（N）时间内找到所有可见的顶点？ p
一项快速研究表明，对于给定的多边形和该多边形内的任意点，可以在<$ c中构建一个 $ C> O（N）。我认为找到一个可见的顶点应该更容易。
解决方案这个问题在30年前解决了：
Joe&辛普森，1985年，从一个角度看一个简单的多边形，提供仔细验证的伪代码：
（）。
这在很多语言中肯定已经实现了很多次。
例如，中提供了一个链接。
Suppose there is a polygon with no holes and self-intersections (i.e. a simple polygon) defined by n vertices. Choose a reflex vertex v of this polygon.
I'd like to find any other vertex u of the same polygon which is "visible" from the vertex v. By visible I mean, that a line segment between v and u lies completely inside the polygon.
Is there an algorithm to do that in O(N) time or better? Is there an algorithm that can find all visible vertices in O(N) time?
A quick research suggests that for a given polygon and any point inside this polygon a visibility polygon can be constructed in O(N). I assume that finding a single visible vertex should be even easier.
This problem was solved 30 years ago:
There is a very nice paper by Joe & Simpson, 1985, "Visibility of a simple polygon from a point," that offers carefully verified pseudocode: (PDF download link).This surely has been implemented many times since, in many languages.For example, there is a link at the Wikipedia article on the topic.
这篇关于线性时间算法，用于查找从其他顶点可见的多边形的任何顶点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！