mourner / geokdbush

The fastest spatial index for geographic locations in JavaScript

Hi! I'm Volodymyr Agafonkin.

I'm a software engineer. I created Leaflet, the number one library for interactive web maps, and maintain 40+ other open source projects with a focus on algorithms, computational geometry and data visualization. I'm building the future of maps at Mapbox. Here are a few of my best tech articles: https://agafonkin.com

I'm a musician. I write songs, play guitar and sing in Obiymy Doschu. If you like beautiful, evocative rock music with lush string arrangements, check out our last album.

I'm a father to beautiful 9-year-old twin girls, I'm happily married and live in Kyiv, Ukraine. I love baking, photography, strength training, martial arts, reading sci-fi and fantasy, and exploring quiet parks. You can find tidbits of my life on X (Twitter), Instagram and Facebook.

geokdbush's Issues

Added Typescript definition to DefinitelyTyped

Just a heads up, I've submitted a PR to add the Typescript definition to geokdbush.

Once it's merged and published, we can add @types/geokdbush to this README.

DefinitelyTyped/DefinitelyTyped#17367

Better lower bound

The current lower bound of great circle distance from a point to any point inside a bounding box is quickly hacked together and pretty poor. I found this algorithm for computing a proper lower bound, although it's a bit complicated:

Will try to implement and see how it goes.

Getting distances in result set

Hi Vladimir

Do you think there is a chance to get distance with a result somehow?

IL

Fix example: kdbush(...) → new kdbush(...)

The code from example doesn't work for me, but when I add the new operator to kdbush, it starts working:

var index = kdbush(points, (p) => p.lon, (p) => p.lat);

should become

var index = new kdbush(points, (p) => p.lon, (p) => p.lat);

geokdbush fails where kdbush.within succeedes

We use kdbush index and used kdbush.within for a lot of time. Recently we started to use geokdbush and it sometimes failed to find the NN on some locations (especially the ones that were really very close). We have used 50.000 set with lat,lons and I was unable to replicate where it failed, but was unable to trace the error inside the lib (since chrome dev tools killed my CPU when trying to investigate content of index).

I am sure kdbush index was correct and contained all the points since kdbush worked fine.

We switched back to kdbush.within and all is ok now.

If you find it useful I can send you the data set for investigation and piece of code but I consider kdbush.within to be much faster.

CommonJS and kdbush

Hi @mourner,

First of all, thank you so much for your work on this project. I've tried several libraries, and this is by far the fastest nearby geo library I've used in a few non-commercial projects.

Unfortunately, it's not working anymore due to the lack of CommonJS support in kdbush. I've integrated geokdbush into my web application, which I cannot easily migrate to ESM. It would be different if it was a simple standalone script running on the backend.

If possible, would it be feasible to reintroduce CommonJS support to kdbush and update this library to reflect v4.* of kdbush? That would be greatly appreciated.

Thanks!

Range method that handles date line wrapping

KDBush already has a range method, but geokdbush should have a wrapper around it that handles the date line wrapping.

compatibility with kdbush 4.x

kdbush 4.x changed the internal interface so that index.points no longer exists, but the latest version of geokdbush still relies on it.

I was able to work around it by manually setting index.points to an array matching what I wanted (lng/lat points).

It might make sense to just return an index.