RTree源代码——C语言实现

时间:2022-03-13 13:01:18

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-Tree library 
*              
* AUTHOR(S):    Antonin Guttman - original code
*               Daniel Green (green@superliminal.com) - major clean-up
*                               and implementation of bounding spheres
*               
* PURPOSE:      Multi Dimensional Index
*
* COPYRIGHT:    (C) 2001 by the GRASS Development Team
*
*               This program is free software under the GNU General Public
*               License (>=v2). Read the file COPYING that comes with GRASS
*               for details.
*
* LAST MODIFY:         ZhangLiang (cheungmine@gmail.com) - 2007-11
****************************************************************************
*/
#ifndef  RTREE_H_INCLUDED
#define   RTREE_H_INCLUDED

/*  PAGE_SIZE is normally the natural page size of the machine  */
#define   PAGE_SIZE    512
#define   DIMS_NUMB    3       /* number of dimensions */
#define   SIDES_NUMB   2*DIMS_NUMB

/*  typedef float REALTYPE;  */
typedef 
double  REALTYPE;


#ifndef  TRUE
#define   TRUE        1
#define   FALSE        0
#endif


typedef 
struct  _RTREEMBR
{
    REALTYPE bound[SIDES_NUMB]; 
/*  xmin,ymin,...,xmax,ymax,...  */
}RTREEMBR;

typedef 
struct  _RTREEBRANCH
{        
    RTREEMBR    mbr;
    
struct  _RTREENODE  * child;     /*  mbr id  */
}RTREEBRANCH;

/*  max branching factor of a node  */
#define  MAXCARD (int)((PAGE_SIZE-(2*sizeof(int))) / sizeof(RTREEBRANCH))

typedef 
struct  _RTREENODE
{
    
int     count;
    
int     level;  /*  0 is leaf, others positive  */
    RTREEBRANCH  branch[MAXCARD];
}RTREENODE;

typedef 
struct  _RTREELISTNODE
{
     
struct  _RTREELISTNODE     * next;
     RTREENODE        
* node;
}RTREELISTNODE;

/*
* If passed to a tree search, this callback function will be called
* with the ID of each data mbr that overlaps the search mbr
* plus whatever user specific pointer was passed to the search.
* It can terminate the search early by returning 0 in which case
* the search will return the number of hits found up to that point.
*/
typedef 
int  ( * pfnSearchHitCallback)( int  id,  void *  pfnParam);


int  RTreeSetNodeMax( int  new_max);

int  RTreeSetLeafMax( int  new_max);

int  RTreeGetNodeMax( void );

int  RTreeGetLeafMax( void );

/* *
 * Initialize a rectangle to have all 0 coordinates.
 
*/
void  RTreeInitRect( RTREEMBR  * rc);

/* *
 * Return a mbr whose first low side is higher than its opposite side -
 * interpreted as an undefined mbr.
 
*/
RTREEMBR RTreeNullRect(
void );


/* *
 * Print out the data for a rectangle.
 
*/
void  RTreePrintRect( RTREEMBR  * rc,  int  depth );

/* *
 * Calculate the 2-dimensional area of a rectangle
 
*/
REALTYPE RTreeRectArea( RTREEMBR 
* rc );

/* *
 * Calculate the n-dimensional volume of a rectangle
 
*/
REALTYPE RTreeRectVolume( RTREEMBR 
* rc );


/* *
 * Calculate the n-dimensional volume of the bounding sphere of a rectangle
 * The exact volume of the bounding sphere for the given RTREEMBR.
 
*/
REALTYPE RTreeRectSphericalVolume( RTREEMBR 
* rc );


/* *
 * Calculate the n-dimensional surface area of a rectangle
 
*/
REALTYPE RTreeRectSurfaceArea( RTREEMBR 
* rc );


/* *
 * Combine two rectangles, make one that includes both.
 
*/
RTREEMBR RTreeCombineRect( RTREEMBR 
* rc1, RTREEMBR  * rc2 );


/* *
 * Decide whether two rectangles overlap.
 
*/
int  RTreeOverlap( RTREEMBR  * rc1, RTREEMBR  * rc2);


/* *
 * Decide whether rectangle r is contained in rectangle s.
 
*/
int  RTreeContained( RTREEMBR  * r, RTREEMBR  * s);

