RTree源代码——C语言实现

RTree源代码——C语言实现

cheungmine

一、什么是RTree

“R树是B树向多维空间发展的另一种形式，它将空间对象按范围划分，每个结点都对应一个区域和一个磁盘页，非叶结点的磁盘页中存储其所有子结点的区域范围，非叶结点的所有子结点的区域都落在它的区域范围之内；叶结点的磁盘页中存储其区域范围之内的所有空间对象的外接矩形。每个结点所能拥有的子结点数目有上、下限，下限保证对磁盘空间的有效利用，上限保证每个结点对应一个磁盘页，当插入新的结点导致某结点要求的空间大于一个磁盘页时，该结点一分为二。R树是一种动态索引结构，即：它的查询可与插入或删除同时进行，而且不需要定期地对树结构进行重新组织。当更新一个关系并且在这个关系上正在做扫描时，如果更新影响到了扫描操作的任何一个页，我们需要检查扫描并且修复它。”

其实上面的话，你也不用多做研究。理解RTree是范围树，适合做空间索引（快速查找）。更多的关于RTree的知识我也没时间写在这里，我只知道原理，然后提供了下面的代码（经过我修改，看起来更顺眼些）。一定要用它。感谢算法的原作者和发明算法的人。“帝国大厦的建立，人才更在资本之上”啊！

二、RTree的实现代码

本文的代码来源于GRASS，我根据自己的习惯，作了适当的修改，把原来多个文件合成了2个文件（rtree.h和rtree.c）。本文提供了完整的rtree实现代码和一个简单的测试代码（test.c）。如果你发现什么问题，请及时提交评论，以利改正。

RTree.h文件：

/****************************************************************************
*RTree.H
*
*MODULE:R-Treelibrary
*
*AUTHOR(S):AntoninGuttman-originalcode
*DanielGreen([e-mail])-majorclean-up
*andimplementationofboundingspheres
*
*PURPOSE:MultiDimensionalIndex
*
*COPYRIGHT:(C)2001bytheGRASSDevelopmentTeam
*
*ThisprogramisfreesoftwareundertheGNUGeneralPublic
*License(>=v2).ReadthefileCOPYINGthatcomeswithGRASS
*fordetails.
*
*LASTMODIFY:ZhangLiang([e-mail])-2007-11
*****************************************************************************/
#ifndefRTREE_H_INCLUDED
#defineRTREE_H_INCLUDED

/*PAGE_SIZEisnormallythenaturalpagesizeofthemachine*/
#definePAGE_SIZE512
#defineDIMS_NUMB3/*numberofdimensions*/
#defineSIDES_NUMB2*DIMS_NUMB

/*typedeffloatREALTYPE;*/
typedefdoubleREALTYPE;


#ifndefTRUE
#defineTRUE1
#defineFALSE0
#endif


typedefstruct_RTREEMBR
{
REALTYPEbound[SIDES_NUMB];/*xmin,ymin,...,xmax,ymax,...*/
}RTREEMBR;

typedefstruct_RTREEBRANCH
{
RTREEMBRmbr;
struct_RTREENODE*child;/*mbrid*/
}RTREEBRANCH;

/*maxbranchingfactorofanode*/
#defineMAXCARD(int)((PAGE_SIZE-(2*sizeof(int)))/sizeof(RTREEBRANCH))

typedefstruct_RTREENODE
{
intcount;
intlevel;/*0isleaf,otherspositive*/
RTREEBRANCHbranch[MAXCARD];
}RTREENODE;

typedefstruct_RTREELISTNODE
{
struct_RTREELISTNODE*next;
RTREENODE*node;
}RTREELISTNODE;

/*
*Ifpassedtoatreesearch,thiscallbackfunctionwillbecalled
*withtheIDofeachdatambrthatoverlapsthesearchmbr
*pluswhateveruserspecificpointerwaspassedtothesearch.
*Itcanterminatethesearchearlybyreturning0inwhichcase
*thesearchwillreturnthenumberofhitsfounduptothatpoint.
*/
typedefint(*pfnSearchHitCallback)(intid,void*pfnParam);


intRTreeSetNodeMax(intnew_max);

intRTreeSetLeafMax(intnew_max);

intRTreeGetNodeMax(void);

intRTreeGetLeafMax(void);

/**
*Initializearectangletohaveall0coordinates.
*/
voidRTreeInitRect(RTREEMBR*rc);

/**
*Returnambrwhosefirstlowsideishigherthanitsoppositeside-
*interpretedasanundefinedmbr.
*/
RTREEMBRRTreeNullRect(void);


/**
*Printoutthedataforarectangle.
*/
voidRTreePrintRect(RTREEMBR*rc,intdepth);

/**
*Calculatethe2-dimensionalareaofarectangle
*/
REALTYPERTreeRectArea(RTREEMBR*rc);

/**
*Calculatethen-dimensionalvolumeofarectangle
*/
REALTYPERTreeRectVolume(RTREEMBR*rc);


/**
*Calculatethen-dimensionalvolumeoftheboundingsphereofarectangle
*TheexactvolumeoftheboundingsphereforthegivenRTREEMBR.
*/
REALTYPERTreeRectSphericalVolume(RTREEMBR*rc);


/**
*Calculatethen-dimensionalsurfaceareaofarectangle
*/
REALTYPERTreeRectSurfaceArea(RTREEMBR*rc);


