在平面上已經用四元樹切割出大大小小區塊，
目前每個節點資料結構內容為：
父節點、座標邊界、
相對父節點的位置(哪一個象限)，
以及四個子節點。
請問給定某個節點後，
如何找出周圍相鄰(共邊)的所有節點？
及其複雜度為多少？
之後想利用這個加 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的鄰居父親方向也不難，一直往上推，直到共同祖先出現以前都會是鄰居