Структура данных для нерегулярной сетки
Мне интересно, какова лучшая структура данных для сетки, содержащей прямоугольники / квадраты разного размера в качестве секторов игровой карты. Мне нужно получить доступ к объекту в этой сетке с помощью простых координат XYZ.
искал KdTrees, но они, кажется, находят ближайший объект, я также нашел сегментированные деревья / интервальные деревья, но информации о них немного.
1 ответ
Вы можете использовать октри. То есть вы можете начать с прямоугольного параллелепипеда, который содержит всю область ((0, 0, 0), (x, y, z))(это корень дерева). На следующем шаге разделите его на 8 прямоугольных параллелепипедов (((0, 0, 0), (x / 2, y / 2, z / 2)), ((0, 0, z / 2), (x / 2, у / 2, з)) и тд). Эти 8 прямоугольных параллелепипедов являются потомками корня. Продолжайте строить дерево рекурсивно для каждого из них. Когда прямоугольный параллелепипед полностью находится внутри одной области, рекурсия должна прекратиться (так что она становится листом дерева).
Чтобы ответить на запрос, начните с корня октерева и переходите к соответствующему ребенку, пока не дойдете до листа.
Также возможно адаптировать дерево kd для решения этой проблемы. Идея похожа на описанную выше: разбить пространство на два полупространства, рекурсивно построить дерево для каждого из них. Базовый случай для рекурсии тоже не изменился: если текущее подпространство находится внутри только одного региона, рекурсия должна быть остановлена.