/**
*Combinetworectangles,makeonethatincludesboth.
*/
RTREEMBRRTreeCombineRect(RTREEMBR*rc1,RTREEMBR*rc2);


/**
*Decidewhethertworectanglesoverlap.
*/
intRTreeOverlap(RTREEMBR*rc1,RTREEMBR*rc2);


/**
*Decidewhetherrectangleriscontainedinrectangles.
*/
intRTreeContained(RTREEMBR*r,RTREEMBR*s);

/**
*Splitanode.
*Dividesthenodesbranchesandtheextraonebetweentwonodes.
*Oldnodeisoneofthenewones,andonereallynewoneiscreated.
*Triesmorethanonemethodforchoosingapartition,usesbestresult.
*/
voidRTreeSplitNode(RTREENODE*node,RTREEBRANCH*br,RTREENODE**new_node);

/**
*InitializeaRTREENODEstructure.
*/
voidRTreeInitNode(RTREENODE*node);

/**
*Makeanewnodeandinitializetohaveallbranchcellsempty.
*/
RTREENODE*RTreeNewNode(void);

voidRTreeFreeNode(RTREENODE*node);


/**
*Printoutthedatainanode.
*/
voidRTreePrintNode(RTREENODE*node,intdepth);


/**
*Findthesmallestrectanglethatincludesallrectanglesinbranchesofanode.
*/
RTREEMBRRTreeNodeCover(RTREENODE*node);


/**
*Pickabranch.Picktheonethatwillneedthesmallestincrease
*inareatoaccomodatethenewrectangle.Thiswillresultinthe
*leasttotalareaforthecoveringrectanglesinthecurrentnode.
*Incaseofatie,picktheonewhichwassmallerbefore,toget
*thebestresolutionwhensearching.
*/
intRTreePickBranch(RTREEMBR*rc,RTREENODE*node);


/**
*Addabranchtoanode.Splitthenodeifnecessary.
*Returns0ifnodenotsplit.Oldnodeupdated.
*Returns1ifnodesplit,sets*new_nodetoaddressofnewnode.
*Oldnodeupdated,becomesoneoftwo.
*/
intRTreeAddBranch(RTREEBRANCH*br,RTREENODE*node,RTREENODE**new_node);


/**
*Disconnectadependentnode.
*/
voidRTreeDisconnectBranch(RTREENODE*node,inti);


/**
*Destroy(free)noderecursively.
*/
voidRTreeDestroyNode(RTREENODE*node);


/**
*Createanewrtreeindex,empty.Consistsofasinglenode.
*/
RTREENODE*RTreeCreate(void);


/**
*Destroyartreerootmustbearootofrtree.Freeallmemory.
*/
voidRTreeDestroy(RTREENODE*root);


/**
*Searchinanindextreeorsubtreeforalldatarectanglesthatoverlaptheargumentrectangle.
*Returnthenumberofqualifyingdatarects.
*/
intRTreeSearch(RTREENODE*node,RTREEMBR*rc,pfnSearchHitCallbackpfnSHCB,void*pfnParam);

/**
*Insertadatarectangleintoanindexstructure.
*RTreeInsertRectprovidesforsplittingtheroot;
*returns1ifrootwassplit,0ifitwasnot.
*Thelevelargumentspecifiesthenumberofstepsupfromtheleaf
*leveltoinsert;e.g.adatarectanglegoesinatlevel=0.
*_RTreeInsertRectdoestherecursion.
*/
intRTreeInsertRect(RTREEMBR*rc,inttid,RTREENODE**root,intlevel);

/**
*Deleteadatarectanglefromanindexstructure.
*PassinapointertoaRTREEMBR,thetidoftherecord,ptrtoptrtorootnode.
*Returns1ifrecordnotfound,0ifsuccess.
*RTreeDeleteRectprovidesforeliminatingtheroot.
*/
intRTreeDeleteRect(RTREEMBR*rc,inttid,RTREENODE**root);

#endif/*RTREE_H_INCLUDED*/

RTree.C文件：

/****************************************************************************
*RTree.C
*
*MODULE:R-Treelibrary
*
*AUTHOR(S):AntoninGuttman-originalcode
*DanielGreen([e-mail])-majorclean-up
*andimplementationofboundingspheres
*
*PURPOSE:MultiDimensionalIndex
*
*COPYRIGHT:(C)2001bytheGRASSDevelopmentTeam
*
*ThisprogramisfreesoftwareundertheGNUGeneralPublic
*License(>=v2).ReadthefileCOPYINGthatcomeswithGRASS
*fordetails.
*
*LASTMODIFY:ZhangLiang([e-mail])-2007-11
*****************************************************************************/

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<float.h>
#include<math.h>

#include"rtree.h"

#defineMETHODS1

/*variablesforfindingapartition*/
typedefstruct_RTREEPARTITION
{
intpartition[MAXCARD+1];
inttotal;
intminfill;
inttaken[MAXCARD+1];
intcount[2];
RTREEMBRcover[2];
REALTYPEarea[2];
}RTREEPARTITION;

RTREEBRANCHBranchBuf[MAXCARD+1];
intBranchCount;
RTREEMBRCoverSplit;
REALTYPECoverSplitArea;
RTREEPARTITIONPartitions[METHODS];


#defineBIG_NUM(FLT_MAX/4.0)

#defineINVALID_RECT(x)((x)->bound[0]>(x)->bound[DIMS_NUMB])
#defineMIN(a,b)((a)<(b)?(a):(b))
#defineMAX(a,b)((a)>(b)?(a):(b))

