graph - 四叉树连通图(寻路)

Question

我读了一些关于四叉树的文章，我正在尝试利用它们进行寻路。为此，我试图使用四叉树来创建一个连通图，其中每个“最小矩形”(无子节点)直接连接到其相邻的最小矩形。为了说明...如果您看一下 http://en.wikipedia.org/wiki/File:Point_quadtree.svg 中右下角的矩形，那个矩形是树中的一个无子节点，它应该直接连接到它周围的三个矩形，这三个矩形也是无子节点。

创建四叉树非常简单，但我不确定如何检测与它的连接。谁能给我一些见解？

提前致谢!

Answer 1

右下角的矩形只是相邻的 3 个矩形的子元素。当你站在顶部时，从上面看它就像一个金字塔，看看四叉树如何将空间递归地划分为 4 个方向。这是一个更好的解释http://blog.notdot.net/2009/11/Damn-Cool-Algorithms-Spatial-indexing-with-Quadtrees-and-Hilbert-Curves