4

我想看看一个点是否在多边形中。当然，我用谷歌搜索并查看了这个问题是否早先得到了回答，然后找到了这个算法： http: //www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html 这工作正常，除非多边形部分打开. 例如： 例子

AE 被检测到，但 B 多边形的开放部分也被认为是封闭的！如果你运行这个示例代码，你会明白我的意思：

#include <stdio.h>

int pnpoly(int nvert, float *vertx, float *verty, float testx, float testy)
{
  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;
}

int main(int argc, char *argv[])
{
        // 1 closed [A]
        float x1[] = { 0, 1, 1, 0, 0 };
        float y1[] = { 0, 0, 1, 1, 0 };
        printf("1: %d (1 expected)\n", pnpoly(5, x1, y1, 0.8, 0.8));
        printf("1: %d (0 expected)\n", pnpoly(5, x1, y1, -0.8, -0.8));

        // 1 closed [B] with a partial open
        // please note that the vertex between [0,-1] and [0,0] is missing
        float x2[] = { 0, 1, 1, 0, 0, -1, -1, 0 };
        float y2[] = { 0, 0, 1, 1, 0,  0, -1, -1 };
        printf("2: %d (1 expected)\n", pnpoly(8, x2, y2, 0.8, 0.8));
        printf("2: %d (0 expected)\n", pnpoly(8, x2, y2, -0.8, -0.8)); // <- fails

        // 2 closed [C/D/E]
        float x3[] = { 0, 1, 1, 0, 0, -1, -1, 0, 0 };
        float y3[] = { 0, 0, 1, 1, 0,  0, -1, -1, 0 };
        printf("3: %d (1 expected)\n", pnpoly(9, x3, y3, 0.8, 0.8));
        printf("3: %d (1 expected)\n", pnpoly(9, x3, y3, -0.8, -0.8));

        return 0;
}

x2/y2 多边形由一个连接到部分开放块的封闭块组成。pnpoly 函数仍然认为开放块“中”的点位于多边形中。

我现在的问题是：我该如何解决这个问题？还是我忽略了什么？

提前致谢。

4

1 回答 1

1

也许这是一个迟到的答复，但无论如何我想贡献。

您需要对多边形数组数据进行预处理，因为这种算法会将最后一个点连接到第一个点。正如您在该算法的描述中特别看到的那样，它处理多边形，并且由于开放区域不是多边形，因此该算法不能处理它。

我建议您使用以下想法对多边形进行一些预处理：

“对于可以表示多边形的每一组点，只要找到重复的起点，就必须将其拆分为子多边形。找到它后，保存该多边形，并从该点开始创建一个新多边形，然后继续你的处理，直到你到达你的集合的末尾。因此，在你的处理中应该忽略每个不以起点结束的子多边形，因此不提交给算法。通过使用这种预处理方法，你只会将那些终点与起点相同的子多边形提交给算法。”

愿它对您有所帮助-如果您仍然需要它...

于 2014-06-27T00:37:43.123 回答