在平面上已经用四元树切割出大大小小区块，
目前每个节点资料结构内容为：
父节点、座标边界、
相对父节点的位置(哪一个象限)，
以及四个子节点。
请问给定某个节点后，
如何找出周围相邻(共边)的所有节点？
及其复杂度为多少？
之后想利用这个加 A* 来做路径搜寻，
所以找相邻算法本身也不能太慢。
Google 可能关键字下错，找不太到答案。

你说的是kd tree吗?

不是，是 quadtree

所找到的节点数最多有没有可能接近总节点数呢？哦、切得愈多，比例就会愈低，可能还好。

相邻的定义是什么?

树的每个节点都是正方形，相邻代表有边重叠。例如第一象限与第四象限就是相邻。但相邻不见得面积要一样。

https://tinyurl.com/ydguu93u 转成dcel 这样可以吗?内存价格便宜容易扩充 大家都用空间换时间

总觉得如果用二元编码后会有某种程度的公式解找到同层邻居，再利用邻居的父亲若非自己的父亲则必也为邻居、上邻居的下方子节点也必为上邻居之类的性质好像有可能从同层邻居把所有邻居推出来，然而我不知道效率好不好这边讲到二元编码是上下1 bit、左右1 bit，所以右上、右下、左上、左下分别为01 11 00 10然后可能就可以依目标的某些特性，用改变其中几个bit的公式取得四个方向的同一层（即大小相等的）邻居只是我没有去仔细推敲是否确实可行以及效率

https://stackoverflow.com/questions/32412107/ 四元树邻居https://tinyurl.com/ydguu93u DCEL转四元树 以及性能^^^^^^^^^^^^ 说反了这应该跟二元树的前继截点/后继节点 差不多意思吧

如果周围的相邻面多的话，自然测试点就多，因为是要找出所有相邻面

其他所有邻面必然是同层邻居的子或父节点，所以要找出所有都是可以从同层的出发而且有一些方向关系可以肯定，比如A是B的上方同层邻居，则A所有只往下方走（包括左下跟右下）的子孙节点都同样是B的邻居这就是上面讲编码方便的其中一个地方，找到上同层邻居A以后，我在A编码后面无限制接上10或11全都自然是B的邻居父亲方向也不难，一直往上推，直到共同祖先出现以前都会是邻居