amarao_san

Category:

equart'овское - поиск в дереве

Ещё одна интересная проблема, точнее оптимизация, которую я сейчас осознал, связана с нахождением точек в регионе. В общем случае основное 'read' применение моего QuadTree дерева — ответить списком хранимых в нём 2D точек, заданных f64 координатами x,y, которые находятся внутри заданной области.

Когда идёт tree traversal, дерево начинается с собственного Boundry, описывающего границы дерева. Дальше мы его режем на квадранты (или ротирующиеся на 90° половинки, как предложил Олег), и каждый квадрант либо содержит точки, либо 4 (2) других региона. При поиске мы выбираем какие квадратны сканировать дальше, а какие точно out of range.

В моём текущем регионе попадающие в искомую область (хотя бы частично) регионы рекурсивно обходятся дальше. Но вот тут я подумал... Это же колоссальная вычислительная нагрузка. Сначала для каждого квадранта считается overlap (а это аж 8 операций f64, потом для каждой точки в самом низу дерева делается is_inside, что даёт ещё 4 f64). При глубине дерева в 10 это 84 операции, чтобы достать одну точку (для одной точки дерево не будет глубиной 10, но это другой вопрос).

Так вот, идея: если у нас квадрант целиком в искомом регионе мы:

а) можем больше не делать рекурсивную проверку границ вложенных квадрантов.

б) можем не проверять is_inside для каждой точки. Если точка находится где-то глубоко в 10ом потомке квадранта, который целиком inside региона, то она очевидно внутри этого региона (если мы правильно insert сделали).

Таким образом алгоритм чуть усложняется, но ускоряется:

Если это конечная нода с точками, то мы вынуждены каждую точку is_inside.

Если это нода с квадрантами, то для каждого квадранта:
* Если он полностью inside искомого региона — вынуть все точки (рекурсивно) не сравнивая их координаты.

*Если он полностью outside, то пропускаем (как сейчас)

* Если он частично overlap, то рекурсивно вызываем поиск для этого квадранта.

После реализации этого алгоритма надо будет серьёзно пересчитывать максимальное число точек в локальном массиве Leaf'а (у меня в предыдущих тестах оказалось, что если leaf хранит порядка 10 точек в неупорядоченном массиве, то это быстрее, чем если leaf хранит одну точку из-за накладных расходов дерева).

Error

default userpic

Your IP address will be recorded 

When you submit the form an invisible reCAPTCHA check will be performed.
You must follow the Privacy Policy and Google Terms of use.