Поиск ближайшего соседа в D3

Я реализовал двумерное дерево kd в Javascript (проверьте это на GitHub), и я использую его для поиска ближайшего соседа вместе с D3.

Я узнал, что есть реализация дерева квадрантов в D3, но также обнаружил, что API документация скудна, а поиск в Google не дает результатов. Когда это возможно, я предпочитаю использовать библиотеку, которую посещали многие люди, чем свое заново изобретенное колесо.

Как выполнить поиск ближайшего соседа с помощью квадродерева D3? Под ближайшим соседом я имею в виду:

  • Заполните квадродерево двумерными точками
  • Поиск точки, содержащейся в дереве квадрантов, ближайшей к новой точке, которая не обязательно существует в дереве квадрантов.

javascript d3.js nearest-neighbor quadtree
person Jacob Marble    schedule 25.09.2012    source источник
comment
Из любопытства и ничего другого, для чего вы используете JS K-D Tree?   -  person Sajjan Sarkar    schedule 04.10.2012
comment
@Sajjan У меня ‹circle› s в ‹svg›, и при перемещении мыши выделяется кружок, ближайший к положению мыши. Он очень гладкий и хорошо масштабируется, потому что поиск ближайшего соседа в двумерном K-D дереве составляет O (log n).   -  person Jacob Marble    schedule 05.10.2012
comment
Прохладный! Можно ли поделиться своим кодом (если, конечно, он не является частным или частным)? Думаю, я мог бы многому у него научиться.   -  person Sajjan Sarkar    schedule 05.10.2012
comment
@SajjanSarkar добавил ссылку на содержание моего вопроса, наслаждайтесь!   -  person Jacob Marble    schedule 07.10.2012

Ответы (1)


arrow_upward
6
arrow_downward

Демонстрация чистки на самом деле не находит ближайшего соседа, а скорее находит точки квадродерева, содержащиеся в данном прямоугольнике. (Попробуйте очистить пустой прямоугольник, и он не обязательно посещает своих ближайших соседей.)

Я создал пример, который эффективно находит ближайшего соседа в дереве квадрантов к произвольной точке - см. http://bl.ocks.org/patricksurry/6478178

person patricksurry    schedule 07.09.2013
comment
Возможен ли поиск ближайшего соседа по широте и долготе на картах leaflet.js? - person gkuhu; 03.11.2018