[請益] 四元樹找鄰

看板Prob_Solve (計算數學 Problem Solving)作者 (木頭)時間6年前 (2018/04/03 07:57), 6年前編輯推噓7(7026)
留言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
文章代碼(AID): #1QmiDnqY (Prob_Solve)
文章代碼(AID): #1QmiDnqY (Prob_Solve)