網(wǎng)格索引在ARX開發(fā)中的使用

1、網(wǎng)格索引在ARX開發(fā)中的使用簡介網(wǎng)格索引是GIS軟件中經(jīng)常使用的一種簡單、高效的空間索引技術(shù)，例如著名的ESRI而這僅僅是只有6條線段時的情況，其中的差別可想而知。在ARX中使用網(wǎng)格索引分析網(wǎng)格索引技術(shù)，核心思想是把整個圖形區(qū)域劃分成MxN個矩形網(wǎng)格，每個網(wǎng)格都 是一個數(shù)組，記錄所有從中穿過的圖形。針對“圖1”的情況，需要定義4X4=16個數(shù)組D4， 保存數(shù)據(jù)后，D1C、D1D中都保存了線段6，D2A中保存了線段1，D2B中保存了 線段1、2、3，D2C中保存了線段5，D2D中保存了線段4，等等。那么，在具體實(shí)現(xiàn) 上，只需定義一個 AcArrayAcDbIntArray, AcArrayObj

2、ectCopyReallocator 數(shù)組 的數(shù)組即可，大小初始化為MXN。下面用一個實(shí)例進(jìn)行說明（假設(shè)圖形都是直線段）。2.1創(chuàng)建索引橫向劃分100個網(wǎng)格縱向劃分100個網(wǎng)格#define GRID_XCOUNT 100#define GRID_YCOUNT 100void CreateSpatialIndex（const AcDbVoidPtrArray& lines,AcArrayAcDbIntArray, CArrayObjectCopyReallocator &gridToGeo, 返回空間索引AcGePoint2dArray &ptLBs, 返回每個圖形的左下角AcGePoint2

3、dArray &ptRTs, 返回每個圖形的右上角AcGePoint2d &ptBase,返回所有圖形的左下角AcGeVector2d &gridSize返回網(wǎng)格橫、縱向尺寸）const AcDbLine* pLine;AcGePoint2d ptLB,ptRT; int i,nCount = lines.length();計(jì)算每個圖形的左下角、右上角坐標(biāo)和全部圖形的左下角、右上角坐標(biāo) GetExtents(lines, ptLBs, ptRTs, ptBase, ptRT);每個網(wǎng)格的橫向和縱向尺寸(加1是處理精度問題)gridSize.x = (ptRT.x - ptBase.x)/GRI

4、D_XCOUNT + 1;gridSize.y = (ptRT.y - ptBase.y)/GRID_YCOUNT + 1;初始化空間索引數(shù)組的內(nèi)存gridToGeo.setLogicalLength(GRID_XCOUNT*GRID_YCOUNT);創(chuàng)建索引int nGridXMin, nGridXMax, nGridYMin, nGridYMax;for(i = 0; inCount; i +)計(jì)算每個圖形占用的網(wǎng)格(根據(jù)外包矩形簡化處理)nGridXMin = (ptLBs.at (i).x - ptBase.x)/gridSize.x;nGridYMin = (ptLBs.at(i).

5、y - ptBase.y)/gridSize.y;nGridXMax = (ptRTs.at (i).x - ptBase.x)/gridSize.x;在計(jì)算出的每個網(wǎng)格數(shù)組中添加當(dāng)前圖形的索引nGridYMax = (ptRTs.at(i).y - ptBase.y)/gridSize.y;for(int j = nGridYMin; j = nGridYMax; j +)for(int k=nGridXMin; k = nGridXMax; k+)gridToGeoj*GRID_XCOUNT+k.append(i);2.2使用索引void TestWithSpatialIndex(cons

6、t AcDbVoidPtrArray& lines)AcArrayAcDbIntArray, AcArrayObjectCopyReallocator gridToGeo;/索引AcGePoint2d ptBase; 圖形范圍左下角AcGeVector2d gridSize; 網(wǎng)格尺寸AcGePoint2dArray ptLBs, ptRTs; /每個圖形的左下角，右上角坐標(biāo)/創(chuàng)建空間索引CreateSpatialIndex(lines, gridToGeo, ptLBs, ptRTs, ptBase, gridSize);AcGePoint3dArray results;const AcDb

7、Line *pLine1, *pLine2;int nGridXMin, nGridXMax, nGridYMin, nGridYMax, nIndex, nMaskBufferSize;創(chuàng)建一個映射區(qū)標(biāo)記計(jì)算過的圖形(因?yàn)橐粋€圖形可能會被添加到多個網(wǎng)格中)，每個圖形占 用1位。nMaskBufferSize = (lines.length()+7)/8;BYTE *pMask = new BYTEnMaskBufferSize;兩兩求交for(int i = 0; ilines.length(); i +)pLine1 = (const AcDbLine*)lines.at(i);memse

