JavaScript implementation of winding number algorithm to determine whether a point is inside a polygon

point_in_polygon_using_winding_number.js

//JavaScript implementation of winding number algorithm to determine whether a point is inside a polygon
//Based on C++ implementation of wn_PnPoly() published on http://geomalgorithms.com/a03-_inclusion.html

function pointInPolygon(point, vs) {
  const x = point[0], y = point[1];
  let wn = 0;

  for (let i = 0, j = vs.length - 1; i < vs.length; j = i++) {
    let xi = vs[i][0], yi = vs[i][1];
    let xj = vs[j][0], yj = vs[j][1];

    if (yj <= y) {
      if (yi > y) {
        if (isLeft([xj, yj], [xi, yi], [x,y]) > 0) {
          wn++;
        }
      }
    } else {
      if (yi <= y) {
        if (isLeft([xj, yj], [xi, yi], [x, y]) < 0) {
          wn--;
        }
      }
    }
  }
  return wn != 0;
};

function isLeft(P0, P1, P2) {
  let res = ( (P1[0] - P0[0]) * (P2[1] - P0[1])
            - (P2[0] -  P0[0]) * (P1[1] - P0[1]) );
  return res;
}

You are awesome :)

You are awesome! I needed this magic :)

@SebaMederos

point is an array of size 2 containing the x and y co-ordinates of the point you want to test, i.e. point[0] is x and point[1] is y.

vs is an array containing the vertices of the polygon, each element is an array of size 2 containing the vertex's x and y co-ordinates.

Take this example in which we want to test if two points pointA and pointB are contained inside the square mySquare which is centred around 0,0 and has a side length of two.

mySquare = [[-1,1], [1,1], [1,-1], [-1,-1]];

pointA = [0.5,0.5];
pointB = [2,2];

pointInPolygon(pointA, mySquare) will return true;
pointInPolygon(pointB, mySquare) will return false;

A bit more terse and using TypeScript, assume Point is a type with x and y number properties...

function cross(x: Point, y: Point, z: Point): number {
  return (y.x - x.x) * (z.y - x.y) - (z.x - x.x) * (y.y - x.y);
}

function pointInPolygon(p: Point, points: Array<Point>): boolean {
  let wn = 0; // winding number

  points.forEach((a, i) => {
    const b = points[(i+1) % points.length];
    if (a.y <= p.y) {
      if (b.y > p.y && cross(a, b, p) > 0) {
        wn += 1;
      }
    } else if (b.y <= p.y && cross(a, b, p) < 0) {
      wn -= 1;
    }
  });

  return wn !== 0;
}

Thanks @gmac! Works perfectly :)