[請益] 四元樹找鄰

看板Prob_Solve作者 (木頭)時間6年前 (2018/04/03 07:57), 6年前編輯推噓7(7推 0噓 26→)
留言33則, 5人參與, 6年前最新討論串1/1
在平面上已經用四元樹切割出大大小小區塊， 目前每個節點資料結構內容為： 父節點、座標邊界、 相對父節點的位置(哪一個象限)， 以及四個子節點。 請問給定某個節點後， 如何找出周圍相鄰(共邊)的所有節點？ 及其複雜度為多少？ 之後想利用這個加 A* 來做路徑搜尋， 所以找相鄰演算法本身也不能太慢。 Google 可能關鍵字下錯，找不太到答案。 ---- Sent from BePTT -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 27.52.35.193 ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1522713457.A.D22.html
推
04/03 08:04, 6年前 , 1F
你說的是kd tree嗎?
04/03 08:04, 1F
→
04/03 08:45, 6年前 , 2F
不是，是 quadtree
04/03 08:45, 2F
推
04/03 10:55, 6年前 , 3F
所找到的節點數最多有沒有可能接近總節點數呢？
04/03 10:55, 3F
→
04/03 10:56, 6年前 , 4F
哦、切得愈多，比例就會愈低，可能還好。
04/03 10:56, 4F
推
04/03 11:36, 6年前 , 5F
相鄰的定義是什麼?
04/03 11:36, 5F
→
04/03 12:21, 6年前 , 6F
樹的每個節點都是正方形，相鄰代表有邊重疊。例如第一
04/03 12:21, 6F
→
04/03 12:21, 6年前 , 7F
象限與第四象限就是相鄰。但相鄰不見得面積要一樣。
04/03 12:21, 7F
推
04/05 06:14, 6年前 , 8F
https://tinyurl.com/ydguu93u 轉成dcel 這樣可以嗎?
04/05 06:14, 8F
→
04/05 06:17, 6年前 , 9F
記憶體價格便宜容易擴充 大家都用空間換時間
04/05 06:17, 9F
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
推
04/06 01:55, 6年前 , 10F
總覺得如果用二元編碼後會有某種程度的公式解找到同層鄰居
04/06 01:55, 10F
→
04/06 01:57, 6年前 , 11F
，再利用鄰居的父親若非自己的父親則必也為鄰居、上鄰居的
04/06 01:57, 11F
→
04/06 01:58, 6年前 , 12F
下方子節點也必為上鄰居之類的性質好像有可能從同層鄰居把
04/06 01:58, 12F
→
04/06 01:58, 6年前 , 13F
所有鄰居推出來，然而我不知道效率好不好
04/06 01:58, 13F
→
04/06 02:00, 6年前 , 14F
這邊講到二元編碼是上下1 bit、左右1 bit，所以右上、右下
04/06 02:00, 14F
→
04/06 02:00, 6年前 , 15F
、左上、左下分別為01 11 00 10
04/06 02:00, 15F
→
04/06 02:01, 6年前 , 16F
然後可能就可以依目標的某些特性，用改變其中幾個bit的公
04/06 02:01, 16F
→
04/06 02:02, 6年前 , 17F
式取得四個方向的同一層（即大小相等的）鄰居
04/06 02:02, 17F
→
04/06 02:03, 6年前 , 18F
只是我沒有去仔細推敲是否確實可行以及效率
04/06 02:03, 18F
推
04/06 05:58, 6年前 , 19F
04/06 05:58, 19F
→
04/06 06:00, 6年前 , 20F
https://tinyurl.com/ydguu93u DCEL轉四元樹 以及性能
04/06 06:00, 20F
→
04/06 06:01, 6年前 , 21F
^^^^^^^^^^^^ 說反了
04/06 06:01, 21F
→
04/06 06:10, 6年前 , 22F
這應該跟二元樹的前繼截點/後繼節點 差不多意思吧
04/06 06:10, 22F
→
04/11 23:12, 6年前 , 23F
如果周圍的相鄰面多的話，自然測試點就多，因為是要找
04/11 23:12, 23F
→
04/11 23:12, 6年前 , 24F
出所有相鄰面
04/11 23:12, 24F
推
04/12 15:55, 6年前 , 25F
其他所有鄰面必然是同層鄰居的子或父節點，所以要找出所
04/12 15:55, 25F
→
04/12 15:55, 6年前 , 26F
有都是可以從同層的出發
04/12 15:55, 26F
→
04/12 15:55, 6年前 , 27F
而且有一些方向關係可以肯定，比如A是B的上方同層鄰居，則
04/12 15:55, 27F
→
04/12 15:55, 6年前 , 28F
A所有只往下方走（包括左下跟右下）的子孫節點都同樣是B
04/12 15:55, 28F
→
04/12 15:55, 6年前 , 29F
的鄰居
04/12 15:55, 29F
→
04/12 15:56, 6年前 , 30F
這就是上面講編碼方便的其中一個地方，找到上同層鄰居A以
04/12 15:56, 30F
→
04/12 15:56, 6年前 , 31F
後，我在A編碼後面無限制接上10或11全都自然是B的鄰居
04/12 15:56, 31F
→
04/12 15:56, 6年前 , 32F
父親方向也不難，一直往上推，直到共同祖先出現以前都會是
04/12 15:56, 32F
→
04/12 15:56, 6年前 , 33F
鄰居
04/12 15:56, 33F
‣ 更多 WoodChen 的文章
文章代碼(AID): #1QmiDnqY (Prob_Solve)