Welcome to the Lounge

k5054 wrote:

At my hourly rate, I've probably spent more than that wingeing about it here ...

honey the codewitch wrote:

but the code is a zoo

honey the codewitch wrote:

Thank you so much for your comment.

// wn_PnPoly(): winding 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:  wn = the winding number (=0 only when P is outside)
int
wn_PnPoly( Point P, Point* V, int n )
{
    int    wn = 0;    // the  winding 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 <= P.y) {          // start y <= P.y
            if (V[i+1].y  > P.y)      // an upward crossing
                 if (isLeft( V[i], V[i+1], P) > 0)  // P left of  edge
                     ++wn;            // have  a valid up intersect
        }
        else {                        // start y > P.y (no test needed)
            if (V[i+1].y  <= P.y)     // a downward crossing
                 if (isLeft( V[i], V[i+1], P) < 0)  // P right of  edge
                     --wn;            // have  a valid down intersect
        }
    }
    return wn;
}

Quote:

There is a significant speed-up (known since 2001) of the winding number algorithm. It uses signed crossings, based on whether each crossing is left-to-right or right-to-left. Details and C++ code are given at the link in the following annotation .[6] Angles are not used, and no trigonometry is involved. The code is as fast as the simple boundary crossing algorithm. Further, it gives the correct answer for nonsimple polygons, whereas the boundary crossing algorithm fails in this case.

static bool IsInsidePolygon2(Point P, Point[] V)
{
    int i, j;
    bool c = false;
    for(i=0,j=V.Length-1;i<V.Length; j=i++)
    {
        Point pti = V[i];
        Point ptj = V[j];
        if (((pti.Y > P.Y) != (ptj.Y > P.Y)) &&
         (P.X < (ptj.X - pti.X) * (P.Y - pti.Y) / (ptj.Y - pti.Y) + pti.X))
            c = !c;
    }
    return c;
}