Control point inside the polygon

Question

int pnpoly(int npol, float *xp, float *yp, float x, float y) { int i, j, c = 0; for (i = 0, j = npol-1; i < npol; j = i++) { if ((((yp[i] <= y) && (y < yp[j])) || ((yp[j] <= y) && (y < yp[i]))) && (x < (xp[j] - xp[i]) * (y - yp[i]) / (yp[j] - yp[i]) + xp[i])) c = !c; } return c; } 

This function checks if the point is inside the polygon. How do I feel about a polygon coordinate that is negative? For instance,

 float x[3] = { 0.16, 1.2, -10 }; float y[3] = { 1.8, 10, -5.5 }; 

I tried to check the valid point inside the polygon and it returns 0.

Answer 1

There are pretty good implementations from iSurfer

The two methods used in most cases (and the two that I know) are the number of intersections and the number of windings . Both of them are not affected by the polygon / point coordinate signs . So this should be a mistake in your code.

For completeness, I put the code for the test with the intersecting number , which seems to be what you are trying to do in your code

 // a Point is defined by its coordinates {int x, y;} // isLeft(): tests if a point is Left|On|Right of an infinite line. // Input: three points P0, P1, and P2 // Return: >0 for P2 left of the line through P0 and P1 // =0 for P2 on the line // <0 for P2 right of the line // See: Algorithm 1 "Area of Triangles and Polygons" inline int isLeft( Point P0, Point P1, Point P2 ) { return ( (P1.x - P0.x) * (P2.y - P0.y) - (P2.x - P0.x) * (P1.y - P0.y) ); } //=================================================================== // cn_PnPoly(): crossing number test for a point in a polygon // Input: P = a point, // V[] = vertex points of a polygon V[n+1] with V[n]=V[0] // Return: 0 = outside, 1 = inside // This code is patterned after [Franklin, 2000] int cn_PnPoly( Point P, Point* V, int n ) { int cn = 0; // the crossing number counter // loop through all edges of the polygon for (int i=0; i<n; i++) { // edge from V[i] to V[i+1] if (((V[i].y <= Py) && (V[i+1].y > Py)) // an upward crossing || ((V[i].y > Py) && (V[i+1].y <= Py))) { // a downward crossing // compute the actual edge-ray intersect x-coordinate float vt = (float)(Py - V[i].y) / (V[i+1].y - V[i].y); if (Px < V[i].x + vt * (V[i+1].x - V[i].x)) // Px < intersect ++cn; // a valid crossing of y=Py right of Px } } return (cn&1); // 0 if even (out), and 1 if odd (in) } //=================================================================== 

A special case that may occur when checking the intersection number is when the ray overlaps the edge of the polygon. In this case, it becomes somewhat fuzzy how to count intersections. That is why this is not the actual number of intersections that we count, but the number that we crossed on the half-planes defined by the ray.

Checking the number of windings is more reliable in this regard.