小屋創作

日誌2014-11-04 17:11

Unity資料蒐集 - 演算法 K-d Tree

作者:悠浪貓

K-d Tree ( 資料 Wiki )

這是我之前用過的一個空間切分的二元搜尋樹演算法

主要用來快速查詢一個空間範圍內的點

當然,如果是不停移動的點就不太適用了

________________________________________

概略介紹一下這個搜尋樹的特點

看不懂的請先去查 二元樹 Binary Tree 有些基本概念再來噢~

他的構成方式很簡單

1. 以一個點為開頭

2. 將後來放入的點
        第一層判斷 X位置 比第一層的點大的放左邊的樹,比他小的放右邊的樹
        第二層判斷 Y位置 比第二層的點大的放左邊的樹,比他小的放右邊的樹
        第三層再改判斷X位置... 以此類推,直到樹的底部



用途

就是快速搜尋一個範圍內的點

那因為我自己有特殊需求,所以我會額外做一些手腳來做簡化和加速


他在新增和移除一個點的時間都是 LogN

算是滿快速的一種用法

但並不適用於會移動的點上



_____________________________________________

今天下午花了不少時間找這個資料

做個筆記囉

之前寫過這個東西但沒紀錄下來,現在得重弄一個了



Have a nice Day

0

0

LINE 分享

相關創作

【茶飲&生活】2024/06/14(五)、簡單的整理&喝咖啡

了不起的AI修仙禮包碼/交流群/兌換碼/序號碼/虛寶碼/討論群

【開箱】KAWASAKI NINJA400 我的第一台重機!

留言

開啟 APP

face基於日前微軟官方表示 Internet Explorer 不再支援新的網路標準,可能無法使用新的應用程式來呈現網站內容,在瀏覽器支援度及網站安全性的雙重考量下,為了讓巴友們有更好的使用體驗,巴哈姆特即將於 2019年9月2日 停止支援 Internet Explorer 瀏覽器的頁面呈現和功能。
屆時建議您使用下述瀏覽器來瀏覽巴哈姆特:
。Google Chrome(推薦)
。Mozilla Firefox
。Microsoft Edge(Windows10以上的作業系統版本才可使用)

face我們了解您不想看到廣告的心情⋯ 若您願意支持巴哈姆特永續經營,請將 gamer.com.tw 加入廣告阻擋工具的白名單中,謝謝 !【教學】