/* *
 * Split a node.
 * Divides the nodes branches and the extra one between two nodes.
 * Old node is one of the new ones, and one really new one is created.
 * Tries more than one method for choosing a partition, uses best result.
 
*/
void  RTreeSplitNode( RTREENODE  * node, RTREEBRANCH  * br, RTREENODE  ** new_node);

/* *
 * Initialize a RTREENODE structure. 
 
*/
void  RTreeInitNode( RTREENODE  * node );

/*
 * Make a new node and initialize to have all branch cells empty. 
 
*/
RTREENODE 
* RTreeNewNode( void );

void  RTreeFreeNode( RTREENODE  * node );


/* *
 * Print out the data in a node. 
 
*/
void  RTreePrintNode( RTREENODE  * node,  int  depth );


/* *
 * Find the smallest rectangle that includes all rectangles in branches of a node.
 
*/
RTREEMBR RTreeNodeCover( RTREENODE 
* node );


/* *
 * Pick a branch.  Pick the one that will need the smallest increase
 * in area to accomodate the new rectangle.  This will result in the
 * least total area for the covering rectangles in the current node.
 * In case of a tie, pick the one which was smaller before, to get
 * the best resolution when searching.
 
*/
int  RTreePickBranch( RTREEMBR  * rc, RTREENODE  * node);


/* *
 * Add a branch to a node.  Split the node if necessary.
 * Returns 0 if node not split.  Old node updated.
 * Returns 1 if node split, sets *new_node to address of new node.
 * Old node updated, becomes one of two.
 
*/
int  RTreeAddBranch( RTREEBRANCH  * br, RTREENODE  * node, RTREENODE  ** new_node);


/* *
 * Disconnect a dependent node. 
 
*/
void  RTreeDisconnectBranch( RTREENODE  * node,  int  i );


/* *
 * Destroy (free) node recursively. 
 
*/
void  RTreeDestroyNode ( RTREENODE  * node );


/* *
 * Create a new rtree index, empty. Consists of a single node. 
 
*/
RTREENODE 
*  RTreeCreate( void );


/* *
 * Destroy a rtree root must be a root of rtree. Free all memory.
 
*/
void  RTreeDestroy(RTREENODE  * root);


/* *
 * Search in an index tree or subtree for all data rectangles that overlap the argument rectangle.
 * Return the number of qualifying data rects.
 
*/
int  RTreeSearch( RTREENODE  * node, RTREEMBR  * rc, pfnSearchHitCallback pfnSHCB,  void *  pfnParam);

/*
 * Insert a data rectangle into an index structure.
 * RTreeInsertRect provides for splitting the root;
 * returns 1 if root was split, 0 if it was not.
 * The level argument specifies the number of steps up from the leaf
 * level to insert; e.g. a data rectangle goes in at level = 0.
 * _RTreeInsertRect does the recursion.
 
*/
int  RTreeInsertRect( RTREEMBR  * rc,  int  tid, RTREENODE  ** root,  int  level);

/* *
 * Delete a data rectangle from an index structure.
 * Pass in a pointer to a RTREEMBR, the tid of the record, ptr to ptr to root node.
 * Returns 1 if record not found, 0 if success.
 * RTreeDeleteRect provides for eliminating the root.
 
*/
int  RTreeDeleteRect( RTREEMBR  * rc,  int  tid, RTREENODE  ** root);

#endif  /* RTREE_H_INCLUDED */

 

RTree.C文件:

 

/* ***************************************************************************
* RTree.C
*
* MODULE:       R-Tree library 
*              
* AUTHOR(S):    Antonin Guttman - original code
*               Daniel Green (green@superliminal.com) - major clean-up
*                               and implementation of bounding spheres
*               
* PURPOSE:      Multi Dimensional Index
*
* COPYRIGHT:    (C) 2001 by the GRASS Development Team
*
*               This program is free software under the GNU General Public
*               License (>=v2). Read the file COPYING that comes with GRASS
*               for details.
*
* LAST MODIFY:         ZhangLiang (cheungmine@gmail.com) - 2007-11
****************************************************************************
*/

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

#include 
" rtree.h "

#define         METHODS        1

/*  variables for finding a partition  */
typedef 
struct  _RTREEPARTITION
{
    
int             partition[MAXCARD + 1 ];
    
int             total;
    
int             minfill;
    
int             taken[MAXCARD + 1 ];
    
int             count[ 2 ];
    RTREEMBR    cover[
2 ];
    REALTYPE    area[
2 ];
} RTREEPARTITION;

RTREEBRANCH        BranchBuf[MAXCARD
+ 1 ];
int                 BranchCount;
RTREEMBR        CoverSplit;
REALTYPE        CoverSplitArea;
RTREEPARTITION    Partitions[METHODS];


#define  BIG_NUM (FLT_MAX/4.0)

#define  INVALID_RECT(x) ((x)->bound[0] > (x)->bound[DIMS_NUMB])
#define  MIN(a, b) ((a) < (b) ? (a) : (b))
#define  MAX(a, b) ((a) > (b) ? (a) : (b))

int  NODECARD  =  MAXCARD;
int  LEAFCARD  =  MAXCARD;

/*  balance criteria for node splitting  */
/*  NOTE: can be changed if needed.  */
#define  MINNODEFILL (NODECARD / 2)
#define  MINLEAFFILL (LEAFCARD / 2)

#define  MAXKIDS(n) ((n)->level > 0 ? NODECARD : LEAFCARD)
#define  MINFILL(n) ((n)->level > 0 ? MINNODEFILL : MINLEAFFILL)

static   int  set_max( int   * which,  int  new_max)
{
    
if ( 2   >  new_max  ||  new_max  >  MAXCARD)
        
return   0 ;
    
* which  =  new_max;
    
return   1 ;
}


/* *
 * Load branch buffer with branches from full node plus the extra branch.
 
*/
static   void  _RTreeGetBranches( RTREENODE  * node, RTREEBRANCH  * br)
{
    
int  i;

    assert(node 
&&  br);
    
    
/*  load the branch buffer  */
    
for  (i = 0 ; i < MAXKIDS(node); i ++ )
    {
        assert(node
-> branch[i].child);  /*  n should have every entry full  */
        BranchBuf[i] 
=  node -> branch[i];
    }

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

    
/*  calculate mbr containing all in the set  */
    CoverSplit 
=  BranchBuf[ 0 ].mbr;

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

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



/* *
 * Put a branch in one of the groups.
 
*/
static   void  _RTreeClassify( int  i,  int  group, 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] ++ ;
}

/* *
 * Pick two rects from set to be the first elements of the two groups.
 * Pick the two that waste the most area if covered by a single rectangle.
 
*/
static   void  _RTreePickSeeds(RTREEPARTITION  * p)
{
    
int  i, j, seed0 = 0 , seed1 = 0 ;
    REALTYPE worst, 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 ++ )
        {
            RTREEMBR one_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);
}


/* *
 * Copy branches from the buffer into two nodes according to the partition.
 
*/
static   void  _RTreeLoadNodes( RTREENODE  * n, RTREENODE  * q, RTREEPARTITION  * p)
{
    
int  i;
    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);
        
else   if  (p -> partition[i]  ==   1 )
            RTreeAddBranch(
& BranchBuf[i], q, NULL);
    }
}

/* *
 * Initialize a RTREEPARTITION structure.
 
*/
static   void  _RTreeInitPart( RTREEPARTITION  * p,  int  maxrects,  int  minfill)
{
    
int  i;
    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 ;
    }
}


/* *
 * Print out data for a partition from RTREEPARTITION struct.
 
*/
static   void  _RTreePrintPart( RTREEPARTITION  * p)
{
    
int  i;
    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] = %d  area = %f " , p -> count[ 0 ], p -> area[ 0 ]);
    fprintf (stdout, 
" count[1] = %d  area = %f " , p -> count[ 1 ], p -> area[ 1 ]);
    
if  (p -> area[ 0 +  p -> area[ 1 >   0 )
    {
        fprintf (stdout, 
" total area = %f  effectiveness = %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 #0 for choosing a partition:
 * As the seeds for the two groups, pick the two rects that would waste the
 * most area if covered by a single rectangle, i.e. evidently the worst pair
 * to have in the same group.
 * Of the remaining, one at a time is chosen to be put in one of the two groups.
 * The one chosen is the one with the greatest difference in area expansion
 * depending on which group - the mbr most strongly attracted to one group
 * and repelled from the other.
 * If one group gets too full (more would force other group to violate min
 * fill requirement) then other group gets the rest.
 * These last are the ones that can go in either group most easily.
 
*/
static   void  _RTreeMethodZero( RTREEPARTITION  * p,  int  minfill )
{
    
int  i;
    REALTYPE biggestDiff;
    
int  group, 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;
                REALTYPE growth0, 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;
                }
                
else   if  (diff == biggestDiff  &&  p -> count[group] < p -> count[betterGroup])
                {
                    chosen 
=  i;
                    betterGroup 
=  group;
                }
            }
        }
        _RTreeClassify(chosen, betterGroup, p);
    }
    
    
/*  if one group too full, put remaining rects in the other  */
    
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);
}


