RTree源代码——C语言实现(上)

 /**
　* 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(' ');
}