pelias / polygon-lookup

Fast point-in-polygon intersection for large numbers of polygons.
72 stars 17 forks source link

polygon-lookup

Greenkeeper badge

NPM

A data-structure for performing fast, accurate point-in-polygon intersections against (potentially very large) sets of polygons. PolygonLookup builds an R-tree, or bounding-box spatial index, for its polygons and uses it to quickly narrow down the set of candidate polygons for any given point. If there are any ambiguities, it'll perform point-in-polygon intersections to identify the one that really intersects. PolygonLookup operates entirely in memory, and works best for polygons with little overlap.

API

PolygonLookup(featureCollection)
PolygonLookup.search(x, y, limit)

Narrows down the candidate polygons by bounding-box, and then performs point-in-polygon intersections to identify the first n container polygon (with n = limit, even if more polygons really do intersect).

PolygonLookup.loadFeatureCollection(featureCollection)

Stores a feature collection in this PolygonLookup, and builds a spatial index for it. The polygons and rtree can be accessed via the .polygons and .rtree properties.

example usage

var PolygonLookup = require( 'polygon-lookup' );
var featureCollection = {
    type: 'FeatureCollection',
    features: [{
        type: 'Feature',
        properties: { id: 'bar' },
        geometry: {
            type: 'Polygon',
            coordinates: [ [ [ 0, 1 ], [ 2, 1 ], [ 3, 4 ], [ 1, 5 ] ] ]
        }
    }]
};
var lookup = new PolygonLookup( featureCollection );
var poly = lookup.search( 1, 2 );
console.log( poly.properties.id ); // bar