Моя версия Quadtree на javascript

• 11, 05, 2014
•  bullgare
•  javascript
• No Comments.

Мне нужно было загружать кучу точек на плоскость и потом быстро узнавать, на какой из этих точек кликнули мышкой.
Точек может быть действительно много — до десяти тысяч — поэтому делать для каждой точки свой DOM-элемент слишком накладно.
Поэтому нужно было эффективно отслеживать клики мышкой на плоскости и вычислять на лету подходящую точку.
Долго возился с алгоритмом voronoi, но потом понял, что это слишком сложно и не очень-то решает мою задачу.
В поисках наткнулся на алгоритм Quadtree («Дерево квадрантов»). Идея — побить плоскость на прямоугольники, которые содержат или другие прямоугольники, или конечные точки («листья»). Бегать по ним можно очень быстро.
.
Реализации на javascript меня не очень воодушевили, так что решил написать свою:
https://github.com/bullgare/quadtree/tree/master
Работает достаточно быстро в chrome, ff, ie, чтобы можно было повесить обработчик на движение мыши и не замечать притормаживания.

Т.е. при количестве точек порядка 10000 работает вполне сносно.

Пример с использованием canvas (в консоль выводятся значения разных таймеров).
http://jsbin.com/xoleziw/1/

Ссылки:
вот здесь было то обсуждение, которое привело меня к quadtree — http://stackoverflow.com/questions/1901139/closest-point-to-a-given-point
Описание алгоритма — https://ru.wikipedia.org/wiki/%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BA%D0%B2%D0%B0%D0%B4%D1%80%D0%B0%D0%BD%D1%82%D0%BE%D0%B2

Similar Posts

• Voronoi algorithm
• Алгоритм динамического центрирования меню по нужному элементу