Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
JavaScript implementation of winding number algorithm to determine whether a point is inside a polygon
//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) {
var x = parseFloat(point[0]), y = parseFloat(point[1]);
var wn = 0;
for (var i = 0, j = vs.length - 1; i < vs.length; j = i++) {
var xi = parseFloat(vs[i][0]), yi = parseFloat(vs[i][1]);
var xj = parseFloat(vs[j][0]), yj = parseFloat(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)
{
var res = ( (P1[0] - P0[0]) * (P2[1] - P0[1])
- (P2[0] - P0[0]) * (P1[1] - P0[1]) );
return res;
}
@shakedlokits

This comment has been minimized.

Copy link

@shakedlokits shakedlokits commented Apr 18, 2019

You are awesome :)

@SebaMederos

This comment has been minimized.

Copy link

@SebaMederos SebaMederos commented Sep 7, 2020

Can you tell me how to use it please!?

@thejambi

This comment has been minimized.

Copy link

@thejambi thejambi commented Oct 25, 2020

You are awesome! I needed this magic :)

@vlasky

This comment has been minimized.

Copy link
Owner Author

@vlasky vlasky commented Dec 9, 2020

@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;

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment