2

我目前正在查找具有 12 个顶点的特定形状内的坐标。

          (3,7)  (5,7)
            #######
            #     #
            #  X  #
       (3,5)#     #(5,5)
 (1,5)#######  X  #######(7,5)
      #                 #
      #  X  X  X  X  X  #
      #                 #
 (1,3)#######  X  #######(7,3)
       (3,3)#     #(5,3)
            #  X  #
            #     #
            #######
          (3,1)  (5,1)

我想找出形状内的坐标（标记为“X”），不包括构成形状的坐标。

我试过 W. Randolph Franklin 的 pnpoly ( http://www.ecse.rpi.edu/~wrf/Research/Short_Notes/pnpoly.html )，但它也将构成形状的坐标视为“在形状”。

请注意，上述形状只是一个示例。坐标可以在任何地方。

如何修改代码以使其不允许包含形状的边界？

int pnpoly(int vertx[], int verty[], int testx, int testy) {
    int nvert = 12;
    int i, j, c = 0;
    for (i = 0, j = nvert-1; i < nvert; j = i++) {
        if ( ((verty[i]>testy) != (verty[j]>testy)) && (testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i]) ) {
            c = !c;
        }
    }
    return c;
}
4

2 回答 2

2

按要排除的边框缩小形状，然后使用现有算法。

顺便说一句：不要使用int vertx[]，这是一个危险的谎言。等效的明显代码是int* vertx，这很明显它缺少const.

于 2013-05-07T15:47:20.610 回答
1

由于您有代码来测试该点是否在给定的多边形内，因此您只需要排除多边形上的那些点。注意：此测试仅在您使用整数坐标（而非浮点数）时才可靠。

struct Point {
  int X;
  int Y;
};

bool PointOnLineSegment(const Point pt, const Point linePt1, const Point linePt2)
{
  return ((pt.X == linePt1.X) && (pt.Y == linePt1.Y)) ||
    ((pt.X == linePt2.X) && (pt.Y == linePt2.Y)) ||
    (((pt.X > linePt1.X) == (pt.X < linePt2.X)) &&
    ((pt.Y > linePt1.Y) == (pt.Y < linePt2.Y)) &&
    ((pt.X - linePt1.X) * (linePt2.Y - linePt1.Y) ==
      (linePt2.X - linePt1.X) * (pt.Y - linePt1.Y)));
}

bool PointOnPolygonEdge(const Point pt, Point *poly, int vertexCnt)
{
  if (vertexCnt < 2) return false;
  vertexCnt--;
  for (int i = 0; i < vertexCnt; ++i)
    if (PointOnLineSegment(pt, poly[i], poly[i+1])) 
      return true;
  if (PointOnLineSegment(pt, poly[vertexCnt], poly[0])) return true;
  return false;
}


编辑（2018 年 12 月 8 日）：

我上面的（旧）答案可以大大改进......
参考 Hormann & Agathos 的“任意多边形的多边形问题点”
http://citeseerx.ist.psu.edu/viewdoc /download?doi=10.1.1.88.5498&rep=rep1&type=pdf

struct Point { int X; int Y; };
typedef std::vector< Point > Path;

int PointInPolygon(const Point &pt, const Path &path)
{
  //returns 0 if false, +1 if true, -1 if pt ON polygon boundary
  int result = 0;
  size_t cnt = path.size();
  if (cnt < 3) return 0;
  Point ip = path[0];
  for(size_t i = 1; i <= cnt; ++i)
  {
    Point ipNext = (i == cnt ? path[0] : path[i]);
    if (ipNext.Y == pt.Y)
    {
        if ((ipNext.X == pt.X) || (ip.Y == pt.Y && 
          ((ipNext.X > pt.X) == (ip.X < pt.X)))) return -1;
    }
    if ((ip.Y < pt.Y) != (ipNext.Y < pt.Y))
    {
      if (ip.X >= pt.X)
      {
        if (ipNext.X > pt.X) result = 1 - result;
        else
        {
          int d = (ip.X - pt.X) * (ipNext.Y - pt.Y) - 
            (ipNext.X - pt.X) * (ip.Y - pt.Y);
          if (!d) return -1;
          if ((d > 0) == (ipNext.Y > ip.Y)) result = 1 - result;
        }
      } else
      {
        if (ipNext.X > pt.X)
        {
          int d = (ip.X - pt.X) * (ipNext.Y - pt.Y) - 
            (ipNext.X - pt.X) * (ip.Y - pt.Y);
          if (!d) return -1;
          if ((d > 0) == (ipNext.Y > ip.Y)) result = 1 - result;
        }
      }
    }
    ip = ipNext;
  } 
  return result;
}
于 2013-05-07T16:42:34.203 回答