split_q.c

Go to the documentation of this file.
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 }
Generated on Tue Apr 6 13:28:10 2010 for GRASS Programmer's Manual by  doxygen 1.6.3