哪个好心人，帮我解释这个 R 树的源代码。万分感激。
#include <stdio.h>#include <stdlib.h>
#include <assert.h>
#include <float.h>
#include <math.h>
#include "rtree.h"
#define METHODS 1
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;
typedef struct _RTREENODE
{
int count;
int level;
RTREEBRANCH branch[MAXCARD];
}RTREENODE;
typedef struct _RTREELISTNODE
{
struct _RTREELISTNODE *next;
RTREENODE *node;
}RTREELISTNODE;
typedef struct _RTREEROOT
{
RTREENODE* root_node;
RTREEBRANCH BranchBuf[MAXCARD+1];
int BranchCount;
RTREEMBR CoverSplit;
REALTYPE CoverSplitArea;
RTREEPARTITION Partitions[METHODS];
PFNRTreeSearchCallback pfnCallback;
} RTREEROOT;
#define BIG_NUM (FLT_MAX/4.0)
#define INVALID_RECT(x) ((x)->bound[0] > (x)->bound[DIMS_NUMB])
#ifndef MIN
#define MIN(a, b) ((a) < (b) ? (a) : (b))
#endif
#ifndef MAX
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#endif
int NODECARD = MAXCARD;
int LEAFCARD = MAXCARD;
#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;
}
static int RTreeSetNodeMax(int new_max) { return set_max(&NODECARD, new_max); }
static int RTreeSetLeafMax(int new_max) { return set_max(&LEAFCARD, new_max); }
static int RTreeGetNodeMax(void) { return NODECARD; }
static int RTreeGetLeafMax(void) { return LEAFCARD; }
static void _RTreeGetBranches(HRTREEROOT root, RTREENODE *node, RTREEBRANCH *br)
{
int i;
assert(node && br);
for (i=0; i<MAXKIDS(node); i++)
{
assert(node->branch[i].child);
root->BranchBuf[i] = node->branch[i];
}
root->BranchBuf[MAXKIDS(node)] = *br;
root->BranchCount = MAXKIDS(node) + 1;
root->CoverSplit = root->BranchBuf[0].mbr;
for (i=1; i<MAXKIDS(node)+1; i++)
{
root->CoverSplit = RTreeCombineRect(&root->CoverSplit, &root->BranchBuf[i].mbr);
}
root->CoverSplitArea = RTreeRectSphericalVolume(&root->CoverSplit);
RTreeInitNode(node);
}
static void _RTreeClassify(HRTREEROOT root, 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] = root->BranchBuf[i].mbr;
else
p->cover[group] = RTreeCombineRect(&root->BranchBuf[i].mbr, &p->cover[group]);
p->area[group] = RTreeRectSphericalVolume(&p->cover[group]);
p->count[group]++;
}
static void _RTreePickSeeds(HRTREEROOT root, 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(&root->BranchBuf[i].mbr);
worst = -root->CoverSplitArea - 1;
for (i=0; i<p->total-1; i++)
{
for (j=i+1; j<p->total; j++)
{
RTREEMBR one_rect;
one_rect = RTreeCombineRect(&root->BranchBuf[i].mbr, &root->BranchBuf[j].mbr);
waste = RTreeRectSphericalVolume(&one_rect) - area[i] - area[j];
if (waste > worst)
{
worst = waste;
seed0 = i;
seed1 = j;
}
}
}
_RTreeClassify(root, seed0, 0, p);
_RTreeClassify(root, seed1, 1, p);
}
static void _RTreeLoadNodes(HRTREEROOT root, 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(root, &root->BranchBuf[i], n, NULL);
else if (p->partition[i] == 1)
RTreeAddBranch(root, &root->BranchBuf[i], q, NULL);
}
}
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;
}
}
static void _RTreePrintPart(HRTREEROOT root, RTREEPARTITION *p)
{
int i;
assert(p);
fprintf (stdout, "\npartition:\n");
for (i=0; i<p->total; i++)
{
fprintf (stdout, "%3d\t", i);
}
fprintf (stdout, "\n");
for (i=0; i<p->total; i++)
{
if (p->taken[i])
fprintf (stdout, " t\t");
else
fprintf (stdout, "\t");
}
fprintf (stdout, "\n");
for (i=0; i<p->total; i++)
{
fprintf (stdout, "%3d\t", p->partition[i]);
}
fprintf (stdout, "\n");
fprintf (stdout, "count[0] = %d area = %f\n", p->count[0], p->area[0]);
fprintf (stdout, "count[1] = %d area = %f\n", p->count[1], p->area[1]);
if (p->area[0] + p->area[1] > 0)
{
fprintf (stdout, "total area = %f effectiveness = %3.2f\n",
p->area[0] + p->area[1], (float)root->CoverSplitArea / (p->area[0] + p->area[1]));
}
fprintf (stdout, "cover[0]:\n");
RTreePrintRect(&p->cover[0], 0);
fprintf (stdout, "cover[1]:\n");
RTreePrintRect(&p->cover[1], 0);
}
static void _RTreeMethodZero(HRTREEROOT root, RTREEPARTITION *p, int minfill )
{
int i;
REALTYPE biggestDiff;
int group, chosen=0, betterGroup=0;
assert(p);
_RTreeInitPart(p, root->BranchCount, minfill);
_RTreePickSeeds(root, 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 = &root->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(root, chosen, betterGroup, p);
}
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(root, i, group, p);
}
}
assert(p->count[0] + p->count[1] == p->total);
assert(p->count[0] >= p->minfill && p->count[1] >= p->minfill);
}
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);
}
static int _RTreeInsertRect(HRTREEROOT root, RTREEMBR *mbr, void* tid, RTREENODE *node, RTREENODE **new_node, int level)
{
int i;
RTREEBRANCH b;
RTREENODE *n2;
assert(mbr && node && new_node);
assert(level >= 0 && level <= node->level);
if (node->level > level)
{
i = RTreePickBranch(mbr, node);
if (!_RTreeInsertRect(root, mbr, tid, node->branch[i].child, &n2, level))
{
node->branch[i].mbr = RTreeCombineRect(mbr, &(node->branch[i].mbr));
return 0;
}
node->branch[i].mbr = RTreeNodeCover(node->branch[i].child);
b.child = n2;
b.mbr = RTreeNodeCover(n2);
return RTreeAddBranch(root, &b, node, new_node);
}
else if (node->level == level)
{
b.mbr = *mbr;
#pragma warning(push)
#pragma warning( disable : 4312 )
b.child = ( RTREENODE *) tid;
#pragma warning(pop)
return RTreeAddBranch(root, &b, node, new_node);
}
assert (FALSE);
return 0;
}
static RTREELISTNODE * _RTreeNewListNode(void)
{
return (RTREELISTNODE *) malloc(sizeof(RTREELISTNODE));
}
static void _RTreeFreeListNode(RTREELISTNODE *p)
{
free(p);
}
static void _RTreeReInsert(RTREENODE *node, RTREELISTNODE **ne)
{
RTREELISTNODE *ln = _RTreeNewListNode();
ln->node = node;
ln->next = *ne;
*ne = ln;
}
static int _RTreeDeleteRect( RTREEMBR *mbr, void* tid, RTREENODE *node, RTREELISTNODE **ee)
{
int i;
assert(mbr && node && ee);
assert(node->level >= 0);
if (node->level > 0)
{
for (i = 0; i < NODECARD; i++)
{
if (node->branch[i].child && RTreeOverlap( mbr, &(node->branch[i].mbr )))
{
if (!_RTreeDeleteRect( mbr, tid, node->branch[i].child, ee ))
{
if (node->branch[i].child->count >= MINNODEFILL)
node->branch[i].mbr = RTreeNodeCover( node->branch[i].child );
else{
_RTreeReInsert(node->branch[i].child, ee);
RTreeDisconnectBranch(node, i);
}
return 0;
}
}
}
return 1;
}
#pragma warning(push)
#pragma warning( disable : 4312 )
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++){
}
}
static int _RTreeSearchRect( RTREENODE *node, RTREEMBR *mbr, PFNRTreeSearchCallback pfnSHCB, void* pfnParam)
{
int hitCount = 0;
int i;
assert(node && mbr);
assert(node->level >= 0);
if (node->level > 0)
{
for (i=0; i<NODECARD; i++){
if (node->branch[i].child && RTreeOverlap(mbr, &node->branch[i].mbr))
hitCount += _RTreeSearchRect(node->branch[i].child, mbr, pfnSHCB, pfnParam);
}
}
else
{
#pragma warning(push)
#pragma warning( disable : 4311 )
for (i=0; i<LEAFCARD; i++)
{
if (node->branch[i].child && RTreeOverlap(mbr, &node->branch[i].mbr))
{
hitCount++;
if(pfnSHCB && ! pfnSHCB((void*)node->branch[i].child, pfnParam) )
return hitCount;
}
}
#pragma warning(pop)
}
return hitCount;
}
void RTreeInitRect( RTREEMBR *mbr)
{
int i;
for (i=0; i<SIDES_NUMB; i++)
mbr->bound[i] = (REALTYPE) 0;
}
RTREEMBR RTreeNullRect(void)
{
RTREEMBR mbr;
int i;
mbr.bound[0] = (REALTYPE) 1;
mbr.bound[DIMS_NUMB] = (REALTYPE)-1;
for (i=1; i<DIMS_NUMB; i++)
mbr.bound[i] = mbr.bound[i+DIMS_NUMB] = (REALTYPE) 0;
return mbr;
}
void RTreePrintRect( RTREEMBR *mbr, int depth)
{
int i;
_RTreeTabIn(depth);
fprintf (stdout, "mbr:\n");
for (i = 0; i < DIMS_NUMB; i++)
{
_RTreeTabIn(depth+1);
fprintf (stdout, "%f\t%f\n", mbr->bound[i], mbr->bound[i + DIMS_NUMB]);
}
}
REALTYPE RTreeRectArea( RTREEMBR *mbr )
{
if (INVALID_RECT(mbr))
return (REALTYPE) 0;
return (mbr->bound[DIMS_NUMB] - mbr->bound[0]) * (mbr->bound[DIMS_NUMB+1] - mbr->bound[1]);
}
REALTYPE RTreeRectVolume( RTREEMBR *mbr )
{
int i;
REALTYPE vol = (REALTYPE) 1;
if (INVALID_RECT(mbr))
return (REALTYPE) 0;
for(i=0; i<DIMS_NUMB; i++)
vol *= (mbr->bound[i+DIMS_NUMB] - mbr->bound[i]);
assert(vol >= 0.0);
return vol;
}
const double UnitSphereVolumes[] = {
0.000000,
2.000000,
3.141593,
4.188790,
4.934802,
5.263789,
5.167713,
4.724766,
4.058712,
3.298509,
2.550164,
1.884104,
1.335263,
0.910629,
0.599265, /* dimension 14 */
0.381443,
0.235331,
0.140981, /* dimension 17 */
0.082146,
0.046622,
0.025807, /* dimension 20 */
};
#if DIMS_NUMB > 20
#error "not enough precomputed sphere volumes"
#endif
#define UnitSphereVolume UnitSphereVolumes[DIMS_NUMB]
REALTYPE RTreeRectSphericalVolume( RTREEMBR *mbr )
{
int i;
double sum_of_squares=0, radius;
if (INVALID_RECT(mbr))
return (REALTYPE) 0;
for (i=0; i<DIMS_NUMB; i++) {
double half_extent = (mbr->bound[i+DIMS_NUMB] - mbr->bound[i]) / 2;
sum_of_squares += half_extent * half_extent;
}
radius = sqrt(sum_of_squares);
return (REALTYPE)(pow(radius, DIMS_NUMB) * UnitSphereVolume);
}
REALTYPE RTreeRectSurfaceArea( RTREEMBR *mbr )
{
int i, j;
REALTYPE sum = (REALTYPE) 0;
if (INVALID_RECT(mbr))
return (REALTYPE) 0;
for (i=0; i<DIMS_NUMB; i++) {
REALTYPE face_area = (REALTYPE)1;
for (j=0; j<DIMS_NUMB; j++)
if(i != j) {
REALTYPE j_extent = mbr->bound[j+DIMS_NUMB] - mbr->bound[j];
face_area *= j_extent;
}
sum += face_area;
}
return 2 * sum;
}
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;
}
int RTreeOverlap( RTREEMBR *rc1, RTREEMBR *rc2)
{
int i, j;
assert(rc1 && rc2);
for (i=0; i<DIMS_NUMB; i++)
{
j = i + DIMS_NUMB;
if (rc1->bound[i] > rc2->bound[j] || rc2->bound[i] > rc1->bound[j])
return FALSE;
}
return TRUE;
}
int RTreeContained( RTREEMBR *r, RTREEMBR *s)
{
int i, j, result;
assert(r && s);
if (INVALID_RECT(r))
return TRUE;
if (INVALID_RECT(s))
return FALSE;
result = TRUE;
for (i = 0; i < DIMS_NUMB; i++)
{
j = i + DIMS_NUMB;
result = result && r->bound[i] >= s->bound[i] && r->bound[j] <= s->bound[j];
}
return result;
}
void RTreeSplitNode(HRTREEROOT root, RTREENODE *node, RTREEBRANCH *br, RTREENODE **new_node)
{
RTREEPARTITION *p;
int level;
assert(node && br);
level = node->level;
_RTreeGetBranches(root, node, br);
p = &root->Partitions[0];
_RTreeMethodZero(root, p, (level>0 ? MINNODEFILL : MINLEAFFILL));
*new_node = RTreeNewNode();
(*new_node)->level = node->level = level;
_RTreeLoadNodes(root, node, *new_node, p);
assert(node->count+(*new_node)->count == p->total);
}
void RTreeInitNode( RTREENODE *node )
{
int i;
node->count = 0;
node->level = -1;
for (i = 0; i < MAXCARD; i++)
_RTreeInitBranch(&(node->branch[i]));
}
RTREENODE *RTreeNewNode(void)
{
RTREENODE *node = (RTREENODE*) malloc(sizeof(RTREENODE));
assert(node);
RTreeInitNode(node);
return node;
}
void RTreeFreeNode( RTREENODE *node )
{
assert(node);
free(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\n", node->level, node->count, (unsigned int) node);
for (i=0; i<node->count; i++)
{
if(node->level == 0) {
fprintf (stdout, "\t%ld: data = %ld\n", i, (unsigned int)node->branch[i].child);
}
else {
_RTreeTabIn(depth);
fprintf (stdout, "branch %d\n", i);
_RTreePrintBranch(&node->branch[i], depth+1);
}
}
#pragma warning(pop)
}
RTREEMBR RTreeNodeCover( RTREENODE *node )
{
int i, first_time=1;
RTREEMBR mbr;
assert(node);
RTreeInitRect(&mbr);
for (i = 0; i < MAXKIDS(node); i++)
{
if (node->branch[i].child)
{
if (first_time)
{
mbr = node->branch[i].mbr;
first_time = 0;
}
else
mbr = RTreeCombineRect(&mbr, &(node->branch[i].mbr));
}
}
return mbr;
}
int RTreePickBranch( RTREEMBR *mbr, RTREENODE *node)
{
RTREEMBR *r;
int i, first_time = 1;
REALTYPE increase, bestIncr=(REALTYPE)-1, area, bestArea=0;
int best=0;
RTREEMBR tmp_rect;
assert(mbr && node);
for (i=0; i<MAXKIDS(node); i++)
{
if (node->branch[i].child)
{
r = &node->branch[i].mbr;
area = RTreeRectSphericalVolume(r);
tmp_rect = RTreeCombineRect(mbr, 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;
}
int RTreeAddBranch(HRTREEROOT root, RTREEBRANCH *br, RTREENODE *node, RTREENODE **new_node)
{
int i;
assert(br && node);
if (node->count < MAXKIDS(node))
{
for (i = 0; i < MAXKIDS(node); i++)
{
if (node->branch[i].child == NULL)
{
node->branch[i] = *br;
node->count++;
break;
}
}
return 0;
}
assert(new_node);
RTreeSplitNode(root, node, br, new_node);
return 1;
}
void RTreeDisconnectBranch( RTREENODE *node, int i )
{
assert(node && i>=0 && i<MAXKIDS(node));
assert(node->branch[i].child);
_RTreeInitBranch(&(node->branch[i]));
node->count--;
}
void RTreeDestroyNode ( RTREENODE *node )
{
int i;
if (node->level > 0)
{
for ( i = 0; i < NODECARD; i++)
{
if ( node->branch[i].child )
RTreeDestroyNode ( node->branch[i].child );
}
}
RTreeFreeNode( node );
}
HRTREEROOT RTreeCreate(PFNRTreeSearchCallback pfnSearchCallback)
{
RTREEROOT * root = (RTREEROOT*) malloc(sizeof(RTREEROOT));
assert(root);
root->root_node = RTreeNewNode();
assert(root->root_node);
root->root_node->level = 0;
root->pfnCallback = pfnSearchCallback;
return root;
}
void RTreeDestroy(HRTREEROOT root)
{
RTreeDestroyNode (root->root_node);
root->root_node = 0;
free(root);
}
int RTreeSearch(HRTREEROOT root, RTREEMBR *mbr, void* pfnSearchCallbackParam)
{
return _RTreeSearchRect(root->root_node, mbr, root->pfnCallback, pfnSearchCallbackParam);
}
int RTreeInsert(HRTREEROOT root, RTREEMBR *mbr, void* tid, int level)
{
#ifdef _DEBUG
int i;
#endif
RTREENODE *newroot;
RTREENODE *newnode;
RTREEBRANCH b;
assert(mbr && root);
assert(level >= 0 && level <= root->root_node->level);
#ifdef _DEBUG
for (i=0; i<DIMS_NUMB; i++)
assert(mbr->bound[i] <= mbr->bound[DIMS_NUMB+i]);
#endif
if (_RTreeInsertRect(root, mbr, tid, root->root_node, &newnode, level))
{
newroot = RTreeNewNode();
newroot->level = root->root_node->level + 1;
b.mbr = RTreeNodeCover(root->root_node);
b.child = root->root_node;
RTreeAddBranch(root, &b, newroot, NULL);
b.mbr = RTreeNodeCover(newnode);
b.child = newnode;
RTreeAddBranch(root, &b, newroot, NULL);
root->root_node = newroot;
return 1;
}
return 0;
}
int RTreeDelete(HRTREEROOT root, RTREEMBR *mbr, void* tid)
{
int i;
RTREENODE *tmp_nptr = NULL;
RTREELISTNODE *reInsertList = NULL;
RTREELISTNODE *e;
assert(mbr && root && root->root_node);
if (!_RTreeDeleteRect(mbr, tid, root->root_node, &reInsertList))
{
while (reInsertList)
{
tmp_nptr = reInsertList->node;
#pragma warning(push)
#pragma warning( disable : 4311 )
for (i = 0; i < MAXKIDS(tmp_nptr); i++)
{
if (tmp_nptr->branch[i].child)
{
RTreeInsert(root, &(tmp_nptr->branch[i].mbr), (void*)tmp_nptr->branch[i].child, tmp_nptr->level);
}
}
#pragma warning(pop)
e = reInsertList;
reInsertList = reInsertList->next;
RTreeFreeNode(e->node);
_RTreeFreeListNode(e);
}
if (root->root_node->count == 1 && root->root_node->level > 0)
{
for (i = 0; i < NODECARD; i++)
{
tmp_nptr = root->root_node->branch[i].child;
if(tmp_nptr)
break;
}
assert(tmp_nptr);
RTreeFreeNode(root->root_node);
root->root_node = tmp_nptr;
}
return 0;
}
return 1;
}
#ifndef RTREE_H_INCLUDED
#define RTREE_H_INCLUDED
#ifdef __cplusplus
extern "C" {
#endif
#define PAGE_SIZE 512
#define DIMS_NUMB 2
#define SIDES_NUMB 2*DIMS_NUMB
typedef double REALTYPE;
#ifndef TRUE
#define TRUE 1
#define FALSE 0
#endif
typedef struct _RTREEMBR
{
REALTYPE bound[SIDES_NUMB];
}RTREEMBR;
typedef struct _RTREEBRANCH
{
RTREEMBR mbr;
struct _RTREENODE *child;
}RTREEBRANCH;
#define MAXCARD (int)((PAGE_SIZE-(2*sizeof(int))) / sizeof(RTREEBRANCH))
typedef struct _RTREENODE* HRTREENODE;
typedef struct _RTREEROOT* HRTREEROOT;
typedef int (*PFNRTreeSearchCallback)(void* data_id, void* pfnParam);
void RTreeInitRect( RTREEMBR *mbr);
RTREEMBR RTreeNullRect(void);
void RTreePrintRect( RTREEMBR *mbr, int depth );
REALTYPE RTreeRectArea( RTREEMBR *mbr );
REALTYPE RTreeRectVolume( RTREEMBR *mbr );
REALTYPE RTreeRectSphericalVolume( RTREEMBR *mbr );
REALTYPE RTreeRectSurfaceArea( RTREEMBR *mbr );
RTREEMBR RTreeCombineRect( RTREEMBR *rc1, RTREEMBR *rc2 );
int RTreeOverlap( RTREEMBR *rc1, RTREEMBR *rc2);
int RTreeContained( RTREEMBR *r, RTREEMBR *s);
void RTreeSplitNode(HRTREEROOT root, HRTREENODE node, RTREEBRANCH *br, HRTREENODE *new_node);
void RTreeInitNode( HRTREENODE node );
HRTREENODE RTreeNewNode(void);
void RTreeFreeNode( HRTREENODE node );
void RTreePrintNode( HRTREENODE node, int depth );
RTREEMBR RTreeNodeCover( HRTREENODE node );
int RTreePickBranch( RTREEMBR *mbr, HRTREENODE node);
int RTreeAddBranch(HRTREEROOT root, RTREEBRANCH *br, HRTREENODE node, HRTREENODE *new_node);
void RTreeDisconnectBranch( HRTREENODE node, int i );
void RTreeDestroyNode ( HRTREENODE node );
HRTREEROOT RTreeCreate(PFNRTreeSearchCallback pfnSearchCallback);
void RTreeDestroy(HRTREEROOT root);
int RTreeSearch(HRTREEROOT root, RTREEMBR *mbr, void* pfnSearchCallbackParam);
int RTreeInsert(HRTREEROOT root, RTREEMBR *data_mbr, void* data_id, int level);
int RTreeDelete(HRTREEROOT root, RTREEMBR *data_mbr, void* data_id);
#ifdef __cplusplus
}
#endif
#endif
#include <stdio.h>
#include "rtree.h"
RTREEMBR mbrs[] = {
{ {0, 0, 2, 2} }, /* xmin, ymin, zmin, xmax, ymax, zmax (for 3 dimensional RTree) */
{ {5, 5, 7, 7} },
{ {8, 5, 9, 6} },
{ {4, 2, 6, 4} },
{ {6, 3, 8, 5} },
{ {7, 1, 9, 2} }
};
int nmbr = sizeof(mbrs) / sizeof(mbrs[0]);
RTREEMBR search_mbr = {
{6, 4, 10, 6}
};
int MySearchCallback(int id, void* arg)
{
fprintf (stdout, "Searched data id: %d\n", id);
return 1; /* 继续 */
}
int main()
{
HRTREEROOT root = RTreeCreate(MySearchCallback);
int i, nhits;
fprintf (stdout, "nmbr = %d\n", nmbr);
for(i=0; i<nmbr; i++){
RTreeInsert(root, &mbrs[i], /* mbr被插入 */
(void*)(i+1), /* i+1 mbr ID,ID必须永远是零 */
0 /* 这意味着添加从根总是零 */
);
}
nhits = RTreeSearch(root, &search_mbr, MySearchCallback);
fprintf (stdout, "Search resulted is %d hits before delete 1\n", nhits);
/* delete first shape: 1 */
fprintf (stdout, "delete id=3 from tree\n");
i = RTreeDelete(root, &mbrs[1], (void*)2);
nhits = RTreeSearch(root, &search_mbr, MySearchCallback);
fprintf (stdout, "Search resulted is %d hits after delete 1\n", nhits);
RTreeDestroy (root);
return 0;
}
