目錄

前言

什么是四叉樹(shù)？

四叉樹(shù)的原理

結(jié)語(yǔ)

前言

????????最近在CAD中開(kāi)發(fā)拓?fù)錂z查和空間分析功能時(shí)發(fā)現(xiàn)，傳統(tǒng)的雙層遞歸法會(huì)極大的降低程序運(yùn)行速度，就比如：圖上有1000個(gè)圖形，我們要求圖形之間的交點(diǎn)，傳統(tǒng)的作法就是遍歷兩次圖形，在兩次循環(huán)中分別對(duì)圖形求交處理，對(duì)于圖形較少的情況，傳統(tǒng)的雙層遞歸法也不會(huì)太多的影響程序的效率，但是如果圖上有10000個(gè)圖形，或者更多圖形呢？按照傳統(tǒng)的雙層遞歸法來(lái)運(yùn)算顯然是不太可能的，可能會(huì)直接導(dǎo)致CAD無(wú)響應(yīng)，大幅度影響計(jì)算效率。為了解決這個(gè)問(wèn)題，針對(duì)大量圖形進(jìn)行空間運(yùn)算的時(shí)候就必須用到空間索引了。

? ? ? ? 我們用過(guò)GIS軟件的小伙伴就能感受到GIS的空間分析功能遠(yuǎn)比CAD強(qiáng)大，最直觀的就是GIS軟件的運(yùn)算速度，很多小伙伴就很好奇為什么它會(huì)這么快，正是因?yàn)樗械腉IS軟件都使用了空間索引，常見(jiàn)的空間索引有很多，比較成熟的有:Rtree、Kdtree、Quadtree等，我們今天要講的就是Quadtree，中文名稱(chēng)叫：四叉樹(shù)。

什么是四叉樹(shù)？

? ? ? ? 本文中使用的編程語(yǔ)言為C#，C#為面向?qū)ο笳Z(yǔ)言，我們開(kāi)始寫(xiě)代碼之前一定得搞懂對(duì)象的定義，我們要寫(xiě)四叉樹(shù)，首先得明白四叉樹(shù)是什么，首先我們來(lái)看看四叉樹(shù)的理論模型圖（圖片源自知乎）：

????????是不是看不太懂？沒(méi)關(guān)系，筆者最開(kāi)始也是看不懂這套模型圖，相對(duì)于網(wǎng)上晦澀難懂的解釋?zhuān)瑢?duì)于大多數(shù)新手朋友來(lái)說(shuō)都是不太友好的，筆者在此將會(huì)以自己的理解跟大家進(jìn)行一個(gè)解讀。

四叉樹(shù)的原理

????????首四叉樹(shù)的原理就是將圖形區(qū)域的最大矩形范圍（根節(jié)點(diǎn)）不斷向下四等分，矩形每劃分一次就形成四個(gè)新的矩形范圍（子節(jié)點(diǎn)），直到滿足設(shè)定條件為止就停止劃分，最終形成成無(wú)數(shù)個(gè)矩形區(qū)域，如下圖：

? ? ? ? 第一步，首先確定出目標(biāo)區(qū)域的最大矩形范圍（根節(jié)點(diǎn)）：

?????????第二步，由最大矩形區(qū)域不斷向下四等分，形成每一層的子節(jié)點(diǎn)

????????筆者在這里一共劃分了三次，每次劃分都形成了一層子節(jié)點(diǎn)（多個(gè)矩形區(qū)域），那么這個(gè)矩形區(qū)域劃分出來(lái)到底有什么作用呢？

? ? ? ? 矩形區(qū)域的作用就是將龐大的空間范圍進(jìn)行劃分，四叉樹(shù)檢索圖形其實(shí)就是檢索矩形區(qū)域對(duì)應(yīng)的圖形，什么意思呢？如下圖所示：

????????從實(shí)例出發(fā)，如上圖所示，圖中一共有四個(gè)矩形，六個(gè)圖形，那么矩形和圖形是什么關(guān)系呢？

? ? ? ? 首先我們要判斷每個(gè)圖形的外包矩形（上圖中的青色部分）和四個(gè)矩形區(qū)域的相交關(guān)系以確定每個(gè)區(qū)域所包含的圖形，上圖的相交與包含關(guān)系圖下：

相交關(guān)系：

• ? ? ? ? 圖形1的外包矩形與矩形一相交，所以矩形一包含圖形1
• ????????圖形2的外包矩形與矩形一相交，所以矩形一包含圖形2
• ????????圖形3的外包矩形與矩形一相交，所以矩形一包含圖形3
• ????????圖形4的外包矩形與矩形一、矩形二、矩形三、矩形四相交，所以矩形一、矩形二、矩形三、矩形四同時(shí)包含圖形4
• ????????圖形5的外包矩形與矩形四相交，所以矩形五包含圖形5
• ?? ? ? ?圖形6的外包矩形與矩形三相交，所以矩形三包含圖形6

包含關(guān)系：

• ????????矩形一包含：圖形1、圖形2、圖形3、圖形4
• ????????矩形二包含：圖形4
• ????????矩形三包含：圖形4、圖形6
• ????????矩形四包含：圖形4、圖形5

? ? ? ? 確定好相交與包含關(guān)系之后，我們就可以進(jìn)行范圍搜索了，還是以上圖為例，我們以圖形1的外包矩形進(jìn)行搜索：

????????首先判斷圖形1與四個(gè)矩形區(qū)域的相交關(guān)系，得出圖形1僅與矩形一相交?，然后根據(jù)上一步的包含關(guān)系即可以拿到圖形1所在區(qū)域所包含的所有圖形：圖形1、圖形2、圖形3、圖形4，通過(guò)這樣的方式進(jìn)行檢索，我們的圖形運(yùn)算就可以按照區(qū)域進(jìn)行，無(wú)需再全圖雙層遞歸對(duì)比了。

? ? ? ? 四叉樹(shù)的工作原理就是將指定的圖形范圍進(jìn)行劃分，每次劃分判斷圖形外包矩形與子節(jié)點(diǎn)的關(guān)系，從而形成一個(gè)位置關(guān)系樹(shù)結(jié)構(gòu)，后期直接通過(guò)給定的矩形范圍逐節(jié)點(diǎn)進(jìn)行判斷指定的矩形范圍屬于哪個(gè)矩形分區(qū)，最后拿出對(duì)應(yīng)矩形分區(qū)所對(duì)應(yīng)的圖形即可。

結(jié)語(yǔ)

????????本章內(nèi)容咱們先理解四叉樹(shù)的原理，下一章我們?cè)僭敿?xì)的教學(xué)如何用C#代碼去編寫(xiě)一個(gè)四叉樹(shù)并進(jìn)行應(yīng)用。如對(duì)本章內(nèi)容有任何疑問(wèn)可掃描下方二維碼，聯(lián)系作者微信。

?

? ? ? ??

?

?

?

? ? ?文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-740729.html

到了這里，關(guān)于C#幾何算法：空間索引——Quadtree四叉樹(shù)及應(yīng)用（一）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！