GRASS Programmer's Manual
6.4.2(2012)
|
00001 00002 /**************************************************************************** 00003 * MODULE: R-Tree library 00004 * 00005 * AUTHOR(S): Antonin Guttman - original code 00006 * Daniel Green (green@superliminal.com) - major clean-up 00007 * and implementation of bounding spheres 00008 * 00009 * PURPOSE: Multidimensional index 00010 * 00011 * COPYRIGHT: (C) 2001 by the GRASS Development Team 00012 * 00013 * This program is free software under the GNU General Public 00014 * License (>=v2). Read the file COPYING that comes with GRASS 00015 * for details. 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 /* variables for finding a partition */ 00030 struct PartitionVars Partitions[METHODS]; 00031 00032 /*----------------------------------------------------------------------------- 00033 | Load branch buffer with branches from full node plus the extra branch. 00034 -----------------------------------------------------------------------------*/ 00035 static void RTreeGetBranches(struct Node *n, struct Branch *b) 00036 { 00037 int i; 00038 00039 assert(n); 00040 assert(b); 00041 00042 /* load the branch buffer */ 00043 for (i = 0; i < MAXKIDS(n); i++) { 00044 assert(n->branch[i].child); /* n should have every entry full */ 00045 BranchBuf[i] = n->branch[i]; 00046 } 00047 BranchBuf[MAXKIDS(n)] = *b; 00048 BranchCount = MAXKIDS(n) + 1; 00049 00050 /* calculate rect containing all in the set */ 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 | Put a branch in one of the groups. 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 | Pick two rects from set to be the first elements of the two groups. 00088 | Pick the two that waste the most area if covered by a single rectangle. 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 | Copy branches from the buffer into two nodes according to the partition. 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 | Initialize a PartitionVars structure. 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 | Print out data for a partition from PartitionVars struct. 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 | Method #0 for choosing a partition: 00210 | As the seeds for the two groups, pick the two rects that would waste the 00211 | most area if covered by a single rectangle, i.e. evidently the worst pair 00212 | to have in the same group. 00213 | Of the remaining, one at a time is chosen to be put in one of the two groups. 00214 | The one chosen is the one with the greatest difference in area expansion 00215 | depending on which group - the rect most strongly attracted to one group 00216 | and repelled from the other. 00217 | If one group gets too full (more would force other group to violate min 00218 | fill requirement) then other group gets the rest. 00219 | These last are the ones that can go in either group most easily. 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 /* if one group too full, put remaining rects in the other */ 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 | Split a node. 00288 | Divides the nodes branches and the extra one between two nodes. 00289 | Old node is one of the new ones, and one really new one is created. 00290 | Tries more than one method for choosing a partition, uses best result. 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 /* load all the branches into a buffer, initialize old node */ 00301 level = n->level; 00302 RTreeGetBranches(n, b); 00303 00304 /* find partition */ 00305 p = &Partitions[0]; 00306 /* Note: can't use MINFILL(n) below since n was cleared by GetBranches() */ 00307 RTreeMethodZero(p, level > 0 ? MinNodeFill : MinLeafFill); 00308 00309 /* 00310 * put branches from buffer into 2 nodes 00311 * according to chosen partition 00312 */ 00313 *nn = RTreeNewNode(); 00314 (*nn)->level = n->level = level; 00315 RTreeLoadNodes(n, *nn, p); 00316 assert(n->count + (*nn)->count == p->total); 00317 }