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

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

3、dArray &ptRTs, 返回每個(gè)圖形的右上角AcGePoint2d &ptBase,返回所有圖形的左下角AcGeVector2d &gridSize返回網(wǎng)格橫、縱向尺寸）const AcDbLine* pLine;AcGePoint2d ptLB,ptRT; int i,nCount = lines.length();計(jì)算每個(gè)圖形的左下角、右上角坐標(biāo)和全部圖形的左下角、右上角坐標(biāo) GetExtents(lines, ptLBs, ptRTs, ptBase, ptRT);每個(gè)網(wǎng)格的橫向和縱向尺寸(加1是處理精度問(wèn)題)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ì)算每個(gè)圖形占用的網(wǎng)格(根據(jù)外包矩形簡(jiǎn)化處理)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ì)算出的每個(gè)網(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; /每個(gè)圖形的左下角，右上角坐標(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)建一個(gè)映射區(qū)標(biāo)記計(jì)算過(guò)的圖形(因?yàn)橐粋€(gè)圖形可能會(huì)被添加到多個(gè)網(wǎng)格中)，每個(gè)圖形占 用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ù)外包矩形簡(jiǎn)化處理)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+)/遍歷一個(gè)網(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ì)算過(guò)了if( (pMasknIndex/8 & (1(nIndex%8) != 0 )continue;標(biāo)記位已設(shè)，已經(jīng)計(jì)算過(guò)了設(shè)標(biāo)記位pMasknIndex/8 |= (1 ptRTsnIndex.x) |i.y

10、ptRTsnIndex.y)i.x ptLBsnIndex.x).y intersectWith(pLine2,AcDb:kOnBothOperands, delete pMask; 性能對(duì)比通過(guò)在一定范圍內(nèi)隨機(jī)生成線段（限定長(zhǎng)度在一定范圍），對(duì)未采用空間索引和采用網(wǎng)格空間索引兩種計(jì)算方法的性能進(jìn)行對(duì)比，結(jié)果如下：篤. . -八注-.“時(shí)Jj/|E：七 /崢 * #圖形數(shù)（萬(wàn)）未采用索 引耗時(shí)（秒）采用網(wǎng)格索 引耗時(shí)（秒）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多倍，對(duì)于多于2萬(wàn)個(gè)圖形的情況，采用網(wǎng)格索引后效果非常明顯。對(duì)比代碼：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é)中的性能對(duì)比表可以看到，圖形數(shù)從1萬(wàn)升到10萬(wàn)時(shí)，采用網(wǎng)格索引時(shí)的耗時(shí)也升高了 43倍，這是非常不利的現(xiàn)象。這是因?yàn)榈?節(jié)中的示例代碼過(guò)

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