intNODECARD=MAXCARD;
intLEAFCARD=MAXCARD;

/*balancecriteriafornodesplitting*/
/*NOTE:canbechangedifneeded.*/
#defineMINNODEFILL(NODECARD/2)
#defineMINLEAFFILL(LEAFCARD/2)

#defineMAXKIDS(n)((n)->level>0?NODECARD:LEAFCARD)
#defineMINFILL(n)((n)->level>0?MINNODEFILL:MINLEAFFILL)

staticintset_max(int*which,intnew_max)
{
if(2>new_max||new_max>MAXCARD)
return0;
*which=new_max;
return1;
}


/**
*Loadbranchbufferwithbranchesfromfullnodeplustheextrabranch.
*/
staticvoid_RTreeGetBranches(RTREENODE*node,RTREEBRANCH*br)
{
inti;

assert(node&&br);

/*loadthebranchbuffer*/
for(i=0;i<MAXKIDS(node);i++)
{
assert(node->branch[i].child);/*nshouldhaveeveryentryfull*/
BranchBuf[i]=node->branch[i];
}

BranchBuf[MAXKIDS(node)]=*br;
BranchCount=MAXKIDS(node)+1;

/*calculatembrcontainingallintheset*/
CoverSplit=BranchBuf[0].mbr;

for(i=1;i<MAXKIDS(node)+1;i++)
{
CoverSplit=RTreeCombineRect(&CoverSplit,&BranchBuf[i].mbr);
}

CoverSplitArea=RTreeRectSphericalVolume(&CoverSplit);
RTreeInitNode(node);
}



/**
*Putabranchinoneofthegroups.
*/
staticvoid_RTreeClassify(inti,intgroup,RTREEPARTITION*p)
{
assert(p);
assert(!p->taken[i]);

p->partition[i]=group;
p->taken[i]=TRUE;

if(p->count[group]==0)
p->cover[group]=BranchBuf[i].mbr;
else
p->cover[group]=RTreeCombineRect(&BranchBuf[i].mbr,&p->cover[group]);

p->area[group]=RTreeRectSphericalVolume(&p->cover[group]);
p->count[group]++;
}

/**
*Picktworectsfromsettobethefirstelementsofthetwogroups.
*Pickthetwothatwastethemostareaifcoveredbyasinglerectangle.
*/
staticvoid_RTreePickSeeds(RTREEPARTITION*p)
{
inti,j,seed0=0,seed1=0;
REALTYPEworst,waste,area[MAXCARD+1];

for(i=0;i<p->total;i++)
area[i]=RTreeRectSphericalVolume(&BranchBuf[i].mbr);

worst=-CoverSplitArea-1;

for(i=0;i<p->total-1;i++)
{
for(j=i+1;j<p->total;j++)
{
RTREEMBRone_rect;
one_rect=RTreeCombineRect(&BranchBuf[i].mbr,&BranchBuf[j].mbr);
waste=RTreeRectSphericalVolume(&one_rect)-area[i]-area[j];
if(waste>worst)
{
worst=waste;
seed0=i;
seed1=j;
}
}
}
_RTreeClassify(seed0,0,p);
_RTreeClassify(seed1,1,p);
}


/**
*Copybranchesfromthebufferintotwonodesaccordingtothepartition.
*/
staticvoid_RTreeLoadNodes(RTREENODE*n,RTREENODE*q,RTREEPARTITION*p)
{
inti;
assert(n&&q&&p);

for(i=0;i<p->total;i++)
{
assert(p->partition[i]==0||p->partition[i]==1);
if(p->partition[i]==0)
RTreeAddBranch(&BranchBuf[i],n,NULL);
elseif(p->partition[i]==1)
RTreeAddBranch(&BranchBuf[i],q,NULL);
}
}

/**
*InitializeaRTREEPARTITIONstructure.
*/
staticvoid_RTreeInitPart(RTREEPARTITION*p,intmaxrects,intminfill)
{
inti;
assert(p);

p->count[0]=p->count[1]=0;
p->cover[0]=p->cover[1]=RTreeNullRect();
p->area[0]=p->area[1]=(REALTYPE)0;
p->total=maxrects;
p->minfill=minfill;
for(i=0;i<maxrects;i++)
{
p->taken[i]=FALSE;
p->partition[i]=-1;
}
}


/**
*PrintoutdataforapartitionfromRTREEPARTITIONstruct.
*/
staticvoid_RTreePrintPart(RTREEPARTITION*p)
{
inti;
assert(p);

fprintf(stdout," partition: ");
for(i=0;i<p->total;i++)
{
fprintf(stdout,"%3d ",i);
}
fprintf(stdout," ");
for(i=0;i<p->total;i++)
{
if(p->taken[i])
fprintf(stdout,"t ");
else
fprintf(stdout," ");
}
fprintf(stdout," ");
for(i=0;i<p->total;i++)
{
fprintf(stdout,"%3d ",p->partition[i]);
}
fprintf(stdout," ");

fprintf(stdout,"count[0]=%darea=%f ",p->count[0],p->area[0]);
fprintf(stdout,"count[1]=%darea=%f ",p->count[1],p->area[1]);
if(p->area[0]+p->area[1]>0)
{
fprintf(stdout,"totalarea=%feffectiveness=%3.2f ",
p->area[0]+p->area[1],(float)CoverSplitArea/(p->area[0]+p->area[1]));
}
fprintf(stdout,"cover[0]: ");
RTreePrintRect(&p->cover[0],0);

fprintf(stdout,"cover[1]: ");
RTreePrintRect(&p->cover[1],0);
}


