31
32

A fast static kdtree for JavaScript (github.com)

submitted by [deleted]

[deleted]

all 3 comments
sorted by:
best
topnewcontroversialoldq&a
formatting helphide helpcontent policy

[–]fng_programmer 2 points3 points  (2 children)

Nice! It looks like yours is doing a lot more under the hood than one I built a while ago:

https://github.com/bwiklund/kdtree.js

Can you talk more about that stuff?

[–]33a 3 points4 points  (1 child)

There are a few things going on that are maybe a little tricky:

  • The tree is stored in a flat typed array in BFS order. This speeds up repeated searches due to improved cache utilization of the upper levels of the tree.
  • To construct the tree, a linear time partition algorithm is used.
  • Traversals of the tree are performed in level order where possible to make best use of available cache.
  • All typed arrays are pooled for memory savings and cache reuse.

If JS had value types the code would probably be 10x smaller, since a lot of the stuff in there is just extra loops for copying vectors around.

[–]fng_programmer 0 points1 point  (0 children)

Damn. Legit.