作者WoodChen (木头)
看板Prob_Solve
标题四元树找邻
时间Tue Apr 3 07:57:34 2018
在平面上已经用四元树切割出大大小小区块，
目前每个节点资料结构内容为：
父节点、座标边界、
相对父节点的位置(哪一个象限)，
以及四个子节点。
请问给定某个节点後，
如何找出周围相邻(共边)的所有节点？
及其复杂度为多少？
之後想利用这个加 A* 来做路径搜寻，
所以找相邻演算法本身也不能太慢。
Google 可能关键字下错，找不太到答案。
----
Sent from
BePTT
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 27.52.35.193
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1522713457.A.D22.html
1F：推 s89162504: 你说的是kd tree吗? 04/03 08:04
2F：→ WoodChen: 不是，是 quadtree 04/03 08:45
3F：推 springman: 所找到的节点数最多有没有可能接近总节点数呢？ 04/03 10:55
4F：→ springman: 哦、切得愈多，比例就会愈低，可能还好。 04/03 10:56
5F：推 s89162504: 相邻的定义是什麽? 04/03 11:36
6F：→ WoodChen: 树的每个节点都是正方形，相邻代表有边重叠。例如第一 04/03 12:21
7F：→ WoodChen: 象限与第四象限就是相邻。但相邻不见得面积要一样。 04/03 12:21
9F：→ DJWS: 记忆体价格便宜容易扩充 大家都用空间换时间 04/05 06:17
https://i.imgur.com/IJVtKYD.png
目前是用测试周遭区域的方式来找空白区域(白色)。
给一个 x,y 座标，求该座标是落在红色或白色区域的复杂度为 ln(N)
蓝色区域周围最多会有 4*蓝色边长/最小切割区域边长 的待测点
最好的情况下待测点只有 4 个。
配合 A* 是可以跑，性能目前看起来也还可以，
但若按照上面的推论，可能还是有些不足。
不过因为我还必须动态的改动红白区域(白色变红色或红色变白色)，
不知道 DCEL 建表的性能如何？
过几天再试试看，谢谢
※ 编辑: WoodChen (36.237.83.117), 04/05/2018 21:44:04
10F：推 ddavid: 总觉得如果用二元编码後会有某种程度的公式解找到同层邻居 04/06 01:55
11F：→ ddavid: ，再利用邻居的父亲若非自己的父亲则必也为邻居、上邻居的 04/06 01:57
12F：→ ddavid: 下方子节点也必为上邻居之类的性质好像有可能从同层邻居把 04/06 01:58
13F：→ ddavid: 所有邻居推出来，然而我不知道效率好不好 04/06 01:58
14F：→ ddavid: 这边讲到二元编码是上下1 bit、左右1 bit，所以右上、右下 04/06 02:00
15F：→ ddavid: 、左上、左下分别为01 11 00 10 04/06 02:00
16F：→ ddavid: 然後可能就可以依目标的某些特性，用改变其中几个bit的公 04/06 02:01
17F：→ ddavid: 式取得四个方向的同一层（即大小相等的）邻居 04/06 02:02
18F：→ ddavid: 只是我没有去仔细推敲是否确实可行以及效率 04/06 02:03
21F：→ DJWS: ^^^^^^^^^^^^ 说反了 04/06 06:01
22F：→ DJWS: 这应该跟二元树的前继截点/後继节点 差不多意思吧 04/06 06:10
23F：→ WoodChen: 如果周围的相邻面多的话，自然测试点就多，因为是要找 04/11 23:12
24F：→ WoodChen: 出所有相邻面 04/11 23:12
25F：推 ddavid: 其他所有邻面必然是同层邻居的子或父节点，所以要找出所 04/12 15:55
26F：→ ddavid: 有都是可以从同层的出发 04/12 15:55
27F：→ ddavid: 而且有一些方向关系可以肯定，比如A是B的上方同层邻居，则 04/12 15:55
28F：→ ddavid: A所有只往下方走（包括左下跟右下）的子孙节点都同样是B 04/12 15:55
29F：→ ddavid: 的邻居 04/12 15:55
30F：→ ddavid: 这就是上面讲编码方便的其中一个地方，找到上同层邻居A以 04/12 15:56
31F：→ ddavid: 後，我在A编码後面无限制接上10或11全都自然是B的邻居 04/12 15:56
32F：→ ddavid: 父亲方向也不难，一直往上推，直到共同祖先出现以前都会是 04/12 15:56
33F：→ ddavid: 邻居 04/12 15:56