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