116 lines
3.8 KiB
JavaScript
Executable File
116 lines
3.8 KiB
JavaScript
Executable File
import { getCoord, getGeom } from "@turf/invariant";
|
|
// http://en.wikipedia.org/wiki/Even%E2%80%93odd_rule
|
|
// modified from: https://github.com/substack/point-in-polygon/blob/master/index.js
|
|
// which was modified from http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html
|
|
/**
|
|
* Takes a {@link Point} and a {@link Polygon} or {@link MultiPolygon} and determines if the point
|
|
* resides inside the polygon. The polygon can be convex or concave. The function accounts for holes.
|
|
*
|
|
* @name booleanPointInPolygon
|
|
* @param {Coord} point input point
|
|
* @param {Feature<Polygon|MultiPolygon>} polygon input polygon or multipolygon
|
|
* @param {Object} [options={}] Optional parameters
|
|
* @param {boolean} [options.ignoreBoundary=false] True if polygon boundary should be ignored when determining if
|
|
* the point is inside the polygon otherwise false.
|
|
* @returns {boolean} `true` if the Point is inside the Polygon; `false` if the Point is not inside the Polygon
|
|
* @example
|
|
* var pt = turf.point([-77, 44]);
|
|
* var poly = turf.polygon([[
|
|
* [-81, 41],
|
|
* [-81, 47],
|
|
* [-72, 47],
|
|
* [-72, 41],
|
|
* [-81, 41]
|
|
* ]]);
|
|
*
|
|
* turf.booleanPointInPolygon(pt, poly);
|
|
* //= true
|
|
*/
|
|
export default function booleanPointInPolygon(point, polygon, options) {
|
|
if (options === void 0) { options = {}; }
|
|
// validation
|
|
if (!point) {
|
|
throw new Error("point is required");
|
|
}
|
|
if (!polygon) {
|
|
throw new Error("polygon is required");
|
|
}
|
|
var pt = getCoord(point);
|
|
var geom = getGeom(polygon);
|
|
var type = geom.type;
|
|
var bbox = polygon.bbox;
|
|
var polys = geom.coordinates;
|
|
// Quick elimination if point is not inside bbox
|
|
if (bbox && inBBox(pt, bbox) === false) {
|
|
return false;
|
|
}
|
|
// normalize to multipolygon
|
|
if (type === "Polygon") {
|
|
polys = [polys];
|
|
}
|
|
var insidePoly = false;
|
|
for (var i = 0; i < polys.length && !insidePoly; i++) {
|
|
// check if it is in the outer ring first
|
|
if (inRing(pt, polys[i][0], options.ignoreBoundary)) {
|
|
var inHole = false;
|
|
var k = 1;
|
|
// check for the point in any of the holes
|
|
while (k < polys[i].length && !inHole) {
|
|
if (inRing(pt, polys[i][k], !options.ignoreBoundary)) {
|
|
inHole = true;
|
|
}
|
|
k++;
|
|
}
|
|
if (!inHole) {
|
|
insidePoly = true;
|
|
}
|
|
}
|
|
}
|
|
return insidePoly;
|
|
}
|
|
/**
|
|
* inRing
|
|
*
|
|
* @private
|
|
* @param {Array<number>} pt [x,y]
|
|
* @param {Array<Array<number>>} ring [[x,y], [x,y],..]
|
|
* @param {boolean} ignoreBoundary ignoreBoundary
|
|
* @returns {boolean} inRing
|
|
*/
|
|
function inRing(pt, ring, ignoreBoundary) {
|
|
var isInside = false;
|
|
if (ring[0][0] === ring[ring.length - 1][0] &&
|
|
ring[0][1] === ring[ring.length - 1][1]) {
|
|
ring = ring.slice(0, ring.length - 1);
|
|
}
|
|
for (var i = 0, j = ring.length - 1; i < ring.length; j = i++) {
|
|
var xi = ring[i][0];
|
|
var yi = ring[i][1];
|
|
var xj = ring[j][0];
|
|
var yj = ring[j][1];
|
|
var onBoundary = pt[1] * (xi - xj) + yi * (xj - pt[0]) + yj * (pt[0] - xi) === 0 &&
|
|
(xi - pt[0]) * (xj - pt[0]) <= 0 &&
|
|
(yi - pt[1]) * (yj - pt[1]) <= 0;
|
|
if (onBoundary) {
|
|
return !ignoreBoundary;
|
|
}
|
|
var intersect = yi > pt[1] !== yj > pt[1] &&
|
|
pt[0] < ((xj - xi) * (pt[1] - yi)) / (yj - yi) + xi;
|
|
if (intersect) {
|
|
isInside = !isInside;
|
|
}
|
|
}
|
|
return isInside;
|
|
}
|
|
/**
|
|
* inBBox
|
|
*
|
|
* @private
|
|
* @param {Position} pt point [x,y]
|
|
* @param {BBox} bbox BBox [west, south, east, north]
|
|
* @returns {boolean} true/false if point is inside BBox
|
|
*/
|
|
function inBBox(pt, bbox) {
|
|
return (bbox[0] <= pt[0] && bbox[1] <= pt[1] && bbox[2] >= pt[0] && bbox[3] >= pt[1]);
|
|
}
|