point-in-polygon-extended

Update: 6/7/15: As seen by the build status it seems neither the winding number nor ray casting point-in-polygon algorithms pass the point on polygon border test, so at this time I can't remember this library. Instead, maybe look at robust-point-in-polygon

Determine if a point is inside of a polygon.

This is a fork of James Halliday's point-in-polygon and includes alternative algorithms beyond ray casting because the original library does not include points on boundaries (see issue2). Another library called robust-point-in-polygon solves this problem but still has some difficulty for complex polygons with regards to performance and accuracy.

Point-in-polygon-extended allows a user to switch between the aforementioned algorithms or other ones, such as the winding number test. This library also includes a testing suite to compare the different algorithms for different test cases.

example

var pointInPoly = require('point-in-polygon-extended');
var pointInPolyRaycast = pointInPoly.pointInPolyRaycast;
var pointInPolyWindingNumber = pointInPoly.pointInPolyWindingNumber;

var polygon = [ [ 1, 1 ], [ 1, 2 ], [ 2, 2 ], [ 2, 1 ] ];

console.dir([
    pointInPolyRaycast([ 1.5, 1.5 ], polygon),
    pointInPolyRaycast([ 4.9, 1.2 ], polygon),
    pointInPolyRaycast([ 1.8, 1.1 ], polygon)
]);
// output: [ true, false, true ]

console.dir([
    pointInPolyWindingNumber([ 1.5, 1.5 ], polygon),
    pointInPolyWindingNumber([ 4.9, 1.2 ], polygon),
    pointInPolyWindingNumber([ 1.8, 1.1 ], polygon)
]);
// output: [ true, false, true ]

methods

Ray-casting

/**
 * Returns whether a point is in a polygon using ray casting. This still returns
 * false if a point is on the boundary.
 *
 * Based on Point Inclusion in Polygon Test (PNPOLY) by W. Randolph Franklin:
 * http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html
 *
 * @param point {Array} should be a 2-item array of coordinates
 * @param polygon {Array} should be an array of 2-item arrays of coordinates.
 * @returns {boolean} true if point is inside or false if not
 */
function pointInPolyRaycast(point, polygon)

Winding number

/**
 * Returns whether a point is in a polygon using a winding number test
 *
 * Algorithm by Dan Sunday: http://geomalgorithms.com/a03-_inclusion.html
 *
 * @param point {Array} should be a 2-item array of coordinates
 * @param polygon {Array} should be an array of 2-item arrays of coordinates.
 * @return {boolean} true if inside, false if outside
 */
 function pointInPolyWindingNumber(point, polygon)

install

npm install point-in-polygon-extended

credit

Thank you to the following people and projects:

James Halliday / substack for his point-in-polygon
Mikola Lysenko for his robust-point-in-polygon
Brendan Kenny for his libtess.js. I borrowed a lot of his testing layout (gulp, travis, coveralls, mocha, etc)
Dan Sunday for his winding number algorithm
W. Randolph Franklin for his ray casting algorithm

other options / research

tips + tricks

Debugging

If you have Webstorm or IntelliJ, set a breakpoint and create a Mocha run configuration with a TDD user interface.

Alternatively, you can run from the root directory

mocha --ui tdd

Gulp tasks

To build, run mocha tests, and measure code coverage

gulp build
gulp test
gulp coverage

bradparks / point-in-polygon-extended Goto Github PK