线性时间算法，用于查找从其他顶点可见的多边形的任何顶点 [英] A linear-time algorithm to find any vertex of a polygon visible from other vertex

问题描述

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

我想找到顶点可见的相同多边形的任何其他顶点 u v 。可见，我的意思是， v 和 u 之间的线段完全位于多边形内。

是否有一种算法可以在 O（N）时间或更好的时间内执行此操作？有没有一种算法可以在 O（N）时间内找到所有可见的顶点？ p

一项快速研究表明，对于给定的多边形和该多边形内的任意点，可以在<$ c中构建一个可见性多边形 $ C> O（N）。我认为找到一个可见的顶点应该更容易。

解决方案

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

ElGindy和Avis，从一个点计算可见性多边形的线性算法， J。算法 ，1981，p。 186--197。

Joe&辛普森，1985年，从一个角度看一个简单的多边形，提供仔细验证的伪代码：
（ PDF下载链接）。
这在很多语言中肯定已经实现了很多次。
例如，维基百科有关该主题的文章中提供了一个链接。

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:

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

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.

这篇关于线性时间算法，用于查找从其他顶点可见的多边形的任何顶点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！