在javascript中实现kd树实现？

Question

我想在模拟中做一堆距离查询,并且不想循环遍历所有点.(事实证明,N**2不能很好地扩展).

是否有一个坚实的kd树(或其他球树,我猜)在javascript中实现任何人都可以推荐？

Answer 1

这是另一个可能证明有用的非常好的实现(免责声明 - 我是作者):

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

Answer 2

这是我写的一个库:

• 静态kdtree

在Chrome中,它比Ubilabs的kdtree快几个数量级,并支持更大的查询集(正交范围查询和边界球).以下是最新版Google Chrome的基准测试结果链接.

• Chrome 34基准测试结果

它使用CommonJS/npm,但与browserify配合得很好.