/* *
 * Initialize one branch cell in a node. 
 
*/
static   void  _RTreeInitBranch( RTREEBRANCH  * br )
{
    RTreeInitRect(
& (br -> mbr));
    br
-> child  =  NULL;
}


static   void  _RTreePrintBranch( RTREEBRANCH  * br,  int  depth )
{
    RTreePrintRect(
& (br -> mbr), depth);
    RTreePrintNode(br
-> child, depth);
}


/* *
 * Inserts a new data rectangle into the index structure.
 * Recursively descends tree, propagates splits back up.
 * Returns 0 if node was not split.  Old node updated.
 * If node was split, returns 1 and sets the pointer pointed to by
 * new_node to point to the new node.  Old node updated to become one of two.
 * The level argument specifies the number of steps up from the leaf
 * level to insert; e.g. a data rectangle goes in at level = 0.
 
*/
static   int  _RTreeInsertRect( RTREEMBR  * rc,  int  tid,  RTREENODE  * node, RTREENODE  ** new_node,  int  level)
{
    
int  i;
    RTREEBRANCH b;
    RTREENODE 
* n2;

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

    
/*  Still above level for insertion, go down tree recursively  */
    
if  (node -> level  >  level)
    {
        i 
=  RTreePickBranch(rc, node);
        
if  ( ! _RTreeInsertRect(rc, tid, node -> branch[i].child,  & n2, level))
        {
            
/*  child was not split  */
            node
-> branch[i].mbr  =  RTreeCombineRect(rc,  & (node -> branch[i].mbr));
            
return   0 ;
        }
        
        
/*  child was split  */
        node
-> branch[i].mbr  =  RTreeNodeCover(node -> branch[i].child);
        b.child 
=  n2;
        b.mbr 
=  RTreeNodeCover(n2);

        
return  RTreeAddBranch( & b, node, new_node);
    }    
    
else   if  (node -> level  ==  level)     /*  Have reached level for insertion. Add mbr, split if necessary  */
    {
        b.mbr 
=   * rc;

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

        
/*  child field of leaves contains tid of data record  */
        
return  RTreeAddBranch( & b, node, new_node);
    }
    
    
/*  Not supposed to happen  */
    assert (FALSE);
    
return   0 ;
}


/* *
 * Allocate space for a node in the list used in DeletRect to
 * store Nodes that are too empty.
 
*/
static  RTREELISTNODE  *  _RTreeNewListNode( void )
{
    
return  (RTREELISTNODE  * ) malloc( sizeof (RTREELISTNODE));
}

static   void  _RTreeFreeListNode(RTREELISTNODE  * p)
{
    free(p);
}

/* *
 * Add a node to the reinsertion list.  All its branches will later
 * be reinserted into the index structure.
 
*/
static   void  _RTreeReInsert(RTREENODE  * node, RTREELISTNODE  ** ne)
{
    RTREELISTNODE 
* ln  =  _RTreeNewListNode();
    ln
-> node  =  node;
    ln
-> next  =   * ne;
    
* ne  =  ln;
}

/* *
 * Delete a rectangle from non-root part of an index structure.
 * Called by RTreeDeleteRect.  Descends tree recursively,
 * merges branches on the way back up.
 * Returns 1 if record not found, 0 if success.
 
*/
static   int  _RTreeDeleteRect( RTREEMBR  * rc,  int  tid, RTREENODE  * node, RTREELISTNODE  ** ee)
{
    
int  i;

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

    
if  (node -> level  >   0 )   /*  not a leaf node  */
    {
        
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 {     /*  not enough entries in child, eliminate child node  */
                        _RTreeReInsert(node
-> branch[i].child, ee);
                        RTreeDisconnectBranch(node, i);
                    }
                    
return   0 ;
                }
            }
        }
        
