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

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

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

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