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

有效

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

本發(fā)明公開(kāi)了基于快速構(gòu)建KD樹(shù)的地球模擬系統(tǒng)網(wǎng)格重映射方法，包括以下步驟：基于地理信息數(shù)據(jù)構(gòu)建KD樹(shù)；獲取目標(biāo)網(wǎng)格點(diǎn)，在所述的KD樹(shù)中搜索對(duì)應(yīng)的源網(wǎng)格點(diǎn)；根據(jù)目標(biāo)網(wǎng)格點(diǎn)和對(duì)應(yīng)的源網(wǎng)格點(diǎn)，重映射網(wǎng)格信息。本發(fā)明方法中整個(gè)KD樹(shù)構(gòu)建過(guò)程分為兩部分，第一部分為構(gòu)建建樹(shù)索引數(shù)組，第二部分為根據(jù)建樹(shù)索引數(shù)組構(gòu)建KD樹(shù)，使得KD樹(shù)能夠被快速高效地構(gòu)建，同時(shí)本發(fā)明方法中使用的基于KD樹(shù)的目標(biāo)網(wǎng)格點(diǎn)搜索過(guò)程，能夠快速定位源網(wǎng)格點(diǎn)。本發(fā)明方法對(duì)網(wǎng)格類型無(wú)要求，具有準(zhǔn)確、高效和適用性強(qiáng)的特點(diǎn)，能較好的解決網(wǎng)格重映射的現(xiàn)實(shí)問(wèn)題，具有廣泛的應(yīng)用前景。

技術(shù)領(lǐng)域

本發(fā)明涉及地理信息數(shù)據(jù)處理與重構(gòu)技術(shù)領(lǐng)域，尤其涉及基于快速構(gòu)建KD樹(shù)的地球模擬系統(tǒng)網(wǎng)格重映射方法。

背景技術(shù)

全球以及區(qū)域地球信息模擬系統(tǒng)在氣候演變、天氣預(yù)報(bào)、災(zāi)害預(yù)警等方面起到了重要的作用。地球信息模擬系統(tǒng)通常耦合了多個(gè)分量模式，如大氣、海洋、陸面等等。分量模式之間通過(guò)信息交換，相互影響。由于各分量模式所采用的網(wǎng)格通常不一樣，為了實(shí)現(xiàn)不同模式間的信息交換，需要通過(guò)重映射技術(shù)將數(shù)據(jù)從源網(wǎng)格插值到目標(biāo)網(wǎng)格上去。常用的插值的方法有雙線性插值、守恒性插值、反距離權(quán)重插值等等。

網(wǎng)格重映射技術(shù)是實(shí)現(xiàn)數(shù)據(jù)在不同網(wǎng)格之間傳遞的重要機(jī)制，而搜索關(guān)聯(lián)點(diǎn)又是其中最復(fù)雜、最耗時(shí)的操作。目前，針對(duì)無(wú)序排列的非結(jié)構(gòu)網(wǎng)格，高效穩(wěn)定的搜索算法還很少。然而，隨著基于非結(jié)構(gòu)網(wǎng)格模式的興起以及模式分辨率的提高，工程實(shí)踐對(duì)非結(jié)構(gòu)網(wǎng)格高效搜索算法的需求也越來(lái)越迫切。