return   1 ;
    }

#pragma  warning(push)    /* C4312 */
#pragma  warning( disable : 4312 )

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

    }
#pragma  warning(pop)

    
return   1 ;
}

static   void  _RTreeTabIn( int  depth)
{
    
int  i;
    
for (i = 0 ; i < depth; i ++ )
        putchar(
' ' );
}

/* =============================================================================
                                Public functions:
 =============================================================================
*/

int  RTreeSetNodeMax( int  new_max) {  return  set_max( & NODECARD, new_max); }
int  RTreeSetLeafMax( int  new_max) {  return  set_max( & LEAFCARD, new_max); }
int  RTreeGetNodeMax( void ) {  return  NODECARD; }
int  RTreeGetLeafMax( void ) {  return  LEAFCARD; }

/* *
 * Initialize a rectangle to have all 0 coordinates.
 
*/
void  RTreeInitRect( RTREEMBR  * rc)
{
    
int  i;
    
for  (i = 0 ; i < SIDES_NUMB; i ++ )
        rc
-> bound[i]  =  (REALTYPE)  0 ;
}


/* *
 * Return a mbr whose first low side is higher than its opposite side -
 * interpreted as an undefined mbr.
 
*/
RTREEMBR RTreeNullRect(
void )
{
    RTREEMBR rc;
    
int  i;

    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 ;
    
return  rc;
}

/* *
 * Print out the data for a rectangle.
 
*/
void  RTreePrintRect( RTREEMBR  * rc,  int  depth)
{
    
int  i;
    
    _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]);
    }
}

/* *
 * Calculate the 2-dimensional area of a rectangle
 
*/
REALTYPE RTreeRectArea( 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 ]);
}


/* *
 * Calculate the n-dimensional volume of a rectangle
 
*/
REALTYPE RTreeRectVolume( RTREEMBR 
* rc )
{
    
int  i;
    REALTYPE vol 
=  (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 );
    
return  vol;
}


/* *
 * Precomputed volumes of the unit spheres for the first few dimensions 
 
*/
const   double  UnitSphereVolumes[]  =  {
    
0.000000 ,   /*  dimension   0  */
    
2.000000 ,   /*  dimension   1  */
    
3.141593 ,   /*  dimension   2  */
    
4.188790 ,   /*  dimension   3  */
    
4.934802 ,   /*  dimension   4  */
    
5.263789 ,   /*  dimension   5  */
    
5.167713 ,   /*  dimension   6  */
    
4.724766 ,   /*  dimension   7  */
    
4.058712 ,   /*  dimension   8  */
    
3.298509 ,   /*  dimension   9  */
    
2.550164 ,   /*  dimension  10  */
    
1.884104 ,   /*  dimension  11  */
    
1.335263 ,   /*  dimension  12  */
    
0.910629 ,   /*  dimension  13  */
    
0.599265 ,   /*  dimension  14  */
    
0.381443 ,   /*  dimension  15  */
    
0.235331 ,   /*  dimension  16  */
    
0.140981 ,   /*  dimension  17  */
    
0.082146 ,   /*  dimension  18  */
    
0.046622 ,   /*  dimension  19  */
    
0.025807 ,   /*  dimension  20  */
};

#if  DIMS_NUMB > 20
    
#error  "not enough precomputed sphere volumes"
#endif

#define  UnitSphereVolume UnitSphereVolumes[DIMS_NUMB]

/* *
 * Calculate the n-dimensional volume of the bounding sphere of a rectangle.
 * The exact volume of the bounding sphere for the given RTREEMBR.
 
*/
REALTYPE RTreeRectSphericalVolume( RTREEMBR 
* rc )
{
    
int  i;
    
double  sum_of_squares = 0 , radius;

    
if  (INVALID_RECT(rc))
        
return  (REALTYPE)  0 ;
    
    
for  (i = 0 ; i < DIMS_NUMB; i ++ ) {
        
double  half_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);
}


