Recently we needed a point-in-polygon algorithm in JavaScript for finderful.com. There are many implementations out there, and there are more efficient ways of doing it, but we find the ray-casting method to be the simplest.

We recently submitted our JavaScript implementation to Rosetta Code, and you can find a commented version below:

/** * @return {boolean} true if (lng, lat) is in bounds */ function contains(bounds, lat, lng) { //https://rosettacode.org/wiki/Ray-casting_algorithm var count = 0; // iterate over the segments of the polygon and count how many times the point is west of the segment for (var b = 0; b < bounds.length; b++) { var vertex1 = bounds[b]; var vertex2 = bounds[(b + 1) % bounds.length]; if (west(vertex1, vertex2, lng, lat)) ++count; } // if it is west of an even number of segments, then point is outside the polygon return count % 2; /** * @return {boolean} true if (x,y) is west of the line segment connecting A and B */ function west(A, B, x, y) { // make it so segment point A is not above segment point B if (A.y <= B.y) { // if the point is outside the y-range containing the segment then the point is definitely not west of the segment // or if the point is east of the x-range containing the segment then the point is definitely not west of the segment if (y <= A.y || y > B.y || x >= A.x && x >= B.x) { return false; } else // if the point is west of the rectangle containing the segment then the point is definitely west of the segment if (x < A.x && x < B.x) { return true; } else // compare the slope of the line segment from A to the point and the slope of the segment from A to B // the first slope is higher if-and-only-if the point is west of the A-B segment { return (y - A.y) / (x - A.x) > (B.y - A.y) / (B.x - A.x); } } else { return west(B, A, x, y); } } }

Advertisements