[發(fā)明專利]基于快速構(gòu)建KD樹的地球模擬系統(tǒng)網(wǎng)格重映射方法

有效

• 申請?zhí)枺?/td>: 202011103135.2
• 申請日: 2020-10-15
• 公開（公告）號: CN112181991B
• 公開（公告）日: 2021-06-15
• 發(fā)明（設(shè)計）人: 曹宇;王輝贊;趙文靜;段博恒;張小將
• 申請（專利權(quán)）人: 中國人民解放軍國防科技大學
• 主分類號: G06F16/22
• 分類號: G06F16/22;G06F16/245;G06F16/29
• 代理公司: 長沙大珂知識產(chǎn)權(quán)代理事務(wù)所(普通合伙) 43236
• 代理人: 伍志祥

1.基于快速構(gòu)建KD樹的地球模擬系統(tǒng)網(wǎng)格重映射方法，其特征在于，包括以下步驟：

步驟1，基于地理信息數(shù)據(jù)構(gòu)建KD樹；

步驟2，獲取目標網(wǎng)格點，在所述的KD樹中搜索對應的源網(wǎng)格點；

步驟3，根據(jù)目標網(wǎng)格點和對應的源網(wǎng)格點，重映射網(wǎng)格信息；

步驟1中所述的KD樹的節(jié)點的數(shù)據(jù)結(jié)構(gòu)包括：當前節(jié)點的值，即位置坐標，當前節(jié)點的劃分維度以及分別指向左右子樹的兩個指針；所述的KD樹的構(gòu)建過程包括以下步驟：

步驟101，預排序和初始化；

步驟102，重復的選擇劃分維度D和處理BN，SS，CUR數(shù)組，直到SS內(nèi)的每一個元素都為0，劃分維度的選取包括選擇方差最大的維度或依次選擇各個維度，其中，BN數(shù)組，SS數(shù)組和CUR數(shù)組均為整數(shù)類型的數(shù)組，每個數(shù)組的大小均為N，N為元素個數(shù)，BN[i]用來記錄元素i所屬子樹集合的起始位置，被選為中位點的元素將被固定在該子樹集合所在區(qū)段的中間，SS[j]用來記錄起始位置為j的元素所屬子樹剩余的元素個數(shù)，當其被選為KD樹的節(jié)點時，無論是中間節(jié)點還是葉子節(jié)點，其值將歸0，同時，對應元素的BN值也將不再變化，CUR[k]數(shù)組用來記錄起始位置為k的元素所屬子樹已經(jīng)排列好的元素的個數(shù)；

步驟103，根據(jù)BN數(shù)組構(gòu)建建樹索引數(shù)組F，將F數(shù)組的第BN[i]號元素置為i即可；

步驟104，根據(jù)建樹索引數(shù)組F，遞歸的構(gòu)建KD樹；

BN，SS，CUR數(shù)組的處理過程具體為：從頭到尾遍歷D索引數(shù)組內(nèi)的每一個元素tmpi，若其已經(jīng)被選中，則跳過，否則賦值tmpBN＝BN[tmpi]，根據(jù)CUR[tmpBN]判斷元素tmpi屬于左子樹或者右子樹或者為中位點，若屬于左或右子樹，則設(shè)置BN[tmpi]為對應的左或右子樹起始位置，否則，設(shè)置BN[tmpi]為當前子樹段的中間位置，并設(shè)置相應的SS值為0，當前子樹段內(nèi)的所有元素都處理完了以后，重置SS和CUR數(shù)組中相對應的元素。

2.根據(jù)權(quán)利要求1所述的地球模擬系統(tǒng)網(wǎng)格重映射方法，其特征在于，步驟2中所述的搜索對應的源網(wǎng)格點包括以下步驟：當KD樹的當前點T為空時，結(jié)束搜索；否則，首先判斷T所劃分的維度K并計算T與目標點M之間的距離；如果T距離M更近，則需更新最小距離D和對應的最近點；在這之后，進入子樹繼續(xù)搜索；如果當目標點M在劃分維度K上的值小于等于當前點T在K維上的值，意味著M位于T的左子樹空間內(nèi)，該空間內(nèi)的點與M的距離比右子樹空間內(nèi)的點與M的距離更小，因此優(yōu)先遞歸的搜索T的左子樹；反之，優(yōu)先搜索T的右子樹；當搜索到葉子節(jié)點時，搜索過程開始回溯，判斷目標點與當前點在K維上的距離是否大于最小距離D，若是，意味著當前點T的另一子樹空間內(nèi)不可能存在更近的點，則繼續(xù)回溯；否則，需要進一步搜索當前點T的另一子樹空間。

3.根據(jù)權(quán)利要求1所述的地球模擬系統(tǒng)網(wǎng)格重映射方法，其特征在于，步驟2中所述的搜索對應的源網(wǎng)格點包括以下步驟：當KD樹的當前點T為空時，結(jié)束搜索；否則，首先判斷T所劃分的維度K并計算T與目標點M之間的距離；如果T與M之間的距離在指定范圍內(nèi)，則需記錄當前點T；在這之后，進入子樹繼續(xù)搜索；如果當目標點M在劃分維度K上的值小于等于當前點T在K維上的值，意味著M位于T的左子樹空間內(nèi)，該空間內(nèi)的點與M的距離可能比右子樹空間內(nèi)的點與M的距離更小，因此優(yōu)先遞歸的搜索T的左子樹；反之，優(yōu)先搜索T的右子樹；當搜索到葉子節(jié)點時，搜索過程開始回溯；判斷目標點與當前點在K維上的距離是否大于指定范圍；若是，意味著當前點T的另一子樹空間內(nèi)不可能存在更近的點，則繼續(xù)回溯；否則，需要進一步搜索當前點T的另一子樹空間。