/* *
 * Calculate the n-dimensional surface area of a rectangle
 
*/
REALTYPE RTreeRectSurfaceArea( RTREEMBR 
* rc )
{
    
int  i, j;
    REALTYPE sum 
=  (REALTYPE)  0 ;

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

    
for  (i = 0 ; i < DIMS_NUMB; i ++ ) {
        REALTYPE face_area 
=  (REALTYPE) 1 ;
        
for  (j = 0 ; j < DIMS_NUMB; j ++ )
            
/*  exclude i extent from product in this dimension  */
            
if (i  !=  j) {
                REALTYPE j_extent 
=     rc -> bound[j + DIMS_NUMB]  -  rc -> bound[j];
                face_area 
*=  j_extent;
            }
            sum 
+=  face_area;
    }
    
return   2   *  sum;
}



/* *
 * Combine two rectangles, make one that includes both.
 
*/
RTREEMBR RTreeCombineRect( RTREEMBR 
* rc1, RTREEMBR  * rc2 )
{
    
int  i, j;
    RTREEMBR new_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]);
    }
    
return  new_rect;
}


/* *
 * Decide whether two rectangles overlap.
 
*/
int  RTreeOverlap( RTREEMBR  * rc1, RTREEMBR  * rc2)
{
    
int  i, j;
    assert(rc1 
&&  rc2);

    
for  (i = 0 ; i < DIMS_NUMB; i ++ )
    {
        j 
=  i  +  DIMS_NUMB;   /*  index for high sides  */

        
if  (rc1 -> bound[i]  >  rc2 -> bound[j]  ||  rc2 -> bound[i]  >  rc1 -> bound[j])
            
return  FALSE;
    }
    
return  TRUE;
}


/* *
 * Decide whether rectangle r is contained in rectangle s.
 
*/
int  RTreeContained( RTREEMBR  * r, RTREEMBR  * s)
{
    
int  i, j, result;
    assert(r 
&&  s);

    
/*  undefined mbr is contained in any other  */
    
if  (INVALID_RECT(r))
        
return  TRUE;

    
/*  no mbr (except an undefined one) is contained in an undef mbr  */
    
if  (INVALID_RECT(s))
        
return  FALSE;

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

/* *
 * Split a node.
 * Divides the nodes branches and the extra one between two nodes.
 * Old node is one of the new ones, and one really new one is created.
 * Tries more than one method for choosing a partition, uses best result.
 
*/
void  RTreeSplitNode( RTREENODE  * node, RTREEBRANCH  * br, RTREENODE  ** new_node)
{
    RTREEPARTITION 
* p;
    
int  level;

    assert(node 
&&  br);
    
    
/*  load all the branches into a buffer, initialize old node  */
    level 
=  node -> level;
    _RTreeGetBranches(node, br);

    
/*  find partition  */
    p 
=   & Partitions[ 0 ];

    
/*  Note: can't use MINFILL(n) below since node was cleared by GetBranches()  */
    _RTreeMethodZero(p, level
> 0   ?  MINNODEFILL : MINLEAFFILL);

    
/*  put branches from buffer into 2 nodes according to chosen partition     */
    
* new_node  =  RTreeNewNode();
    (
* new_node) -> level  =  node -> level  =  level;
    _RTreeLoadNodes(node, 
* new_node, p);

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


/* *
 * Initialize a RTREENODE structure. 
 
*/
void  RTreeInitNode( RTREENODE  * node )
{
    
int  i;
    node
-> count  =   0 ;
    node
-> level  =   - 1 ;
    
for  (i  =   0 ; i  <  MAXCARD; i ++ )
        _RTreeInitBranch(
& (node -> branch[i]));
}

/*
 * Make a new node and initialize to have all branch cells empty. 
 
*/
RTREENODE 
* RTreeNewNode( void )
{
    RTREENODE 
* node  =  (RTREENODE * ) malloc( sizeof (RTREENODE));
    assert(node);
    RTreeInitNode(node);
    
return  node;
}

void  RTreeFreeNode( RTREENODE  * node )
{
    assert(node);
    free(node);
}


/* *
 * Print out the data in a node. 
 
*/
void  RTreePrintNode( RTREENODE  * node,  int  depth )
{
    
int  i;
    assert(node);

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

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

#pragma  warning(push)    /* C4311 */
#pragma  warning( disable : 4311 )
    fprintf (stdout, 
"   level=%d  count=%d  address=%o " , node -> level, node -> count, (unsigned  int ) node);
#pragma  warning(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 );
        }
    }
}

