check if point is in polygon algorithm javascript test

check if point is in polygon algorithm javascript test

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s