00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018 #include <stdio.h>
00019 #include "assert.h"
00020 #include "index.h"
00021 #include "card.h"
00022 #include "split_q.h"
00023
00024 struct Branch BranchBuf[MAXCARD + 1];
00025 int BranchCount;
00026 struct Rect CoverSplit;
00027 RectReal CoverSplitArea;
00028
00029
00030 struct PartitionVars Partitions[METHODS];
00031
00032
00033
00034
00035 static void RTreeGetBranches(struct Node *n, struct Branch *b)
00036 {
00037 int i;
00038
00039 assert(n);
00040 assert(b);
00041
00042
00043 for (i = 0; i < MAXKIDS(n); i++) {
00044 assert(n->branch[i].child);
00045 BranchBuf[i] = n->branch[i];
00046 }
00047 BranchBuf[MAXKIDS(n)] = *b;
00048 BranchCount = MAXKIDS(n) + 1;
00049
00050
00051 CoverSplit = BranchBuf[0].rect;
00052 for (i = 1; i < MAXKIDS(n) + 1; i++) {
00053 CoverSplit = RTreeCombineRect(&CoverSplit, &BranchBuf[i].rect);
00054 }
00055 CoverSplitArea = RTreeRectSphericalVolume(&CoverSplit);
00056
00057 RTreeInitNode(n);
00058 }
00059
00060
00061
00062
00063
00064
00065
00066 static void RTreeClassify(int i, int group, struct PartitionVars *p)
00067 {
00068 assert(p);
00069 assert(!p->taken[i]);
00070
00071 p->partition[i] = group;
00072 p->taken[i] = TRUE;
00073
00074 if (p->count[group] == 0)
00075 p->cover[group] = BranchBuf[i].rect;
00076 else
00077 p->cover[group] =
00078 RTreeCombineRect(&BranchBuf[i].rect, &p->cover[group]);
00079 p->area[group] = RTreeRectSphericalVolume(&p->cover[group]);
00080 p->count[group]++;
00081 }
00082
00083
00084
00085
00086
00087
00088
00089
00090 static void RTreePickSeeds(struct PartitionVars *p)
00091 {
00092 int i, j, seed0 = 0, seed1 = 0;
00093 RectReal worst, waste, area[MAXCARD + 1];
00094
00095 for (i = 0; i < p->total; i++)
00096 area[i] = RTreeRectSphericalVolume(&BranchBuf[i].rect);
00097
00098 worst = -CoverSplitArea - 1;
00099 for (i = 0; i < p->total - 1; i++) {
00100 for (j = i + 1; j < p->total; j++) {
00101 struct Rect one_rect;
00102
00103 one_rect = RTreeCombineRect(&BranchBuf[i].rect,
00104 &BranchBuf[j].rect);
00105 waste = RTreeRectSphericalVolume(&one_rect) - area[i] - area[j];
00106 if (waste > worst) {
00107 worst = waste;
00108 seed0 = i;
00109 seed1 = j;
00110 }
00111 }
00112 }
00113 RTreeClassify(seed0, 0, p);
00114 RTreeClassify(seed1, 1, p);
00115 }
00116
00117
00118
00119
00120
00121
00122
00123 static void RTreeLoadNodes(struct Node *n, struct Node *q,
00124 struct PartitionVars *p)
00125 {
00126 int i;
00127
00128 assert(n);
00129 assert(q);
00130 assert(p);
00131
00132 for (i = 0; i < p->total; i++) {
00133 assert(p->partition[i] == 0 || p->partition[i] == 1);
00134 if (p->partition[i] == 0)
00135 RTreeAddBranch(&BranchBuf[i], n, NULL);
00136 else if (p->partition[i] == 1)
00137 RTreeAddBranch(&BranchBuf[i], q, NULL);
00138 }
00139 }
00140
00141
00142
00143
00144
00145
00146
00147 static void RTreeInitPVars(struct PartitionVars *p, int maxrects, int minfill)
00148 {
00149 int i;
00150
00151 assert(p);
00152
00153 p->count[0] = p->count[1] = 0;
00154 p->cover[0] = p->cover[1] = RTreeNullRect();
00155 p->area[0] = p->area[1] = (RectReal) 0;
00156 p->total = maxrects;
00157 p->minfill = minfill;
00158 for (i = 0; i < maxrects; i++) {
00159 p->taken[i] = FALSE;
00160 p->partition[i] = -1;
00161 }
00162 }
00163
00164
00165
00166
00167
00168
00169
00170 static void RTreePrintPVars(struct PartitionVars *p)
00171 {
00172 int i;
00173
00174 assert(p);
00175
00176 fprintf(stdout, "\npartition:\n");
00177 for (i = 0; i < p->total; i++) {
00178 fprintf(stdout, "%3d\t", i);
00179 }
00180 fprintf(stdout, "\n");
00181 for (i = 0; i < p->total; i++) {
00182 if (p->taken[i])
00183 fprintf(stdout, " t\t");
00184 else
00185 fprintf(stdout, "\t");
00186 }
00187 fprintf(stdout, "\n");
00188 for (i = 0; i < p->total; i++) {
00189 fprintf(stdout, "%3d\t", p->partition[i]);
00190 }
00191 fprintf(stdout, "\n");
00192
00193 fprintf(stdout, "count[0] = %d area = %f\n", p->count[0], p->area[0]);
00194 fprintf(stdout, "count[1] = %d area = %f\n", p->count[1], p->area[1]);
00195 if (p->area[0] + p->area[1] > 0) {
00196 fprintf(stdout, "total area = %f effectiveness = %3.2f\n",
00197 p->area[0] + p->area[1],
00198 (float)CoverSplitArea / (p->area[0] + p->area[1]));
00199 }
00200 fprintf(stdout, "cover[0]:\n");
00201 RTreePrintRect(&p->cover[0], 0);
00202
00203 fprintf(stdout, "cover[1]:\n");
00204 RTreePrintRect(&p->cover[1], 0);
00205 }
00206
00207
00208
00209
00210
00211
00212
00213
00214
00215
00216
00217
00218
00219
00220
00221 static void RTreeMethodZero(struct PartitionVars *p, int minfill)
00222 {
00223 int i;
00224 RectReal biggestDiff;
00225 int group, chosen = 0, betterGroup = 0;
00226
00227 assert(p);
00228
00229 RTreeInitPVars(p, BranchCount, minfill);
00230 RTreePickSeeds(p);
00231
00232 while (p->count[0] + p->count[1] < p->total
00233 && p->count[0] < p->total - p->minfill
00234 && p->count[1] < p->total - p->minfill) {
00235 biggestDiff = (RectReal) - 1.;
00236 for (i = 0; i < p->total; i++) {
00237 if (!p->taken[i]) {
00238 struct Rect *r, rect_0, rect_1;
00239 RectReal growth0, growth1, diff;
00240
00241 r = &BranchBuf[i].rect;
00242 rect_0 = RTreeCombineRect(r, &p->cover[0]);
00243 rect_1 = RTreeCombineRect(r, &p->cover[1]);
00244 growth0 = RTreeRectSphericalVolume(&rect_0) - p->area[0];
00245 growth1 = RTreeRectSphericalVolume(&rect_1) - p->area[1];
00246 diff = growth1 - growth0;
00247 if (diff >= 0)
00248 group = 0;
00249 else {
00250 group = 1;
00251 diff = -diff;
00252 }
00253
00254 if (diff > biggestDiff) {
00255 biggestDiff = diff;
00256 chosen = i;
00257 betterGroup = group;
00258 }
00259 else if (diff == biggestDiff &&
00260 p->count[group] < p->count[betterGroup]) {
00261 chosen = i;
00262 betterGroup = group;
00263 }
00264 }
00265 }
00266 RTreeClassify(chosen, betterGroup, p);
00267 }
00268
00269
00270 if (p->count[0] + p->count[1] < p->total) {
00271 if (p->count[0] >= p->total - p->minfill)
00272 group = 1;
00273 else
00274 group = 0;
00275 for (i = 0; i < p->total; i++) {
00276 if (!p->taken[i])
00277 RTreeClassify(i, group, p);
00278 }
00279 }
00280
00281 assert(p->count[0] + p->count[1] == p->total);
00282 assert(p->count[0] >= p->minfill && p->count[1] >= p->minfill);
00283 }
00284
00285
00286
00287
00288
00289
00290
00291
00292 void RTreeSplitNode(struct Node *n, struct Branch *b, struct Node **nn)
00293 {
00294 struct PartitionVars *p;
00295 int level;
00296
00297 assert(n);
00298 assert(b);
00299
00300
00301 level = n->level;
00302 RTreeGetBranches(n, b);
00303
00304
00305 p = &Partitions[0];
00306
00307 RTreeMethodZero(p, level > 0 ? MinNodeFill : MinLeafFill);
00308
00309
00310
00311
00312
00313 *nn = RTreeNewNode();
00314 (*nn)->level = n->level = level;
00315 RTreeLoadNodes(n, *nn, p);
00316 assert(n->count + (*nn)->count == p->total);
00317 }