/* *
 * Find the smallest rectangle that includes all rectangles in branches of a node.
 
*/
RTREEMBR RTreeNodeCover( RTREENODE 
* node )
{
    
int  i, first_time = 1 ;
    RTREEMBR rc;
    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));
        }
    }
    
return  rc;
}

/* *
 * Pick a branch.  Pick the one that will need the smallest increase
 * in area to accomodate the new rectangle.  This will result in the
 * least total area for the covering rectangles in the current node.
 * In case of a tie, pick the one which was smaller before, to get
 * the best resolution when searching.
 
*/
int  RTreePickBranch( RTREEMBR  * rc, RTREENODE  * node)
{
    RTREEMBR 
* r;
    
int  i, first_time  =   1 ;
    REALTYPE increase, bestIncr
= (REALTYPE) - 1 , area, bestArea = 0 ;
    
int  best = 0 ;
    RTREEMBR tmp_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 ;
            }
            
else   if  (increase  ==  bestIncr  &&  area  <  bestArea)
            {
                best 
=  i;
                bestArea 
=  area;
                bestIncr 
=  increase;
            }
        }
    }
    
return  best;
}

/* *
 * Add a branch to a node.  Split the node if necessary.
 * Returns 0 if node not split.  Old node updated.
 * Returns 1 if node split, sets *new_node to address of new node.
 * Old node updated, becomes one of two.
 
*/
int  RTreeAddBranch( RTREEBRANCH  * br, RTREENODE  * node, RTREENODE  ** new_node)
{
    
int  i;
    assert(br 
&&  node);
    
    
if  (node -> count  <  MAXKIDS(node))   /*  split won't be necessary  */
    {
        
for  (i  =   0 ; i  <  MAXKIDS(node); i ++ )   /*  find empty branch  */
        {
            
if  (node -> branch[i].child  ==  NULL)
            {
                node
-> branch[i]  =   * br;
                node
-> count ++ ;
                
break ;
            }
        }

        
return   0 ;
    }
    
    assert(new_node);
    RTreeSplitNode(node, br, new_node);
    
    
return   1 ;
}