/**
*Method#0forchoosingapartition:
*Astheseedsforthetwogroups,pickthetworectsthatwouldwastethe
*mostareaifcoveredbyasinglerectangle,i.e.evidentlytheworstpair
*tohaveinthesamegroup.
*Oftheremaining,oneatatimeischosentobeputinoneofthetwogroups.
*Theonechosenistheonewiththegreatestdifferenceinareaexpansion
*dependingonwhichgroup-thembrmoststronglyattractedtoonegroup
*andrepelledfromtheother.
*Ifonegroupgetstoofull(morewouldforceothergrouptoviolatemin
*fillrequirement)thenothergroupgetstherest.
*Theselastaretheonesthatcangoineithergroupmosteasily.
*/
staticvoid_RTreeMethodZero(RTREEPARTITION*p,intminfill)
{
inti;
REALTYPEbiggestDiff;
intgroup,chosen=0,betterGroup=0;
assert(p);

_RTreeInitPart(p,BranchCount,minfill);
_RTreePickSeeds(p);

while(p->count[0]+p->count[1]<p->total&&
p->count[0]<p->total-p->minfill&&
p->count[1]<p->total-p->minfill)
{
biggestDiff=(REALTYPE)-1.;
for(i=0;i<p->total;i++)
{
if(!p->taken[i])
{
RTREEMBR*r,rect_0,rect_1;
REALTYPEgrowth0,growth1,diff;

r=&BranchBuf[i].mbr;
rect_0=RTreeCombineRect(r,&p->cover[0]);
rect_1=RTreeCombineRect(r,&p->cover[1]);
growth0=RTreeRectSphericalVolume(&rect_0)-p->area[0];
growth1=RTreeRectSphericalVolume(&rect_1)-p->area[1];
diff=growth1-growth0;
if(diff>=0)
group=0;
else
{
group=1;
diff=-diff;
}
if(diff>biggestDiff)
{
biggestDiff=diff;
chosen=i;
betterGroup=group;
}
elseif(diff==biggestDiff&&p->count[group]<p->count[betterGroup])
{
chosen=i;
betterGroup=group;
}
}
}
_RTreeClassify(chosen,betterGroup,p);
}

/*ifonegrouptoofull,putremainingrectsintheother*/
if(p->count[0]+p->count[1]<p->total)
{
if(p->count[0]>=p->total-p->minfill)
group=1;
else
group=0;

for(i=0;i<p->total;i++)
{
if(!p->taken[i])
_RTreeClassify(i,group,p);
}
}

assert(p->count[0]+p->count[1]==p->total);
assert(p->count[0]>=p->minfill&&p->count[1]>=p->minfill);
}


/**
*Initializeonebranchcellinanode.
*/
staticvoid_RTreeInitBranch(RTREEBRANCH*br)
{
RTreeInitRect(&(br->mbr));
br->child=NULL;
}


staticvoid_RTreePrintBranch(RTREEBRANCH*br,intdepth)
{
RTreePrintRect(&(br->mbr),depth);
RTreePrintNode(br->child,depth);
}


/**
*Insertsanewdatarectangleintotheindexstructure.
*Recursivelydescendstree,propagatessplitsbackup.
*Returns0ifnodewasnotsplit.Oldnodeupdated.
*Ifnodewassplit,returns1andsetsthepointerpointedtoby
*new_nodetopointtothenewnode.Oldnodeupdatedtobecomeoneoftwo.
*Thelevelargumentspecifiesthenumberofstepsupfromtheleaf
*leveltoinsert;e.g.adatarectanglegoesinatlevel=0.
*/
staticint_RTreeInsertRect(RTREEMBR*rc,inttid,RTREENODE*node,RTREENODE**new_node,intlevel)
{
inti;
RTREEBRANCHb;
RTREENODE*n2;

assert(rc&&node&&new_node);
assert(level>=0&&level<=node->level);

/*Stillabovelevelforinsertion,godowntreerecursively*/
if(node->level>level)
{
i=RTreePickBranch(rc,node);
if(!_RTreeInsertRect(rc,tid,node->branch[i].child,&n2,level))
{
/*childwasnotsplit*/
node->branch[i].mbr=RTreeCombineRect(rc,&(node->branch[i].mbr));
return0;
}

/*childwassplit*/
node->branch[i].mbr=RTreeNodeCover(node->branch[i].child);
b.child=n2;
b.mbr=RTreeNodeCover(n2);

returnRTreeAddBranch(&b,node,new_node);
}
elseif(node->level==level)/*Havereachedlevelforinsertion.Addmbr,splitifnecessary*/
{
b.mbr=*rc;

#pragmawarning(push)/*C4312*/
#pragmawarning(disable:4312)
b.child=(RTREENODE*)tid;
#pragmawarning(pop)

/*childfieldofleavescontainstidofdatarecord*/
returnRTreeAddBranch(&b,node,new_node);
}

/*Notsupposedtohappen*/
assert(FALSE);
return0;
}


/**
*AllocatespaceforanodeinthelistusedinDeletRectto
*storeNodesthataretooempty.
*/
staticRTREELISTNODE*_RTreeNewListNode(void)
{
return(RTREELISTNODE*)malloc(sizeof(RTREELISTNODE));
}

