作者WoodChen (木頭)
看板Prob_Solve
標題四元樹找鄰
時間Tue Apr 3 07:57:34 2018
在平面上已經用四元樹切割出大大小小區塊，
目前每個節點資料結構內容為：
父節點、座標邊界、
相對父節點的位置(哪一個象限)，
以及四個子節點。
請問給定某個節點後，
如何找出周圍相鄰(共邊)的所有節點？
及其複雜度為多少？
之後想利用這個加 A* 來做路徑搜尋，
所以找相鄰演算法本身也不能太慢。
Google 可能關鍵字下錯，找不太到答案。
----
Sent from
BePTT
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 27.52.35.193
※ 文章網址: https://webptt.com/m.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