/* *
 * Disconnect a dependent node. 
 
*/
void  RTreeDisconnectBranch( RTREENODE  * node,  int  i )
{
    assert(node 
&&  i >= 0   &&  i < MAXKIDS(node));
    assert(node
-> branch[i].child);

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

/* *
 * Destroy (free) node recursively. 
 
*/
void  RTreeDestroyNode ( RTREENODE  * node )
{
    
int  i;

    
if  (node -> level  >   0
    {
        
/*  it is not leaf -> destroy childs  */
        
for  ( i  =   0 ; i  <  NODECARD; i ++
        {
            
if  ( node -> branch[i].child ) 
                RTreeDestroyNode ( node
-> branch[i].child );
        }
    }

    
/*  Free this node  */
    RTreeFreeNode( node );
}


/* *
 * Create a new rtree index, empty. Consists of a single node. 
 
*/
RTREENODE 
*  RTreeCreate( void )
{
    RTREENODE 
*  root  =  RTreeNewNode();
    root
-> level  =   0 /*  leaf  */
    
return  root;
}

/* *
 * Destroy a rtree root must be a root of rtree. Free all memory.
 
*/
void  RTreeDestroy(RTREENODE  * root)
{
    RTreeDestroyNode (root);
}

/* *
 * Search in an index tree or subtree for all data rectangles that overlap the argument rectangle.
 * Return the number of qualifying data rects.
 
*/
int  RTreeSearch( RTREENODE  * node, RTREEMBR  * rc, pfnSearchHitCallback pfnSHCB,  void *  pfnParam)
{
    
/*  Fix not yet tested.  */
    
int  hitCount  =   0 ;
    
int  i;

    assert(node 
&&  rc);
    assert(node
-> level  >=   0 );
    
    
if  (node -> level  >   0 /*  this is an internal node in the tree  */
    {
        
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   /*  this is a leaf node  */
    {
#pragma  warning(push)    /* C4311 */
#pragma  warning( disable : 4311 )
        
for  (i = 0 ; i < LEAFCARD; i ++ )
        {
            
if  (node -> branch[i].child  &&  RTreeOverlap(rc,  & node -> branch[i].mbr))
            {
                hitCount
++ ;

                
/*  call the user-provided callback and return if callback wants to terminate search early  */
                
if (pfnSHCB  &&   !  pfnSHCB(( int )node -> branch[i].child, pfnParam) )
                    
return  hitCount; 

            }
        }
#pragma  warning(pop)
    }
    
return  hitCount;
}

/*
 * Insert a data rectangle into an index structure.
 * RTreeInsertRect provides for splitting the root;
 * returns 1 if root was split, 0 if it was not.
 * The level argument specifies the number of steps up from the leaf
 * level to insert; e.g. a data rectangle goes in at level = 0.
 * _RTreeInsertRect does the recursion.
 
*/
int  RTreeInsertRect( RTREEMBR  * rc,  int  tid, RTREENODE  ** root,  int  level)
{
#ifdef _DEBUG
    
int  i;
#endif

    RTREENODE    
* newroot;
    RTREENODE    
* newnode;
    RTREEBRANCH b;
    
    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

    
/*  root split  */
    
if  (_RTreeInsertRect(rc, tid,  * root,  & newnode, level))  
    {
        newroot 
=  RTreeNewNode();   /*  grow a new root, & tree taller  */
        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;
        
        
return   1 ;
    }

    
return   0 ;
}


/* *
 * Delete a data rectangle from an index structure.
 * Pass in a pointer to a RTREEMBR, the tid of the record, ptr to ptr to root node.
 * Returns 1 if record not found, 0 if success.
 * RTreeDeleteRect provides for eliminating the root.
 
*/
int  RTreeDeleteRect( RTREEMBR  * rc,  int  tid, RTREENODE  ** root)
{
    
int         i;
    RTREENODE        
* tmp_nptr  =  NULL;
    RTREELISTNODE    
* reInsertList  =  NULL;
    RTREELISTNODE    
* e;

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

    
if  ( ! _RTreeDeleteRect(rc, tid,  * root,  & reInsertList))
    {
        
/*  found and deleted a data item  */

        
/*  reinsert any branches from eliminated nodes  */
        
while  (reInsertList)
        {
            tmp_nptr 
=  reInsertList -> node;

#pragma  warning(push)    /* C4311 */
#pragma  warning( 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);
                }
            }
#pragma  warning(pop)

            e 
=  reInsertList;
            reInsertList 
=  reInsertList -> next;
            RTreeFreeNode(e
-> node);
            _RTreeFreeListNode(e);
        }
        
        
/*  check for redundant root (not leaf, 1 child) and eliminate  */
        
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;
        }

        
return   0 ;
    }
    
    
return   1 ;
}

 

测试文件test.c:

 

/* *
    rtree lib usage example app.
 
*/
#include 
< stdio.h >
#include 
" rtree.h "

RTREEMBR rects[] 
=  {
    { {
0 0 0 2 2 0 } },   /*  xmin, ymin, zmin, xmax, ymax, zmax (for 3 dimensional RTree)  */
    { {
5 5 0 7 7 0 } },
    { {
8 5 0 9 6 0 } },
    { {
7 1 0 9 2 0 } }
};


int  nrects  =   sizeof (rects)  /   sizeof (rects[ 0 ]);
RTREEMBR search_rect 
=  {
    {
6 4 0 10 6 0 }    /*  search will find above rects that this one overlaps  */
};

int  MySearchCallback( int  id,  void *  arg) 
{
    
/*  Note: -1 to make up for the +1 when data was inserted  */
    fprintf (stdout, 
" Hit data mbr %d " , id - 1 );
    
return   1 /*  keep going  */
}

int  main()
{
    RTREENODE
*  root  =  RTreeCreate();
    
    
int  i, nhits;
    
    fprintf (stdout, 
" nrects = %d " , nrects);
    
    
/*  Insert all the testing data rects  */
    
for (i = 0 ; i < nrects; i ++ ){
        RTreeInsertRect(
& rects[i],   /*  the mbr being inserted  */
                        i
+ 10 ,         /*  i+1 is mbr ID. ID MUST NEVER BE ZERO  */
                        
& root,         /*  the address of rtree's root since root can change undernieth */
                        
0              /*  always zero which means to add from the root  */
                    );
    }

    nhits 
=  RTreeSearch(root,  & search_rect, MySearchCallback,  0 );
    
    fprintf (stdout, 
" Search resulted in %d hits " , nhits);

    RTreeDestroy (root);

    
return   0 ;
}


 

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