elevated spatial thinking

Fast geometry in geometry lookup for large GeoJSONs

github.com/simonepri/geojson-geometries-lookup

This package actually uses turfJS’s booleanContains to check if a geometry is contained into another.

What the package does is to pre-process the GeoJSON creating a lookup table for each kind of geometry using an R-Tree. Then it uses each R-Tree to fastly choose appropriate candidates to be checked with turfJS.

What’s the benefit of the pre-processing?? Assume that you have a GeoJSON with N nonoverlapping geometries and you want to search M different geometries in this GeoJSON.

Using just turfJS you have to iterate on all M geometries and apply booleanContains on the whole GeoJSON ending-up with a complexity of O(M * N)

Using the package I wrote, basically, you reduce the complexity of the search to O(M * log2(N)) but you have to pay O(N * log2(N) the first time to build the R-Tree.

This means that if you have to find one single element booleanContains performs better, while if you have to do multiple queries on the same GeoJSON then this package performs logarithmically better.