Check if the point is in a polygon that is partially open

Question

I would like to see if the point is in the polygon or not. Of course, I googled and looked if this question had an answer before, and then found this algorithm: http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html This works fine if the polygon is partially is open. For instance.:

AEs are detected as they should, but the open part of the B-polygon is also considered closed! If you run this sample code, you will 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 polygon x2 / y2 consists of a closed block connected to a partially open block. The pnpoly function still thinks that the point "in" the open block is in the polygon.

Now my question is: how can I solve this problem? Or am I not noticing something?

Thanks in advance.

Answer 1

This may be a late answer, but I would like to contribute anyway.

You need to pre-process the data of the polygon array, because such an algorithm processes the last point, which should be associated with the first point. As you can see in the description of this algorithm, in particular, it processes polygons, and since the open area is not a polygon, it cannot be considered using this algorithm.

I suggest you do some pre-processing in your landfills using the following idea:

“For each set of points that can be a polygon, it should be divided into sub-polygons whenever you think that the starting point is repeated. When you find it, save this polygon and, starting from this point, create a new one and continue processing until you reach the end of your set.Thus, each subpolygon that does not end at the starting point should be ignored in its treatment and, therefore, not presented to the algorithm. second processing, you will only obey the algorithm subpoligonam, the end point of which coincides with the starting point. "

May this help you - if you still need to ...