staticvoid_RTreeFreeListNode(RTREELISTNODE*p)
{
free(p);
}

/**
*Addanodetothereinsertionlist.Allitsbrancheswilllater
*bereinsertedintotheindexstructure.
*/
staticvoid_RTreeReInsert(RTREENODE*node,RTREELISTNODE**ne)
{
RTREELISTNODE*ln=_RTreeNewListNode();
ln->node=node;
ln->next=*ne;
*ne=ln;
}

/**
*Deletearectanglefromnon-rootpartofanindexstructure.
*CalledbyRTreeDeleteRect.Descendstreerecursively,
*mergesbranchesonthewaybackup.
*Returns1ifrecordnotfound,0ifsuccess.
*/
staticint_RTreeDeleteRect(RTREEMBR*rc,inttid,RTREENODE*node,RTREELISTNODE**ee)
{
inti;

assert(rc&&node&&ee);
assert(tid>=0);
assert(node->level>=0);

if(node->level>0)/*notaleafnode*/
{
for(i=0;i<NODECARD;i++)
{
if(node->branch[i].child&&RTreeOverlap(rc,&(node->branch[i].mbr)))
{
if(!_RTreeDeleteRect(rc,tid,node->branch[i].child,ee))
{
if(node->branch[i].child->count>=MINNODEFILL)
node->branch[i].mbr=RTreeNodeCover(node->branch[i].child);
else{/*notenoughentriesinchild,eliminatechildnode*/
_RTreeReInsert(node->branch[i].child,ee);
RTreeDisconnectBranch(node,i);
}
return0;
}
}
}
return1;
}

#pragmawarning(push)/*C4312*/
#pragmawarning(disable:4312)

/*aleafnode*/
for(i=0;i<LEAFCARD;i++)
{
if(node->branch[i].child&&node->branch[i].child==(RTREENODE*)tid)
{
RTreeDisconnectBranch(node,i);
return0;
}

}
#pragmawarning(pop)

return1;
}

staticvoid_RTreeTabIn(intdepth)
{
inti;
for(i=0;i<depth;i++)
putchar(' ');
}

/*=============================================================================
Publicfunctions:
=============================================================================*/

intRTreeSetNodeMax(intnew_max){returnset_max(&NODECARD,new_max);}
intRTreeSetLeafMax(intnew_max){returnset_max(&LEAFCARD,new_max);}
intRTreeGetNodeMax(void){returnNODECARD;}
intRTreeGetLeafMax(void){returnLEAFCARD;}

/**
*Initializearectangletohaveall0coordinates.
*/
voidRTreeInitRect(RTREEMBR*rc)
{
inti;
for(i=0;i<SIDES_NUMB;i++)
rc->bound[i]=(REALTYPE)0;
}


/**
*Returnambrwhosefirstlowsideishigherthanitsoppositeside-
*interpretedasanundefinedmbr.
*/
RTREEMBRRTreeNullRect(void)
{
RTREEMBRrc;
inti;

rc.bound[0]=(REALTYPE)1;
rc.bound[DIMS_NUMB]=(REALTYPE)-1;
for(i=1;i<DIMS_NUMB;i++)
rc.bound[i]=rc.bound[i+DIMS_NUMB]=(REALTYPE)0;
returnrc;
}

/**
*Printoutthedataforarectangle.
*/
voidRTreePrintRect(RTREEMBR*rc,intdepth)
{
inti;

_RTreeTabIn(depth);
fprintf(stdout,"mbr: ");
for(i=0;i<DIMS_NUMB;i++)
{
_RTreeTabIn(depth+1);
fprintf(stdout,"%f %f ",rc->bound[i],rc->bound[i+DIMS_NUMB]);
}
}

/**
*Calculatethe2-dimensionalareaofarectangle
*/
REALTYPERTreeRectArea(RTREEMBR*rc)
{
if(INVALID_RECT(rc))
return(REALTYPE)0;

return(rc->bound[DIMS_NUMB]-rc->bound[0])*(rc->bound[DIMS_NUMB+1]-rc->bound[1]);
}


/**
*Calculatethen-dimensionalvolumeofarectangle
*/
REALTYPERTreeRectVolume(RTREEMBR*rc)
{
inti;
REALTYPEvol=(REALTYPE)1;

if(INVALID_RECT(rc))
return(REALTYPE)0;

for(i=0;i<DIMS_NUMB;i++)
vol*=(rc->bound[i+DIMS_NUMB]-rc->bound[i]);
assert(vol>=0.0);
returnvol;
}


/**
*Precomputedvolumesoftheunitspheresforthefirstfewdimensions
*/
constdoubleUnitSphereVolumes[]={
0.000000,/*dimension0*/
2.000000,/*dimension1*/
3.141593,/*dimension2*/
4.188790,/*dimension3*/
4.934802,/*dimension4*/
5.263789,/*dimension5*/
5.167713,/*dimension6*/
4.724766,/*dimension7*/
4.058712,/*dimension8*/
3.298509,/*dimension9*/
2.550164,/*dimension10*/
1.884104,/*dimension11*/
1.335263,/*dimension12*/
0.910629,/*dimension13*/
0.599265,/*dimension14*/
0.381443,/*dimension15*/
0.235331,/*dimension16*/
0.140981,/*dimension17*/
0.082146,/*dimension18*/
0.046622,/*dimension19*/
0.025807,/*dimension20*/
};

