algorithm - 四叉树中的相邻单元格

Question

有没有办法在四叉树分割中找到相邻的单元格？我的意思是在任何级别与所选单元格相邻的所有单元格？

Answer 1

空间填充曲线完全填充空间并将 2 维减少到 1 维。我在 phpclasses.org(希尔伯特曲线)上写了一个免费的 php 类。它包括一条 z 曲线、4 条希尔伯特曲线和一条摩尔曲线以及一个四键函数。这是一篇关于碰撞检测和四叉树的博客:lab.polygonal.de/?p=202?

莫顿 a.k.a. z 曲线很容易构建。将 x 和 y 值转换为二进制并连接这些值。您可以在这里找到一些代码:http://msdn.microsoft.com/en-us/library/bb259689.aspx .您可以使用最高有效位来验证上边界。