Find in which polygon a GeoJSON point lies in, in NodeJS

Question

Given a defined (lat, lon) geo-point I'm trying to find in which polygon this point lies in. I suppose iterating over all the polygons is not efficient. Is there available any function or library for NodeJS that does this?

const polygon = getPolygonFromPoint(FeatureCollection, x, y);

There are no overlapping polygons, actually I'm using this to detect in which district of a certain country a defined GPS coordinates point lies in.

Some details are missing... For example, If you have overlapping polygons, a point may belong to more than one polygon — Michael Rovinsky
– Michael Rovinsky, Commented Apr 24, 2021 at 7:34
@MichaelRovinsky thanks for the note, I updated my answer accordingly. There are no overlapping polygons. — João Pimentel Ferreira
– João Pimentel Ferreira, Commented Apr 24, 2021 at 9:01
Do you need to do it for more than one point e.g. a lot of points? — Robin Mackenzie
– Robin Mackenzie, Commented Apr 24, 2021 at 9:56

Robin Mackenzie · Accepted Answer · 2021-04-24 10:47:39Z

4

For a simple point in polygon test you can check turf which has a booleanPointInPolygon. Turf works in node but you should check for differences between v5 and v6+ around how to use npm accordingly. Points should be long/ lat (not lat/ long) and the polygon can be easily pulled out of the feature geometry of your feature collection.

For a more complex use case where you have many points and many polygons within which to locate them you should consider using rbush.

Note that the rbush library constructs an r-tree out of the bounding boxes of the polygons and not the polygons themselves, so use of an r-tree is just a way to vastly reduce the number of polygons you need to test with booleanPointInPolygon.

Example code for rbush:

const RBush = require("rbush");
const turfBbox = require("@turf/bbox").default;

const geo = {} // your feature collection...
const maxEntriesPerNode = 50; // check the doco
const tree = new RBush(maxEntriesPerNode);
const bbox2Object = (keys, bbox) => ["minX", "minY", "maxX", "maxY"].reduce((o, k, i) => ({...o, [k]: bbox[i]}), {})

// create rtree from feature collection
geo.features.forEach(feature => {
  const leaf = bbox2Object(bboxKeys, turfBbox(feature)); // use bbox of feature
  leaf["id"] = feature.properties.SOME_ID; // add some custom properties
  tree.insert(leaf);
});

// test a random point from your data
const [x, y] = [123, 456]; // should be long, lat
const test = tree.search({minX: x, minY: y, maxX: x, maxY: y});
// test should have an array of leaves per the tree.insert above

You can then perform the booleanPointInPolygon test on this reduced set of polygons.

answered Apr 24, 2021 at 10:47

Robin Mackenzie

19.4k7 gold badges42 silver badges63 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Andrew Reid Over a year ago

Just a note: these approaches consider coordinates in Cartesian space, while D3 considers lat long pairs to be 3 dimensional points on a sphere - as a consequence D3 uses great circles to connect vertices of a polygon, which means that a point that is geographically within a polygon might be missed by the above methods, but drawn inside the polygon by D3. D3 does contain the method d3.geoContains which avoids this and any issues with antimeridians, though for the majority of cases, treating coordinates as Cartesian will result in accurate results.

Robin Mackenzie Over a year ago

Thanks @AndrewReid, agree this is an important point, and assume you mean the turf function ? Or is this referring to rbush as well ?

Andrew Reid Over a year ago

Both turf and rbush work in Cartesian coordinate space rather than a geographic coordinate space, both should return the same result, which may be geographically incorrect. The likelihood of incorrect results will be dependent on the length of polygon segments, the span of longitude crossed, and the distance from the poles. D3's geographic functions are relatively unique in using spherical math including for path rendering.

João Pimentel Ferreira · Accepted Answer · 2021-04-24 10:42:37Z

2

I implemented that with the library polygon-lookup

const PolygonLookup = require('polygon-lookup')
const 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

answered Apr 24, 2021 at 10:42

João Pimentel Ferreira

16.5k13 gold badges98 silver badges131 bronze badges

1 Comment

citykid Over a year ago

i think this is the pragmatic solution to use. theoretically the problem is treated under the name "point location". en.wikipedia.org/wiki/Point_location The slab decomposition approach is the origin of persistent data structures (tarjan et al). slab decomposition is log(n) - full polygons test included while the rtree appraoch is log(n) for bounding boxes + k * point in polygon test. it assumes non overlapping. interesting topic ;)

Collectives™ on Stack Overflow

Find in which polygon a GeoJSON point lies in, in NodeJS

2 Answers 2

3 Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related