#ifDIMS_NUMB>20
#error"notenoughprecomputedspherevolumes"
#endif

#defineUnitSphereVolumeUnitSphereVolumes[DIMS_NUMB]

/**
*Calculatethen-dimensionalvolumeoftheboundingsphereofarectangle.
*TheexactvolumeoftheboundingsphereforthegivenRTREEMBR.
*/
REALTYPERTreeRectSphericalVolume(RTREEMBR*rc)
{
inti;
doublesum_of_squares=0,radius;

if(INVALID_RECT(rc))
return(REALTYPE)0;

for(i=0;i<DIMS_NUMB;i++){
doublehalf_extent=(rc->bound[i+DIMS_NUMB]-rc->bound[i])/2;
sum_of_squares+=half_extent*half_extent;
}
radius=sqrt(sum_of_squares);
return(REALTYPE)(pow(radius,DIMS_NUMB)*UnitSphereVolume);
}


/**
*Calculatethen-dimensionalsurfaceareaofarectangle
*/
REALTYPERTreeRectSurfaceArea(RTREEMBR*rc)
{
inti,j;
REALTYPEsum=(REALTYPE)0;

if(INVALID_RECT(rc))
return(REALTYPE)0;

for(i=0;i<DIMS_NUMB;i++){
REALTYPEface_area=(REALTYPE)1;
for(j=0;j<DIMS_NUMB;j++)
/*excludeiextentfromproductinthisdimension*/
if(i!=j){
REALTYPEj_extent=rc->bound[j+DIMS_NUMB]-rc->bound[j];
face_area*=j_extent;
}
sum+=face_area;
}
return2*sum;
}



/**
*Combinetworectangles,makeonethatincludesboth.
*/
RTREEMBRRTreeCombineRect(RTREEMBR*rc1,RTREEMBR*rc2)
{
inti,j;
RTREEMBRnew_rect;

assert(rc1&&rc2);

if(INVALID_RECT(rc1))
return*rc2;

if(INVALID_RECT(rc2))
return*rc1;

for(i=0;i<DIMS_NUMB;i++)
{
new_rect.bound[i]=MIN(rc1->bound[i],rc2->bound[i]);
j=i+DIMS_NUMB;
new_rect.bound[j]=MAX(rc1->bound[j],rc2->bound[j]);
}
returnnew_rect;
}


/**
*Decidewhethertworectanglesoverlap.
*/
intRTreeOverlap(RTREEMBR*rc1,RTREEMBR*rc2)
{
inti,j;
assert(rc1&&rc2);

for(i=0;i<DIMS_NUMB;i++)
{
j=i+DIMS_NUMB;/*indexforhighsides*/

if(rc1->bound[i]>rc2->bound[j]||rc2->bound[i]>rc1->bound[j])
returnFALSE;
}
returnTRUE;
}


/**
*Decidewhetherrectangleriscontainedinrectangles.
*/
intRTreeContained(RTREEMBR*r,RTREEMBR*s)
{
inti,j,result;
assert(r&&s);

/*undefinedmbriscontainedinanyother*/
if(INVALID_RECT(r))
returnTRUE;

/*nombr(exceptanundefinedone)iscontainedinanundefmbr*/
if(INVALID_RECT(s))
returnFALSE;

result=TRUE;
for(i=0;i<DIMS_NUMB;i++)
{
j=i+DIMS_NUMB;/*indexforhighsides*/
result=result&&r->bound[i]>=s->bound[i]&&r->bound[j]<=s->bound[j];
}
returnresult;
}

/**
*Splitanode.
*Dividesthenodesbranchesandtheextraonebetweentwonodes.
*Oldnodeisoneofthenewones,andonereallynewoneiscreated.
*Triesmorethanonemethodforchoosingapartition,usesbestresult.
*/
voidRTreeSplitNode(RTREENODE*node,RTREEBRANCH*br,RTREENODE**new_node)
{
RTREEPARTITION*p;
intlevel;

assert(node&&br);

/*loadallthebranchesintoabuffer,initializeoldnode*/
level=node->level;
_RTreeGetBranches(node,br);

/*findpartition*/
p=&Partitions[0];

/*Note:can'tuseMINFILL(n)belowsincenodewasclearedbyGetBranches()*/
_RTreeMethodZero(p,level>0?MINNODEFILL:MINLEAFFILL);

/*putbranchesfrombufferinto2nodesaccordingtochosenpartition*/
*new_node=RTreeNewNode();
(*new_node)->level=node->level=level;
_RTreeLoadNodes(node,*new_node,p);

assert(node->count+(*new_node)->count==p->total);
}


/**
*InitializeaRTREENODEstructure.
*/
voidRTreeInitNode(RTREENODE*node)
{
inti;
node->count=0;
node->level=-1;
for(i=0;i<MAXCARD;i++)
_RTreeInitBranch(&(node->branch[i]));
}

/**
*Makeanewnodeandinitializetohaveallbranchcellsempty.
*/
RTREENODE*RTreeNewNode(void)
{
RTREENODE*node=(RTREENODE*)malloc(sizeof(RTREENODE));
assert(node);
RTreeInitNode(node);
returnnode;
}

voidRTreeFreeNode(RTREENODE*node)
{
assert(node);
free(node);
}


