Я ищу, чтобы сделать кучу дистанционных запросов в симуляции, и предпочел бы не перебирать все точки. (N ** 2 не масштабируется так хорошо, оказывается).Реализация твердого k-d дерева в javascript?
Есть ли твердое k-d tree (или другое шариковое дерево, я полагаю) в javascript, который любой может порекомендовать?
Вот еще довольно хорошая реализация, которая может оказаться полезной (отказ от ответственности - Я автор):
This R-Tree implementation выглядит довольно хорошо.
Поздний ответ, но это хороший один https://github.com/dbotha/Javascript-k-d-tree (отказ от ответственности - я знаю автора)
Это хорошо, но в настоящее время оно реализовано только для двух измерений - словом, это двухмерное дерево, а не дерево k-d. –
Черт возьми, совсем забыл об этом (я использовал его только для чистого 2d недавно), в какой-то момент сделайте это истинным KD, с другой стороны, это не должно быть слишком сложно, чтобы кто-то еще мог ... –
RBush - еще одна реализация R-дерева javascript.
Вот библиотека, которую я написал:
В Chrome это до несколько порядков быстрее, чем kdtree Ubilabs' и поддерживает больший набор запросов (ортогональный диапазон запроса и ограничивающая сфера). Вот ссылка на результаты тестов для последней версии Google Chrome.
Он использует CommonJS/НМП, но прекрасно работает с browserify.
Можно ли создать экземпляр без каких-либо элементов? Планируете ли вы реализовать функцию, которая извлекает все элементы путем эффективной ходьбы по дереву, а не путем вызова ближайшего без ограничения расстояния? Почему функция расстояния иногда проходит по всему объекту и иногда проходит только по размерам? – light24bulbs