基于R-Tree的CAD圖元快速索引研究.pdf

1、當(dāng)CAD 系統(tǒng)處理數(shù)量較大的圖元數(shù)據(jù)時(shí)，自主產(chǎn)權(quán)的CAD 系統(tǒng)相對(duì)AutoCAD等大型CAD 系統(tǒng)，會(huì)出現(xiàn)明顯的顯示滯后現(xiàn)象。圖形的顯示過(guò)程包括從數(shù)據(jù)庫(kù)選擇圖元數(shù)據(jù)，對(duì)編輯處理的消息響應(yīng)，對(duì)圖形的重繪，最后是在硬件上顯示結(jié)果。為了改善顯示滯后的狀況，本文從改進(jìn)與優(yōu)化CAD 系統(tǒng)圖元數(shù)據(jù)索引結(jié)構(gòu)的角度出發(fā)，對(duì)圖形顯示優(yōu)化進(jìn)行了研究與分析。
　　 R-Tree 索引結(jié)構(gòu)是一種具有快速性與動(dòng)態(tài)性的空間索引技術(shù)，它是基于空間數(shù)據(jù)最小邊界

2、矩形的大小與位置構(gòu)造的，在地理信息系統(tǒng)中得到了商業(yè)化的應(yīng)用。對(duì)于二維CAD 圖元數(shù)據(jù)，如果直接使用R-Tree 索引結(jié)構(gòu)，則R-Tree的優(yōu)點(diǎn)并不能有效的發(fā)揮，要將R-Tree 引入CAD 系統(tǒng)中，需要對(duì)其進(jìn)行改進(jìn)。
　　 本文在對(duì)R-Tree 索引結(jié)構(gòu)的特征以及插入、刪除、查找關(guān)鍵算法進(jìn)行詳細(xì)的研究后，分析了影響其查找速率的因素。闡述了不能直接使用R-Tree 索引結(jié)構(gòu)作為CAD圖元數(shù)據(jù)索引結(jié)構(gòu)的原因。此外，對(duì)另一種常見(jiàn)的空間

3、索引技術(shù)——空間四叉樹(shù)索引結(jié)構(gòu)的特征及其算法進(jìn)行了研究與分析。
　　 本文在對(duì)R-Tree和空間四叉樹(shù)這兩種數(shù)據(jù)索引技術(shù)深入研究的基礎(chǔ)上，提出了適用于CAD 圖元數(shù)據(jù)的、基于R-Tree 索引結(jié)構(gòu)、結(jié)合四叉樹(shù)的區(qū)域劃分技術(shù)的索引結(jié)構(gòu)，設(shè)計(jì)了其插入、刪除及查找算法。改進(jìn)的索引結(jié)構(gòu)具有R-Tree 索引結(jié)構(gòu)動(dòng)態(tài)性的特點(diǎn)，通過(guò)區(qū)域劃分技術(shù)的引入減少了圖元邊界的交迭狀況，減少了單棵R-Tree的樹(shù)高，提高了圖元數(shù)據(jù)的索引速度。