00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017 #include <stdio.h>
00018 #include <stdlib.h>
00019 #include "assert.h"
00020 #include "index.h"
00021 #include "card.h"
00022
00023
00024 static void RTreeInitBranch(struct Branch *b)
00025 {
00026 RTreeInitRect(&(b->rect));
00027 b->child = NULL;
00028 }
00029
00030
00031 void RTreeInitNode(struct Node *N)
00032 {
00033 register struct Node *n = N;
00034 register int i;
00035 n->count = 0;
00036 n->level = -1;
00037 for (i = 0; i < MAXCARD; i++)
00038 RTreeInitBranch(&(n->branch[i]));
00039 }
00040
00041
00042 struct Node * RTreeNewNode(void)
00043 {
00044 register struct Node *n;
00045
00046
00047 n = (struct Node*)malloc(sizeof(struct Node));
00048 assert(n);
00049 RTreeInitNode(n);
00050 return n;
00051 }
00052
00053 void RTreeFreeNode(struct Node *p)
00054 {
00055 assert(p);
00056
00057 free(p);
00058 }
00059
00060 static void RTreePrintBranch(struct Branch *b, int depth)
00061 {
00062 RTreePrintRect(&(b->rect), depth);
00063 RTreePrintNode(b->child, depth);
00064 }
00065
00066 extern void RTreeTabIn(int depth)
00067 {
00068 int i;
00069 for(i=0; i<depth; i++)
00070 putchar('\t');
00071 }
00072
00073
00074 void RTreePrintNode(struct Node *n, int depth)
00075 {
00076 int i;
00077 assert(n);
00078
00079 RTreeTabIn(depth);
00080 fprintf (stdout, "node");
00081 if (n->level == 0)
00082 fprintf (stdout, " LEAF");
00083 else if (n->level > 0)
00084 fprintf (stdout, " NONLEAF");
00085 else
00086 fprintf (stdout, " TYPE=?");
00087 fprintf (stdout, " level=%d count=%d address=%o\n", n->level, n->count, (unsigned) n);
00088
00089 for (i=0; i<n->count; i++)
00090 {
00091 if(n->level == 0) {
00092
00093
00094 }
00095 else {
00096 RTreeTabIn(depth);
00097 fprintf (stdout, "branch %d\n", i);
00098 RTreePrintBranch(&n->branch[i], depth+1);
00099 }
00100 }
00101 }
00102
00103
00104
00105
00106
00107 struct Rect RTreeNodeCover(struct Node *N)
00108 {
00109 register struct Node *n = N;
00110 register int i, first_time=1;
00111 struct Rect r;
00112 assert(n);
00113
00114 RTreeInitRect(&r);
00115 for (i = 0; i < MAXKIDS(n); i++)
00116 if (n->branch[i].child)
00117 {
00118 if (first_time)
00119 {
00120 r = n->branch[i].rect;
00121 first_time = 0;
00122 }
00123 else
00124 r = RTreeCombineRect(&r, &(n->branch[i].rect));
00125 }
00126 return r;
00127 }
00128
00129
00130
00131
00132
00133
00134
00135
00136 int RTreePickBranch(struct Rect *R, struct Node *N)
00137 {
00138 register struct Rect *r = R;
00139 register struct Node *n = N;
00140 register struct Rect *rr;
00141 register int i, first_time=1;
00142 RectReal increase, bestIncr=(RectReal)-1, area, bestArea=0;
00143 int best=0;
00144 struct Rect tmp_rect;
00145 assert(r && n);
00146
00147 for (i=0; i<MAXKIDS(n); i++)
00148 {
00149 if (n->branch[i].child)
00150 {
00151 rr = &n->branch[i].rect;
00152 area = RTreeRectSphericalVolume(rr);
00153 tmp_rect = RTreeCombineRect(r, rr);
00154 increase = RTreeRectSphericalVolume(&tmp_rect) - area;
00155 if (increase < bestIncr || first_time)
00156 {
00157 best = i;
00158 bestArea = area;
00159 bestIncr = increase;
00160 first_time = 0;
00161 }
00162 else if (increase == bestIncr && area < bestArea)
00163 {
00164 best = i;
00165 bestArea = area;
00166 bestIncr = increase;
00167 }
00168 }
00169 }
00170 return best;
00171 }
00172
00173
00174
00175
00176
00177
00178
00179 int RTreeAddBranch(struct Branch *B, struct Node *N, struct Node **New_node)
00180 {
00181 register struct Branch *b = B;
00182 register struct Node *n = N;
00183 register struct Node **new_node = New_node;
00184 register int i;
00185
00186 assert(b);
00187 assert(n);
00188
00189 if (n->count < MAXKIDS(n))
00190 {
00191 for (i = 0; i < MAXKIDS(n); i++)
00192 {
00193 if (n->branch[i].child == NULL)
00194 {
00195 n->branch[i] = *b;
00196 n->count++;
00197 break;
00198 }
00199 }
00200 return 0;
00201 }
00202 else
00203 {
00204 assert(new_node);
00205 RTreeSplitNode(n, b, new_node);
00206 return 1;
00207 }
00208 }
00209
00210
00211 void RTreeDisconnectBranch(struct Node *n, int i)
00212 {
00213 assert(n && i>=0 && i<MAXKIDS(n));
00214 assert(n->branch[i].child);
00215
00216 RTreeInitBranch(&(n->branch[i]));
00217 n->count--;
00218 }
00219
00220
00221 void RTreeDestroyNode (struct Node *n)
00222 {
00223 int i;
00224
00225 if (n->level > 0) {
00226 for ( i = 0; i < NODECARD; i++) {
00227 if ( n->branch[i].child ) {
00228 RTreeDestroyNode ( n->branch[i].child );
00229 }
00230 }
00231 }
00232
00233
00234 RTreeFreeNode( n );
00235 }
00236