四元樹找鄰

[WoodChen (木頭)]

在平面上已經用四元樹切割出大大小小區塊，

目前每個節點資料結構內容為：

父節點、座標邊界、
相對父節點的位置(哪一個象限)，
以及四個子節點。

請問給定某個節點後，
如何找出周圍相鄰(共邊)的所有節點？
及其複雜度為多少？

之後想利用這個加 A* 來做路徑搜尋，
所以找相鄰演算法本身也不能太慢。

Google 可能關鍵字下錯，找不太到答案。

----
Sent from BePTT

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 27.52.35.193
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1522713457.A.D22.html
推 s89162504: 你說的是kd tree嗎?
→ WoodChen: 不是，是 quadtree
推 springman: 所找到的節點數最多有沒有可能接近總節點數呢？
→ springman: 哦、切得愈多，比例就會愈低，可能還好。
推 s89162504: 相鄰的定義是什麼?
→ WoodChen: 樹的每個節點都是正方形，相鄰代表有邊重疊。例如第一
→ WoodChen: 象限與第四象限就是相鄰。但相鄰不見得面積要一樣。
推 DJWS: https://tinyurl.com/ydguu93u    轉成dcel  這樣可以嗎?
→ DJWS: 記憶體價格便宜容易擴充  大家都用空間換時間
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
推 ddavid: 總覺得如果用二元編碼後會有某種程度的公式解找到同層鄰居
→ ddavid: ，再利用鄰居的父親若非自己的父親則必也為鄰居、上鄰居的
→ ddavid: 下方子節點也必為上鄰居之類的性質好像有可能從同層鄰居把
→ ddavid: 所有鄰居推出來，然而我不知道效率好不好
→ ddavid: 這邊講到二元編碼是上下1 bit、左右1 bit，所以右上、右下
→ ddavid: 、左上、左下分別為01 11 00 10
→ ddavid: 然後可能就可以依目標的某些特性，用改變其中幾個bit的公
→ ddavid: 式取得四個方向的同一層（即大小相等的）鄰居
→ ddavid: 只是我沒有去仔細推敲是否確實可行以及效率
推 DJWS: https://stackoverflow.com/questions/32412107/ 四元樹鄰居
→ DJWS: https://tinyurl.com/ydguu93u  DCEL轉四元樹  以及性能
→ DJWS:                                ^^^^^^^^^^^^ 說反了
→ DJWS: 這應該跟二元樹的前繼截點/後繼節點  差不多意思吧
→ WoodChen: 如果周圍的相鄰面多的話，自然測試點就多，因為是要找
→ WoodChen: 出所有相鄰面
推 ddavid: 其他所有鄰面必然是同層鄰居的子或父節點，所以要找出所
→ ddavid: 有都是可以從同層的出發
→ ddavid: 而且有一些方向關係可以肯定，比如A是B的上方同層鄰居，則
→ ddavid: A所有只往下方走（包括左下跟右下）的子孫節點都同樣是B
→ ddavid: 的鄰居
→ ddavid: 這就是上面講編碼方便的其中一個地方，找到上同層鄰居A以
→ ddavid: 後，我在A編碼後面無限制接上10或11全都自然是B的鄰居
→ ddavid: 父親方向也不難，一直往上推，直到共同祖先出現以前都會是
→ ddavid: 鄰居