Связанный граф с квадрантами (путь)

Question

Я читал некоторые о квадрантах, и я стараюсь использовать их для поиска путей. С этой целью я пытаюсь использовать квадрант для создания связанного графа, где каждый «минимальный прямоугольник» (бездетный узел) напрямую связан с его соседними минимальными прямоугольниками. Чтобы проиллюстрировать ... если вы посмотрите на правый нижний прямоугольник в http://en.wikipedia.org/wiki/File:Point_quadtree.svg, этот прямоугольник является бездетным узлом в дереве, и он должен быть непосредственно связан с тремя окружающими его прямоугольниками, которые также являются бездетными узлами.

Создание quadtree довольно просто, но я не уверен, как определить связи с ним. Может ли кто-нибудь предложить мне некоторое представление?

Заранее благодарен!

Answer 1

Нижний правый прямоугольник - всего лишь ребенок смежного 3 прямоугольника. Взгляните сверху на него, как пирамида, когда вы стоите на вершине и смотрите, как квадранты делят пространство рекурсивной на 4 направления. вот лучшее объяснение http://blog.notdot.net/2009/11/Damn-Cool-Algorithms-Spatial-indexing-with-Quadtrees-and-Hilbert-Curves