60 RTreeInitLeafBranch, RTreeInitNodeBranchM, RTreeInitNodeBranchF
73 RTreeInitBranch[type](&(n->
branch[i]), t);
120 for (i = 0; i <
MAXCARD; i++) {
138 int i, first_time = 1;
140 if ((n)->
level > 0) {
182 RectReal increase, bestIncr = -1, area, bestArea = 0;
183 int best = 0, bestoverlap;
205 if (overlap < bestoverlap) {
207 bestoverlap = overlap;
211 else if (overlap == bestoverlap) {
213 if (increase < bestIncr) {
218 else if (increase == bestIncr && area < bestArea) {
239 int i, first_time = 1;
246 return RTreePickLeafBranch(r, n, t);
254 if (increase < bestIncr || first_time) {
260 else if (increase == bestIncr && area < bestArea) {
272 if ((n)->level > 0) {
273 assert(n && i >= 0 && i < t->nodecard);
276 RTreeInitNodeBranchM(&(n->
branch[i]), t);
278 RTreeInitNodeBranchF(&(n->
branch[i]), t);
281 assert(n && i >= 0 && i < t->leafcard);
283 RTreeInitLeafBranch(&(n->
branch[i]), t);
296 for (i = 0; i < nodes; i++) {
318 static void RTreeSwapDist(
struct dist *a,
struct dist *b)
330 static int RTreeDistIsSorted(
struct dist *d,
int first,
int last)
334 for (i = first; i < last; i++) {
335 if (d[i].distance > d[i + 1].distance)
345 static int RTreePartitionDist(
struct dist *d,
int first,
int last)
347 int pivot, mid = ((first + last) >> 1);
350 if (last - first == 1) {
351 if (d[first].distance > d[last].distance) {
352 RTreeSwapDist(&(d[first]), &(d[last]));
358 larger = pivot = mid;
360 if (d[first].distance > d[mid].distance) {
361 larger = pivot = first;
365 if (d[larger].distance > d[last].distance) {
368 if (d[smaller].distance > d[last].distance) {
374 RTreeSwapDist(&(d[pivot]), &(d[last]));
379 while (first < last) {
380 if (d[first].distance <= d[last].distance) {
381 if (pivot != first) {
382 RTreeSwapDist(&(d[pivot]), &(d[first]));
390 RTreeSwapDist(&(d[pivot]), &(d[last]));
400 static void RTreeQuicksortDist(
struct dist *d,
int n)
402 int pivot, first, last;
413 first = s_first[stacksize];
414 last = s_last[stacksize];
416 if (!RTreeDistIsSorted(d, first, last)) {
418 pivot = RTreePartitionDist(d, first, last);
420 s_first[stacksize] = first;
421 s_last[stacksize] = pivot - 1;
424 s_first[stacksize] = pivot + 1;
425 s_last[stacksize] = last;
456 l = RTreeNewListBranch(t);
472 int i, j, maxkids, type;
474 struct dist rdist[MAXCARD + 1];
481 maxkids =
MAXKIDS((n)->level, t);
489 for (j = 0; j < t->
ndims; j++) {
494 for (i = 0; i < maxkids; i++) {
496 rdist[i].distance = 0;
498 for (j = 0; j < t->
ndims; j++) {
502 delta = center_n[j] - center_r;
503 rdist[i].distance += delta * delta;
506 RTreeInitBranch[type](&(n->
branch[i]), t);
511 rdist[maxkids].distance = 0;
512 for (j = 0; j < t->
ndims; j++) {
516 delta = center_n[j] - center_r;
517 rdist[maxkids].distance += delta * delta;
519 rdist[maxkids].id = maxkids;
522 RTreeQuicksortDist(rdist, maxkids);
526 RTreeReInsertBranch(t->
BranchBuf[rdist[maxkids - i].id], n->
level, ee, t);
529 for (i = 0; i < maxkids - FORCECARD + 1; i++) {
532 n->
count = maxkids - FORCECARD + 1;
548 maxkids =
MAXKIDS((n)->level, t);
550 if (n->
count < maxkids) {
551 if ((n)->level > 0) {
552 for (i = 0; i < maxkids; i++) {
563 else if ((n)->level == 0) {
564 for (i = 0; i < maxkids; i++) {
579 RTreeRemoveBranches(n, b, ee, cover, t);
580 overflow[n->
level] = 0;
606 for (i = 0; i < depth; i++)
625 fprintf(stdout,
"node");
627 fprintf(stdout,
" LEAF");
628 else if (n->
level > 0)
629 fprintf(stdout,
" NONLEAF");
631 fprintf(stdout,
" TYPE=?");
632 fprintf(stdout,
" level=%d count=%d", n->
level, n->
count);
634 for (i = 0; i < maxkids; i++) {
638 fprintf(stdout,
"\t%d: data id = %d\n", i,
643 fprintf(stdout,
"branch %d\n", i);
644 RTreePrintBranch(&(n->
branch[i]), depth + 1, t);
int RTreePickBranch(struct RTree_Rect *r, struct RTree_Node *n, struct RTree *t)
struct RTree_Rect rect_0 rect_1 upperrect orect
#define RTreeCopyRect(r1, r2, t)
void RTreeFreeNode(struct RTree_Node *n)
RectReal RTreeRectSphericalVolume(struct RTree_Rect *, struct RTree *)
void RTreeNodeCover(struct RTree_Node *n, struct RTree_Rect *r, struct RTree *t)
void RTreeDisconnectBranch(struct RTree_Node *n, int i, struct RTree *t)
void RTreeCopyNode(struct RTree_Node *n1, struct RTree_Node *n2, struct RTree *t)
struct RTree_ListBranch * next
#define MAXKIDS(level, t)
void RTreeSplitNode(struct RTree_Node *, struct RTree_Branch *, struct RTree_Node *, struct RTree *)
void RTreeInitNode(struct RTree *t, struct RTree_Node *n, int type)
rt_valid_child_fn * valid_child
void RTreeTabIn(int depth)
void RTreeDestroyNode(struct RTree_Node *n, int nodes)
void RTreeCopyBranch(struct RTree_Branch *b1, struct RTree_Branch *b2, struct RTree *t)
void RTreePrintNode(struct RTree_Node *n, int depth, struct RTree *t)
int RTreeAddBranch(struct RTree_Branch *b, struct RTree_Node *n, struct RTree_Node **newnode, struct RTree_ListBranch **ee, struct RTree_Rect *cover, char *overflow, struct RTree *t)
unsigned char ndims_alloc
#define assert(condition)
void RTreeFreeBoundary(struct RTree_Rect *r)
Delete the boundary of a rectangle.
void RTreeCombineRect(struct RTree_Rect *, struct RTree_Rect *, struct RTree_Rect *, struct RTree *)
struct RTree_Branch * BranchBuf
struct RTree_Branch * branch
void RTreeInitRect(struct RTree_Rect *, struct RTree *)
Initialize a rectangle to have all 0 coordinates.
int RTreeExpandRect(struct RTree_Rect *, struct RTree_Rect *, struct RTree *)
struct RTree_Node * RTreeAllocNode(struct RTree *t, int level)
RectReal * RTreeAllocBoundary(struct RTree *t)
Allocate the boundary array of a rectangle for a given tree.
int RTreeOverlap(struct RTree_Rect *r, struct RTree_Rect *s, struct RTree *t)
void RTreePrintRect(struct RTree_Rect *R, int depth, struct RTree *t)