對(duì)于結(jié)構(gòu)規(guī)則的網(wǎng)格來(lái)說(shuō)，可以利用已知的網(wǎng)格點(diǎn)排列規(guī)則創(chuàng)造出高效率的搜索算法。然而，對(duì)于非結(jié)構(gòu)網(wǎng)格來(lái)說(shuō)，網(wǎng)格排列通常是無(wú)序的，無(wú)法建立各網(wǎng)格點(diǎn)之間連通性的邏輯索引，因此，針對(duì)結(jié)構(gòu)網(wǎng)格的很多搜索優(yōu)化算法將失效。隨著各分量模式分辨率的不斷提升，網(wǎng)格越來(lái)越密，網(wǎng)格規(guī)模也越來(lái)越大，對(duì)非結(jié)構(gòu)網(wǎng)格與其他網(wǎng)格之間重映射算法效率的要求也越來(lái)越高。以最鄰近點(diǎn)重映射為例，最直觀的最鄰近點(diǎn)搜索算法即為暴力搜索，求源網(wǎng)格上所有點(diǎn)與目標(biāo)網(wǎng)格的距離，然后選取距離最小的點(diǎn)。一種改進(jìn)算法為將源網(wǎng)格點(diǎn)按照不同維度進(jìn)行分塊，目標(biāo)網(wǎng)格點(diǎn)將在其所屬的塊以及所屬塊鄰近的塊中搜索最近點(diǎn)。這種方法可以在一定程度上排除掉大量不必要的搜索空間，并且易于并行處理。但該方法可能遇到兩個(gè)問(wèn)題：一是如果空間中的點(diǎn)分布極度不均勻，在點(diǎn)較為密集的塊中搜索的效率將極大降低。如果是并行搜索，這些塊中搜索耗時(shí)將是整個(gè)搜索過(guò)程的瓶頸。二是搜索過(guò)程中可能會(huì)遇到最鄰近點(diǎn)不在所屬塊以及所屬塊鄰近塊的情況。。

將非結(jié)構(gòu)網(wǎng)格上的網(wǎng)格點(diǎn)抽象為一個(gè)無(wú)序的K維空間點(diǎn)集，將目標(biāo)網(wǎng)格點(diǎn)抽象為一個(gè)K維空間點(diǎn)，那么在源網(wǎng)格上尋找目標(biāo)點(diǎn)的關(guān)聯(lián)點(diǎn)的問(wèn)題就可以抽象為如何在一個(gè)K維空間內(nèi)，從一個(gè)特定點(diǎn)集中為目標(biāo)點(diǎn)找到關(guān)聯(lián)點(diǎn)的問(wèn)題。基于KD樹(shù)的搜索算法是一種解決多維空間搜索問(wèn)題的經(jīng)典算法，被廣泛應(yīng)用于最鄰近點(diǎn)搜索、范圍搜索等方面。其基本思想為將高維度搜索空間依次按照某一維度進(jìn)行分割，以便形成更小的搜索空間，直到搜索空間內(nèi)最多只有一個(gè)待搜索點(diǎn)，整個(gè)搜索空間按照分割順序用二叉樹(shù)的形式組織起來(lái)。以最鄰近點(diǎn)搜索為例，空間劃分完成之后，首先搜索目標(biāo)點(diǎn)所在的空間，然后依照之前空間分割過(guò)程的逆序，依次判斷其他空間是否存在有更近點(diǎn)的可能。KD樹(shù)本質(zhì)上用二叉樹(shù)的形式實(shí)現(xiàn)了對(duì)空間的分塊。與傳統(tǒng)分塊搜索算法不同之處在于：一、分割線必須穿過(guò)至少一個(gè)源網(wǎng)格點(diǎn)；二、子塊中最多只有一個(gè)待搜索點(diǎn)；三、搜索空間根據(jù)需要對(duì)不同維度進(jìn)行分割。為了進(jìn)一步提高KD樹(shù)的查詢效率，每次劃分需保持左右子樹(shù)上的元素個(gè)數(shù)相當(dāng)(即構(gòu)建一個(gè)平衡樹(shù))，并且優(yōu)先劃分方差高的維度(劃分的空間越均勻，在其他空間存在更近點(diǎn)的可能性越小)。

發(fā)明內(nèi)容

有鑒于此，有必要針對(duì)上述技術(shù)問(wèn)題，提供基于快速構(gòu)建KD樹(shù)的地球模擬系統(tǒng)網(wǎng)格重映射方法，所述方法針對(duì)非結(jié)構(gòu)地理網(wǎng)格與其他網(wǎng)格之間的高效重映射搜索問(wèn)題，實(shí)現(xiàn)了基于KD樹(shù)的重映射搜索方法，在構(gòu)建KD樹(shù)時(shí)，采用更加快速的方法，使得地理空間數(shù)據(jù)的組織與重構(gòu)搜索更加高效。

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

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