检查一个点是否在一个部分开放的多边形内

Question

我想查看一个点是否在多边形内，当然我已经过谷歌搜索并查看之前是否有人回答这个问题，并找到了这个算法：http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html。 这个算法很好用，除非多边形是部分开放的。例如： A-E被检测到了，但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函数仍然认为在开放块内的点在多边形内。

我的问题是：我该如何解决这个问题？或者我有所忽略吗？

提前感谢。

- Folkert van Heusden

Answer 1

也许我的回复有些晚，但我仍然想贡献我的力量。

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

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

“对于每组可能表示多边形的点集，当您发现起始点重复时，必须将其拆分为子多边形。当您找到它时，请保存此多边形，并从此点开始创建新的多边形并继续处理，直到达到集合的末尾。因此，在您的处理中，应忽略每个不以起始点结尾的子多边形，因此不会将其提交给算法。通过使用此预处理方法，您将只向算法提交那些以起始点结尾的子多边形。”

希望这能帮助您-如果您仍然需要的话...

- Erick Sperandio