/**
*Printoutthedatainanode.
*/
voidRTreePrintNode(RTREENODE*node,intdepth)
{
inti;
assert(node);

_RTreeTabIn(depth);
fprintf(stdout,"node");

if(node->level==0)
fprintf(stdout,"LEAF");
elseif(node->level>0)
fprintf(stdout,"NONLEAF");
else
fprintf(stdout,"TYPE=?");

#pragmawarning(push)/*C4311*/
#pragmawarning(disable:4311)
fprintf(stdout,"level=%dcount=%daddress=%o ",node->level,node->count,(unsignedint)node);
#pragmawarning(pop)

for(i=0;i<node->count;i++)
{
if(node->level==0){
/*_RTreeTabIn(depth);*/
/*fprintf(stdout," %d:data=%d ",i,n->branch[i].child);*/
}
else{
_RTreeTabIn(depth);
fprintf(stdout,"branch%d ",i);
_RTreePrintBranch(&node->branch[i],depth+1);
}
}
}

/**
*Findthesmallestrectanglethatincludesallrectanglesinbranchesofanode.
*/
RTREEMBRRTreeNodeCover(RTREENODE*node)
{
inti,first_time=1;
RTREEMBRrc;
assert(node);

RTreeInitRect(&rc);

for(i=0;i<MAXKIDS(node);i++)
{
if(node->branch[i].child)
{
if(first_time)
{
rc=node->branch[i].mbr;
first_time=0;
}
else
rc=RTreeCombineRect(&rc,&(node->branch[i].mbr));
}
}
returnrc;
}

/**
*Pickabranch.Picktheonethatwillneedthesmallestincrease
*inareatoaccomodatethenewrectangle.Thiswillresultinthe
*leasttotalareaforthecoveringrectanglesinthecurrentnode.
*Incaseofatie,picktheonewhichwassmallerbefore,toget
*thebestresolutionwhensearching.
*/
intRTreePickBranch(RTREEMBR*rc,RTREENODE*node)
{
RTREEMBR*r;
inti,first_time=1;
REALTYPEincrease,bestIncr=(REALTYPE)-1,area,bestArea=0;
intbest=0;
RTREEMBRtmp_rect;
assert(rc&&node);

for(i=0;i<MAXKIDS(node);i++)
{
if(node->branch[i].child)
{
r=&node->branch[i].mbr;
area=RTreeRectSphericalVolume(r);
tmp_rect=RTreeCombineRect(rc,r);
increase=RTreeRectSphericalVolume(&tmp_rect)-area;
if(increase<bestIncr||first_time)
{
best=i;
bestArea=area;
bestIncr=increase;
first_time=0;
}
elseif(increase==bestIncr&&area<bestArea)
{
best=i;
bestArea=area;
bestIncr=increase;
}
}
}
returnbest;
}

/**
*Addabranchtoanode.Splitthenodeifnecessary.
*Returns0ifnodenotsplit.Oldnodeupdated.
*Returns1ifnodesplit,sets*new_nodetoaddressofnewnode.
*Oldnodeupdated,becomesoneoftwo.
*/
intRTreeAddBranch(RTREEBRANCH*br,RTREENODE*node,RTREENODE**new_node)
{
inti;
assert(br&&node);

if(node->count<MAXKIDS(node))/*splitwon'tbenecessary*/
{
for(i=0;i<MAXKIDS(node);i++)/*findemptybranch*/
{
if(node->branch[i].child==NULL)
{
node->branch[i]=*br;
node->count++;
break;
}
}

return0;
}

assert(new_node);
RTreeSplitNode(node,br,new_node);

return1;
}

/**
*Disconnectadependentnode.
*/
voidRTreeDisconnectBranch(RTREENODE*node,inti)
{
assert(node&&i>=0&&i<MAXKIDS(node));
assert(node->branch[i].child);

_RTreeInitBranch(&(node->branch[i]));
node->count--;
}

/**
*Destroy(free)noderecursively.
*/
voidRTreeDestroyNode(RTREENODE*node)
{
inti;

if(node->level>0)
{
/*itisnotleaf->destroychilds*/
for(i=0;i<NODECARD;i++)
{
if(node->branch[i].child)
RTreeDestroyNode(node->branch[i].child);
}
}

/*Freethisnode*/
RTreeFreeNode(node);
}


/**
*Createanewrtreeindex,empty.Consistsofasinglenode.
*/
RTREENODE*RTreeCreate(void)
{
RTREENODE*root=RTreeNewNode();
root->level=0;/*leaf*/
returnroot;
}

/**
*Destroyartreerootmustbearootofrtree.Freeallmemory.
*/
voidRTreeDestroy(RTREENODE*root)
{
RTreeDestroyNode(root);
}

/**
*Searchinanindextreeorsubtreeforalldatarectanglesthatoverlaptheargumentrectangle.
*Returnthenumberofqualifyingdatarects.
*/
intRTreeSearch(RTREENODE*node,RTREEMBR*rc,pfnSearchHitCallbackpfnSHCB,void*pfnParam)
{
/*Fixnotyettested.*/
inthitCount=0;
inti;

assert(node&&rc);
assert(node->level>=0);

if(node->level>0)/*thisisaninternalnodeinthetree*/
{
for(i=0;i<NODECARD;i++){
if(node->branch[i].child&&RTreeOverlap(rc,&node->branch[i].mbr))
hitCount+=RTreeSearch(node->branch[i].child,rc,pfnSHCB,pfnParam);
}
}
else/*thisisaleafnode*/
{
#pragmawarning(push)/*C4311*/
#pragmawarning(disable:4311)
for(i=0;i<LEAFCARD;i++)
{
if(node->branch[i].child&&RTreeOverlap(rc,&node->branch[i].mbr))
{
hitCount++;

/*calltheuser-providedcallbackandreturnifcallbackwantstoterminatesearchearly*/
if(pfnSHCB&&!pfnSHCB((int)node->branch[i].child,pfnParam))
returnhitCount;

}
}
#pragmawarning(pop)
}
returnhitCount;
}