8、t(pMask, 0, nMaskBufferSize); 映射區(qū)清零計(jì)算當(dāng)前圖形占用的網(wǎng)格(根據(jù)外包矩形簡化處理)nGridXMin = (ptLBs.at (i).x - ptBase.x)/gridSize.x;nGridYMin = (ptLBs.at(i).y - ptBase.y)/gridSize.y;nGridXMax = (ptRTs.at (i).x - ptBase.x)/gridSize.x;nGridYMax = (ptRTs.at(i).y - ptBase.y)/gridSize.y;遍歷占用的所有網(wǎng)格，和其中的圖形求交for(int j = nGridYMin;

9、 j = nGridYMax; j +)for(int k=nGridXMin; k = nGridXMax; k+)/遍歷一個網(wǎng)格中的所有圖形for(int m = 0; mgridToGeoj*GRID_XCOUNT+k.length(); m+)nIndex = gridToGeoj*GRID_XCOUNT+k.at(m);if(nIndex = i)continue;已經(jīng)計(jì)算過了if( (pMasknIndex/8 & (1(nIndex%8) != 0 )continue;標(biāo)記位已設(shè)，已經(jīng)計(jì)算過了設(shè)標(biāo)記位pMasknIndex/8 |= (1 ptRTsnIndex.x) |i.y

10、ptRTsnIndex.y)i.x ptLBsnIndex.x).y intersectWith(pLine2,AcDb:kOnBothOperands, delete pMask; 性能對比通過在一定范圍內(nèi)隨機(jī)生成線段（限定長度在一定范圍），對未采用空間索引和采用網(wǎng)格空間索引兩種計(jì)算方法的性能進(jìn)行對比，結(jié)果如下：篤. . -八注-.“時Jj/|E：七 /崢 * #圖形數(shù)（萬）未采用索 引耗時（秒）采用網(wǎng)格索 引耗時（秒）11.970.03一28.340.06一326.450.14一450.280.50一582.270.77-10-1.30圖2隨機(jī)生成的圖形可以發(fā)現(xiàn)，兩者性能相差可達(dá)幾十倍到1

11、00多倍，對于多于2萬個圖形的情況，采用網(wǎng)格索引后效果非常明顯。對比代碼：void TestNoSpatialIndex(const AcDbVoidPtrArray& lines)int nCount = lines.length();const AcDbLine* pLine1, *pLine2;AcGePoint2dArray ptLBs, ptRTs;AcGePoint2d extentLB, extentRT;GetExtents(lines, ptLBs, ptRTs, extentLB, extentRT);AcGePoint3dArray results;兩兩求交for(int

12、 i = 0; inCount; i +)pLine1 = (const AcDbLine*)lines.at(i);for(int j = i + 1; j ptRTs.at(j).x) |(ptLBs.at (i).y ptRTs.at(j).y)(ptRTs.at(i).x ptLBs.at(j).x)(ptRTs.at(i).y intersectWith(pLine2, AcDb:kOnBothOperands, results);進(jìn)一步優(yōu)化從上一節(jié)中的性能對比表可以看到，圖形數(shù)從1萬升到10萬時，采用網(wǎng)格索引時的耗時也升高了 43倍，這是非常不利的現(xiàn)象。這是因?yàn)榈?節(jié)中的示例代碼過

13、于簡化所致，這個問題可以通過以下幾個環(huán)節(jié)進(jìn)行優(yōu)化處理。4.1網(wǎng)格尺寸和數(shù)目的確定在示例中，網(wǎng)格的數(shù)目是固定的，網(wǎng)格尺寸是從空間范圍和網(wǎng)格數(shù)目倒推出來的，優(yōu)化 的做法應(yīng)該是根據(jù)多數(shù)圖形的尺寸確定網(wǎng)格尺寸，盡量使多數(shù)圖形的尺寸和網(wǎng)格尺寸相近。 也就是說，網(wǎng)格尺寸過大或過小都不合適?？梢约僭O(shè)一下，如果網(wǎng)格尺寸很大，所有圖形都 落在幾個網(wǎng)格內(nèi)，索引就失去了意義；而如果網(wǎng)格尺寸很小，會造成每個圖形都占用大量的 網(wǎng)格，重復(fù)數(shù)據(jù)增多，內(nèi)存占用增大，顯然也是不合適的。4.2采用多級網(wǎng)格如果圖形尺寸相差很大，采用一級網(wǎng)格時網(wǎng)格尺寸就很難確定，這時可以采用多級網(wǎng)格， 各級之間的網(wǎng)格尺寸大小最好相差5倍以上。例如一級網(wǎng)格尺寸為2mx5m，二級網(wǎng)格就可 以定為20mx30m，三級網(wǎng)格可以設(shè)為200mx500m等，具體識該級別的圖形尺寸而定，有些 情況下，各級之間可以相差上百倍。在使用時，如果一個圖形需要占用非常多的一級網(wǎng)格，就把它放到二級或三級網(wǎng)格中， 每個圖形只在一個級別的網(wǎng)格中存在。在查詢時需要分別查詢所有級別的網(wǎng)格。4.2每個圖形所占網(wǎng)格的計(jì)算會造成很大的性能損失。如“圖3償失，主要