split_q.c

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

Generated on Sun Apr 6 17:32:44 2008 for GRASS by  doxygen 1.5.5