网格索引在ARX开发中的使用

网格索引在ARX开发中的使用简介网格索引是GIS软件中经常使用的一种简单、高效的空间索引技术，例如著名的ESRI公司的ArcSDE空间数据库系统就是采用了这种索引技术。其原理非常简单，如“图1”所示，有6条直线段，被划分成了16(4x4)个网格，线段1到6分别占用了5（包括A3和B2）、2、1、3、2、2个网格。其中B2网格同时被线段1、2、3占用，B3网格同时被线段线段1、2占用。现在假设要对这6条线段两两求交，对于线段1来说，只有线段2、3和它有共用网格现象，所以只需和线段2、3进行计算，同理线段2只需和线段3计算即可，总共计算3次。而如果不采用索引技术，需要计算5+4+3+2=14次。图1而这仅仅是只有6条线段时的情况，其中的差别可想而知。在ARX中使用网格索引分析网格索引技术，核心思想是把整个图形区域划分成MxN个矩形网格，每个网格都是一个数组，记录所有从中穿过的图形。针对“图1”的情况，需要定义4X4=16个数组D[4][4]，保存数据后，D[1][C]、D[1][D]中都保存了线段6，D[2][A]中保存了线段1，D[2][B]中保存了线段1、2、3，D[2][C]中保存了线段5，D[2][D]中保存了线段4，等等。那么，在具体实现上，只需定义一个AcArray<AcDbIntArray,AcArrayObjectCopyReallocator<AcDbIntArray>>数组的数组即可，大小初始化为MXN。下面用一个实例进行说明（假设图形都是直线段）。2.1创建索引#defineGRID_XCOUNT100 //横向划分100个网格#defineGRID_YCOUNT100 //纵向划分100个网格voidCreateSpatialIndex(constAcDbVoidPtrArray&lines,AcArray<AcDbIntArray,CArrayObjectCopyReallocator<AcDbIntArray>>&gridToGeo, //返回空间索引 AcGePoint2dArray&ptLBs, //返回每个图形的左下角AcGePoint2dArray&ptRTs, //返回每个图形的右上角 AcGePoint2d&ptBase, //返回所有图形的左下角AcGeVector2d&gridSize //返回网格横、纵向尺寸 ){ constAcDbLine*pLine; AcGePoint2dptLB,ptRT; inti,nCount=lines.length(); //计算每个图形的左下角、右上角坐标和全部图形的左下角、右上角坐标 GetExtents(lines,ptLBs,ptRTs,ptBase,ptRT); //每个网格的横向和纵向尺寸（加1是处理精度问题） gridSize.x=(ptRT.x-ptBase.x)/GRID_XCOUNT+1; gridSize.y=(ptRT.y-ptBase.y)/GRID_YCOUNT+1; //初始化空间索引数组的内存 gridToGeo.setLogicalLength(GRID_XCOUNT*GRID_YCOUNT); //创建索引 intnGridXMin,nGridXMax,nGridYMin,nGridYMax; for(i=0;i<nCount;i++) { //计算每个图形占用的网格（根据外包矩形简化处理） 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; //在计算出的每个网格数组中添加当前图形的索引for(intj=nGridYMin;j<=nGridYMax;j++) { for(intk=nGridXMin;k<=nGridXMax;k++) { gridToGeo[j*GRID_XCOUNT+k].append(i); } } }}使用索引voidTestWithSpatialIndex(constAcDbVoidPtrArray&lines){ AcArray<AcDbIntArray,AcArrayObjectCopyReallocator<AcDbIntArray>>gridToGeo; //索引 AcGePoint2dptBase; //图形范围左下角 AcGeVector2dgridSize; //网格尺寸 AcGePoint2dArrayptLBs,ptRTs; //每个图形的左下角，右上角坐标 //创建空间索引 CreateSpatialIndex(lines,gridToGeo,ptLBs,ptRTs,ptBase,gridSize); AcGePoint3dArrayresults; constAcDbLine*pLine1,*pLine2; intnGridXMin,nGridXMax,nGridYMin,nGridYMax,nIndex,nMaskBufferSize; //创建一个映射区标记计算过的图形（因为一个图形可能会被添加到多个网格中），每个图形占用1位。 nMaskBufferSize=(lines.length()+7)/8; BYTE*pMask=newBYTE[nMaskBufferSize]; //两两求交 for(inti=0;i<lines.length();i++) { pLine1=(constAcDbLine*)lines.at(i); memset(pMask,0,nMaskBufferSize); //映射区清零 //计算当前图形占用的网格（根据外包矩形简化处理） 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; //遍历占用的所有网格，和其中的图形求交 for(intj=nGridYMin;j<=nGridYMax;j++) { for(intk=nGridXMin;k<=nGridXMax;k++) { //遍历一个网格中的所有图形 for(intm=0;m<gridToGeo[j*GRID_XCOUNT+k].length();m++) { nIndex=gridToGeo[j*GRID_XCOUNT+k].at(m); if(nIndex<=i) { continue; //已经计算过了 } if((pMask[nIndex/8]&(1<<(nIndex%8)))!=0) { continue; //标记位已设，已经计算过了 } //设标记位 pMask[nIndex/8]|=(1<<(nIndex%8)); if((ptLBs[i].x>ptRTs[nIndex].x)|| (ptLBs[i].y>ptRTs[nIndex].y)|| (ptRTs[i].x<ptLBs[nIndex].x)|| (ptRTs[i].y<ptLBs[nIndex].y)) { continue;//两者外包矩形不相交 } pLine2=(constAcDbLine*)lines.at(nIndex); results.setLogicalLength(0); pLine1->intersectWith(pLine2,AcDb::kOnBothOperands,results); } } } } delete[]pMask;}性能对比通过在一定范围内随机生成线段（限定长度在一定范围），对未采用空间索引和采用网格空间索引两种计算方法的性能进行对比，结果如下：图2随机生成的图形图形数（万）未采用索引耗时(秒)采用网格索引耗时(秒)11.970.0328.340.06326.450.14450.280.50582.270.7710--1.30可以发现，两者性能相差可达几十倍到100多倍，对于多于2万个图形的情况，采用网格索引后效果非常明显。对比代码：voidTestNoSpatialIndex(constAcDbVoidPtrArray&lines){ intnCount=lines.length(); constAcDbLine*pLine1,*pLine2; AcGePoint2dArrayptLBs,ptRTs; AcGePoint2dextentLB,extentRT; GetExtents(lines,ptLBs,ptRTs,extentLB,extentRT); AcGePoint3dArrayresults; //两两求交 for(inti=0;i<nCount;i++) { pLine1=(constAcDbLine*)lines.at(i); for(intj=i+1;j<nCount;j++) { pLine2=(constAcDbLine*)lines.at(j); if((ptLBs.at(i).x>ptRTs.at(j).x)|| (ptLBs.at(i).y>ptRTs.at(j).y)|| (ptRTs.at(i).x<ptLBs.at(j).x)|| (ptRTs.at(i).y<ptLBs.at(j).y)) { continue;//两者外包矩形不相交 } results.setLogicalLength(0); pLine1->intersectWith(pLine2,AcDb::kOnBothOperands,results); } }}进一步优化从上一节中的性能对比表可以看到，图形数从1万升到10万时，采用网格索引时的耗时也升高了43倍，这是非常不利的现象。这是因为第2节中的示例代码过于简化所致，这个问题可以通过以下几个环节进行优化处理。4.1网格尺寸和数目的确定在示例中，网格的数目是固定的，网格尺寸是从空间范围和网格数目倒推出来的，优化的做法应该是根据多数图形的尺寸确定网格尺寸，尽量使多数图形的尺寸和网格尺寸相近。也就是说，网格尺寸过大或过小都不合适。可以假设一下，如果网格尺寸很大，所有图形都落在几个网格内，索引就失去了意义；而如果网格尺寸很小，会造成每个图形都占用大量的网格，重复数据增多，内存占用增大，显然也是不合适的。4.2采用多级网格如果图形尺寸相差很大，采用一级网格时网格尺寸就很难确定，这时可以采用多级网格，各级之间的网格尺寸大小最好相差5倍以上。例如一级网格尺寸为2mx5m，二级网格就可以定为20mx30m，三级网格可以设为200mx500m等，具体识该级别的图形尺寸而定，有些情况下，各级之间可以相差上百倍。在使用时，如果一个图形需要占用非常多的一级网格，就把它放到二级或三级网格中，每个图形只在一个级别的网格