K-d Tree ( 資料 Wiki )
這是我之前用過的一個空間切分的二元搜尋樹演算法
主要用來快速查詢一個空間範圍內的點
當然，如果是不停移動的點就不太適用了
________________________________________
概略介紹一下這個搜尋樹的特點
看不懂的請先去查 二元樹 Binary Tree 有些基本概念再來噢~
他的構成方式很簡單
1. 以一個點為開頭
2. 將後來放入的點
第一層判斷 X位置 比第一層的點大的放左邊的樹，比他小的放右邊的樹
第二層判斷 Y位置 比第二層的點大的放左邊的樹，比他小的放右邊的樹
第三層再改判斷X位置... 以此類推，直到樹的底部
用途上
就是快速搜尋一個範圍內的點
那因為我自己有特殊需求，所以我會額外做一些手腳來做簡化和加速
他在新增和移除一個點的時間都是 LogN
算是滿快速的一種用法
但並不適用於會移動的點上
_____________________________________________
今天下午花了不少時間找這個資料
做個筆記囉
之前寫過這個東西但沒紀錄下來，現在得重弄一個了
![]()
Have a nice Day ![]()
LINE