7

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

我想找到u从 vertex 中“可见”的同一多边形的任何其他顶点v。v可见我的意思是，在多边形之间和u完全位于多边形内部的线段。

O(N)有没有一种算法可以及时或更好地做到这一点？有没有一种算法可以及时找到所有可见的顶点O(N)？

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

4

5 回答 5

7

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

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

Joe & Simpson 在 1985 年发表了一篇非常好的论文，“Visibility of a simple polygon from a point”，提供了经过仔细验证的伪代码：（PDF 下载链接）。从那以后，这肯定已经用多种语言实现了很多次。例如，在Wikipedia 文章中有一个关于该主题的链接。

于 2012-11-21T02:08:59.497 回答
2

我修改了算法，因为它不正确。我希望这次它涵盖所有情况！

从反射a开始，让a'下一个顶点并跟随多边形，直到找到一条与a--a'相交的边a'，让b成为该边与线a--a的交点'和c边缘的终点（a--c右侧的那个）。

现在继续穿过多边形的边，如果边从左到右穿过线段a--b ，则将b设置为新的交点，将c设置为结束顶点。当你完成时，我们有一个三角形a--b--c。现在再次从c开始查看每个顶点，看看它是否在三角形a--b--c内，在这种情况下，将c设置为新顶点。最后a--c是多边形的对角线。

这是 C 中的一个实现，它假设反射点a在 中P[0]：

struct pt {
    double x,y;
    friend pt operator+(pt a, pt b){a.x+=b.x; a.y+=b.y; return a;}
    friend pt operator-(pt a, pt b){a.x-=b.x; a.y-=b.y; return a;}
    friend pt operator*(pt a, double k){a.x*=k; a.y*=k; return a;}
    bool leftof(pt a, pt b) const{
        // returns true if the *this point is left of the segment a--b.
        return (b.x-a.x)*(y-a.y) - (x-a.x)*(b.y-a.y) > 0;
    }
};
pt intersect(pt a, pt b, pt c, pt d){// (see O'rourke p.222)
    double s,t, denom;
    denom = (a.x-b.x)*(d.y-c.y)+ (d.x-c.x)*(b.y-a.y);
    s = ( a.x*(d.y-c.y)+c.x*(a.y-d.y)+d.x*(c.y-a.y) )/denom;
    return a + (b-a)*s;
}
/**
    P is a polygon, P[0] is a reflex (the inside angle at P[0] is > pi).
    finds a vertex t such that P[0]--P[t] is a diagonal of the polygon.
**/
int diagonal( vector<pt> P ){
    pt a = P[0], b = P[1]; //alias
    int j=2;
    if( !b.leftof(a,P[j]) ){
        // find first edge cutting a--b to the right of b
        for(int k = j+1; k+1 < int(P.size()); ++k)
            if( P[k].leftof(a,b) && P[k+1].leftof(b,a) && b.leftof(P[k+1],P[k]) )
                j = k,
                b = intersect( a,b,P[k],P[k+1] );
        // find nearest edge cutting the segment a--b 
        for(int k = j+1; k+1 < int(P.size()); ++k)
            if( P[k].leftof(a,b) && P[k+1].leftof(b,a) &&
                a.leftof(P[k+1],P[k]) && b.leftof(P[k],P[k+1]) ){
                b = intersect( a,b,P[k],P[k+1] );
                j = k+1;
            }
    }
    for(int k = j+1; k+1 < int(P.size()); ++k)
        if( P[k].leftof(a,b) && P[k].leftof(b,P[j]) && P[k].leftof(P[j],a) )
            j = k;
    return j;
}
于 2012-11-20T00:15:04.403 回答
0

您可以在O(n)时间内测试任何单个顶点，从而在O(n^2)中测试所有顶点。要测试是否有任何单个顶点U从V可见，请在V和U之间构建线。让我们称这条线为 L。现在，测试L以查看它是否与任何多边形边相交。如果不是，则U不会被V遮挡。如果是，则U 被遮挡。

此外，您可以测试L是否位于多边形内，如下所示：假设V上的入射边是E1和E2。计算E1和E2之间（称为a1）和E1和L之间（称为a2）的有符号角。a2的符号应与a1相同（即L与E2在E1的“同一”侧），并且a2应小于a1（即L '在' E2之前）。

小心你的相交测试，因为L将与入射到V的多边形边相交。您可以忽略这些交叉点。

此外，如果U共享与V相关的任何边，则U从V中很容易看到。

于 2012-11-17T11:02:22.823 回答
0

您可以使用多边形的三角剖分。

假设您有一个 triangulation ，则可以通过检查三角剖分中的相关内部边来找到顶点的T一组可见顶点。具体来说，如果遍历连接到的三角形集合并识别出内部边（出现两次的那些！），则该集合是除 之外的所有边顶点。UVVUV

请注意，这不一定是来自 的所有可见顶点V，只是一个带有|U| >= 0 (必须是来自 V 的至少一个内部边)的集合。不过它是有效的——只有访问的三角形/边的数量O(m)在哪里m，这本质上是O(1)为了合理的输入。

当然，您需要先建立一个三角测量。有一些有效的算法允许内置约束 Delaunay 三角剖分O(n*log(n))，但这并不完全O(n)。可以在Triangle和CGAL中找到良好的约束 Delaunay 实现。

于 2012-11-17T11:33:51.393 回答
0

只需继续通过以 V 开头的顶点并更新可见顶点列表即可。如果我没有错过任何东西，那将是 O(n)。

为简单起见，我们称 V 可见。

我已经尝试了一天用文字来表达，失败并使用了伪代码:)

visible_vertices = {V}
for each next segment in counter-clockwise polygon traversal
  if segment is counter-clockwise (looking from V)
    if (visible_vertices.last -> segment.end) is counter-clockwise
      visible_vertices.add(segment.end)
  else
    while segment hides visible_vertices.last or segment.start=visible_vertices.last
      visible_vertices.remove_last
于 2012-11-18T07:01:41.613 回答