用于确定两个凹多边形之间的一对可见边的算法

Question

假设我们有两个不相交的凹二维多边形(A,B).问题是找到一组边对(每对由多边形A的一条边和多边形B的边组成),它们具有以下属性:对中的每个项必须彼此可见.如果没有障碍物(在图片中有三个案例,在这个规则被打破时用红色十字标记),则一个边缘对另一个边缘是可见的.

我知道如何使用光线和边缘顶点在O(n ^ 2)中解决这个问题.但它太慢了.

Answer 1

我认为它不能比O(n ^ 2)更快地完成.

见下图.有一个双曲线和两个多边形.每个多边形的顶点位于双曲线的分支上.

在这种情况下,两个多边形的边缘是成对可见的(除了后面的两个边缘).然后,得到的集合将包含O(n ^ 2)个边对.