check if a point is in a polygon which is partially open

Question

I would like to see if a point is in a polygon or not. Of course I googled and looked if this question was answered earlier and then found this algorithm: http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html This works fine unless the polygon is partially open. E.g.:

A-E are detected as they should, but the open part of the B-polygon is also considered to be closed! If you run this example code you'll see what I mean:

#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;
}

The x2/y2 polygon consists of a an closed block connected to a partially open block. The pnpoly function still considers a point "in" the open block to be in a polygon.

My question now is: how can I solve this problem? Or am I overlooking something?

Thanks in advance.

Answer 1

Maybe it is a late reply, but I would like to contribute, anyway.

You need to make a pre-processing in your polygon array data, because such algorithm treats the last point to be connected to the first point. As you can see in the description of this algorithm in particular, it treats polygons, and as the open region is not a polygon, it cannot be treated by this algorithm.

I would suggest you make some pre-processing in your polygons using the following idea:

"For every set of points that could represent a polygon, it must be splitted into sub-polygons whenever you find the starting point being repeated. When you find it, save this polygon, and, starting at this point, create a new one and continue your processing, until you reach the end of your set. Thus, every sub-polygon that does not end with the starting point, should be ignored in your treatment and hence not submitted to the algorithm. By using this pre-processing approach, you will only submit to the algorithm those sub-polygons whose ending point is the same as the starting point."

May it helps you - if you still needs it...