Предложен алгоритм поиска областей по точкам на основе 6-мерного дерева
Для поиска области в двумерном пространстве, которой принадлежит заданная точка, предложили хранить коллекцию областей в дереве с шестью измерениями вместо обычного перебора массива. Каждая область задаётся начальной точкой P0 и конечной P1, а сами области не пересекаются.
Классическое KD-дерево делит пространство бинарно, чередуя измерения при переходе между слоями. В предложенном варианте дерево расширяется до шести измерений: каждой ветви потомков узла ставится в соответствие один из вариантов взаимного расположения отрезков по оси X или Y в зависимости от слоя.
Классификация идёт по положению начальной точки второго отрезка, а подкласс определяется его конечной точкой. Поскольку отрицательной длины не бывает, число возможных вариантов сокращается при движении начальной точки от меньшего значения к большему при фиксированном родительском отрезке.
При поиске алгоритм переходит только в те дочерние ветви, которые определяются положением искомой точки относительно базового отрезка. В каждом узле проверяется, лежит ли точка внутри области, ограниченной P0 и P1; если да, поиск прекращается и возвращается найденная область.
Если области пересекаются, поиск идёт до нижнего уровня дерева и возвращает коллекцию всех найденных областей. В примере пространство 8×8 клеток разделено между 21 областью, а для точки P (X = 7, Y = 1) алгоритм определил область под индексом 17.
При тестировании сравнивали число проверок принадлежности точек областям: последовательный перебор массива и предложенный алгоритм. Выигрыш в производительности зависит от размерности коллекции областей; сценарием был последовательный поиск для всех точек пространства.
Автор не заявляет исключительных прав на алгоритм. К его недостаткам он отнёс отсутствие масштабируемости при изменении размерности пространства, тогда как обычные бинарные деревья универсальны.