/**
*Insertadatarectangleintoanindexstructure.
*RTreeInsertRectprovidesforsplittingtheroot;
*returns1ifrootwassplit,0ifitwasnot.
*Thelevelargumentspecifiesthenumberofstepsupfromtheleaf
*leveltoinsert;e.g.adatarectanglegoesinatlevel=0.
*_RTreeInsertRectdoestherecursion.
*/
intRTreeInsertRect(RTREEMBR*rc,inttid,RTREENODE**root,intlevel)
{
#ifdef_DEBUG
inti;
#endif

RTREENODE*newroot;
RTREENODE*newnode;
RTREEBRANCHb;

assert(rc&&root);
assert(level>=0&&level<=(*root)->level);

#ifdef_DEBUG
for(i=0;i<DIMS_NUMB;i++)
assert(rc->bound[i]<=rc->bound[DIMS_NUMB+i]);
#endif

/*rootsplit*/
if(_RTreeInsertRect(rc,tid,*root,&newnode,level))
{
newroot=RTreeNewNode();/*growanewroot,&treetaller*/
newroot->level=(*root)->level+1;
b.mbr=RTreeNodeCover(*root);
b.child=*root;
RTreeAddBranch(&b,newroot,NULL);
b.mbr=RTreeNodeCover(newnode);
b.child=newnode;
RTreeAddBranch(&b,newroot,NULL);
*root=newroot;

return1;
}

return0;
}


/**
*Deleteadatarectanglefromanindexstructure.
*PassinapointertoaRTREEMBR,thetidoftherecord,ptrtoptrtorootnode.
*Returns1ifrecordnotfound,0ifsuccess.
*RTreeDeleteRectprovidesforeliminatingtheroot.
*/
intRTreeDeleteRect(RTREEMBR*rc,inttid,RTREENODE**root)
{
inti;
RTREENODE*tmp_nptr=NULL;
RTREELISTNODE*reInsertList=NULL;
RTREELISTNODE*e;

assert(rc&&root);
assert(*root);
assert(tid>=0);

if(!_RTreeDeleteRect(rc,tid,*root,&reInsertList))
{
/*foundanddeletedadataitem*/

/*reinsertanybranchesfromeliminatednodes*/
while(reInsertList)
{
tmp_nptr=reInsertList->node;

#pragmawarning(push)/*C4311*/
#pragmawarning(disable:4311)
for(i=0;i<MAXKIDS(tmp_nptr);i++)
{
if(tmp_nptr->branch[i].child)
{
RTreeInsertRect(&(tmp_nptr->branch[i].mbr),(int)tmp_nptr->branch[i].child,root,tmp_nptr->level);
}
}
#pragmawarning(pop)

e=reInsertList;
reInsertList=reInsertList->next;
RTreeFreeNode(e->node);
_RTreeFreeListNode(e);
}

/*checkforredundantroot(notleaf,1child)andeliminate*/
if((*root)->count==1&&(*root)->level>0)
{
for(i=0;i<NODECARD;i++)
{
tmp_nptr=(*root)->branch[i].child;
if(tmp_nptr)
break;
}
assert(tmp_nptr);
RTreeFreeNode(*root);
*root=tmp_nptr;
}

return0;
}

return1;
}

测试文件test.c：

/**
rtreelibusageexampleapp.
*/
#include<stdio.h>
#include"rtree.h"

RTREEMBRrects[]={
{{0,0,0,2,2,0}},/*xmin,ymin,zmin,xmax,ymax,zmax(for3dimensionalRTree)*/
{{5,5,0,7,7,0}},
{{8,5,0,9,6,0}},
{{7,1,0,9,2,0}}
};


intnrects=sizeof(rects)/sizeof(rects[0]);
RTREEMBRsearch_rect={
{6,4,0,10,6,0}/*searchwillfindaboverectsthatthisoneoverlaps*/
};

intMySearchCallback(intid,void*arg)
{
/*Note:-1tomakeupforthe+1whendatawasinserted*/
fprintf(stdout,"Hitdatambr%d ",id-1);
return1;/*keepgoing*/
}

intmain()
{
RTREENODE*root=RTreeCreate();

inti,nhits;

fprintf(stdout,"nrects=%d ",nrects);

/*Insertallthetestingdatarects*/
for(i=0;i<nrects;i++){
RTreeInsertRect(&rects[i],/*thembrbeinginserted*/
i+10,/*i+1ismbrID.IDMUSTNEVERBEZERO*/
&root,/*theaddressofrtree'srootsincerootcanchangeundernieth*/
0/*alwayszerowhichmeanstoaddfromtheroot*/
);
}

nhits=RTreeSearch(root,&search_rect,MySearchCallback,0);

fprintf(stdout,"Searchresultedin%dhits ",nhits);

RTreeDestroy(root);

return0;
}

使用VS2005，新建一个Console项目test，选为空项目。然后把这3个文件加入进来，就可以使用了。必要的话，把RTree.h和RTree.C建立成连接库，就更方便了。