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

5 回答

• 0

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

  ElGindy和Avis，“用于计算点的可见性多边形的线性算法”，J . Algorithms 2,1981，p . 186--197 .

  有一篇非常好的论文，Joe＆Simpson，1985，"Visibility of a simple polygon from a point,"提供经过仔细验证的伪代码：（PDF download link） . 自从多种语言以来，这肯定已经实施了很多次 . 例如，the Wikipedia article on the topic处有一个链接 .

  回复于 2024-05-03T12:54:06+08:00
• 6

  我修改了算法，因为它不正确 . 我希望这次它涵盖了所有案例！

  从反射a开始，让'下一个顶点并跟随多边形，直到找到一条与a'中的a'相交的边，让b成为该边与a的交点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;
  }
  

  回复于 2024-05-03T12:54:06+08:00
• 0

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

  此外，您可以测试 L 是否位于多边形内，如下所示：假设 V 上的事件边缘为 E1 和 E2 . 计算 E1 和 E2 （调用此 a1 ）之间以及 E1 和 L 之间的有符号角度（调用此 a2 ） . a2 的符号应与 a1 相同（即， L 位于 E1 的'same'侧， E2 为）， a2 应小于 a1 （即 L 'comes before' E2 ） .

  小心你的相交测试，因为 L 将与 V 事件的多边形边缘轻微相交 . 您可以忽略这些交叉点 .

  此外，如果 U 共享发生在 V 的任何边缘， U 从 V 可以轻易看到 .

  回复于 2024-05-03T12:54:06+08:00
• 2

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

  假设您有一个三角测量 T ，可以通过检查三角测量中的相关内部边缘找到顶点 V 的一组可见顶点 U . 具体来说，如果遍历附加到 V 的三角形集并且标识了内部边（那些出现两次！），则集 U 是除 V 之外的所有边顶点 .

  请注意，这不一定是来自 V 的所有可见顶点，只是一个带有 |U| >= 0 的集合（必须至少是V的一个内部边缘） . 虽然它是有效的 - 只有 O(m) 其中 m 是所访问的三角形/边的数量，对于合理的输入基本上是 O(1) .

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

  回复于 2024-05-03T12:54:06+08:00
• 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
  

  回复于 2024-05-03T12:54:06+08:00