Solid k-d tree implementation in javascript? [clos

问题:

I'm looking to do a bunch of distance queries in a simulation, and would prefer not to loop over all the points. (N**2 doesn't scale that well, it turns out).

Is there a solid k-d tree (or other ball tree, I suppose) implementation in javascript that anyone can recommend?

回答1:

Here is another pretty good implementation that might prove useful (disclaimer - I am the author):

https://github.com/ubilabs/kd-tree-javascript

回答2:

Here is a library that I wrote:

• static-kdtree

In Chrome, it is up to several orders of magnitude faster than Ubilabs' kdtree and supports a larger set of queries (orthogonal range query and bounding sphere). Here is a link to the benchmark results for the latest version of Google Chrome.

• Chrome 34 benchmark results

It uses CommonJS/npm, but works great with browserify.

回答3:

Late answer but this is a good one https://github.com/dbotha/Javascript-k-d-tree (disclaimer - I know the author)

回答4:

This R-Tree implementation looks pretty good.

回答5:

RBush is another javascript R-Tree implementation.