node.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 #include <stdio.h>
00018 #include <stdlib.h>
00019 #include "assert.h"
00020 #include "index.h"
00021 #include "card.h"
00022 
00023 /* Initialize one branch cell in a node. */
00024 static void RTreeInitBranch(struct Branch *b)
00025 {
00026         RTreeInitRect(&(b->rect));
00027         b->child = NULL;
00028 }
00029 
00030 /* Initialize a Node structure. */
00031 void RTreeInitNode(struct Node *N)
00032 {
00033         register struct Node *n = N;
00034         register int i;
00035         n->count = 0;
00036         n->level = -1;
00037         for (i = 0; i < MAXCARD; i++)
00038                 RTreeInitBranch(&(n->branch[i]));
00039 }
00040 
00041 /* Make a new node and initialize to have all branch cells empty. */
00042 struct Node * RTreeNewNode(void)
00043 {
00044         register struct Node *n;
00045 
00046         /* n = new Node; */
00047         n = (struct Node*)malloc(sizeof(struct Node));
00048         assert(n);
00049         RTreeInitNode(n);
00050         return n;
00051 }
00052 
00053 void RTreeFreeNode(struct Node *p)
00054 {
00055         assert(p);
00056         /* delete p; */
00057         free(p);
00058 }
00059 
00060 static void RTreePrintBranch(struct Branch *b, int depth)
00061 {
00062         RTreePrintRect(&(b->rect), depth);
00063         RTreePrintNode(b->child, depth);
00064 }
00065 
00066 extern void RTreeTabIn(int depth)
00067 {
00068         int i;
00069         for(i=0; i<depth; i++)
00070                 putchar('\t');
00071 }
00072 
00073 /* Print out the data in a node. */
00074 void RTreePrintNode(struct Node *n, int depth)
00075 {
00076         int i;
00077         assert(n);
00078 
00079         RTreeTabIn(depth);
00080         fprintf (stdout, "node");
00081         if (n->level == 0)
00082                 fprintf (stdout, " LEAF");
00083         else if (n->level > 0)
00084                 fprintf (stdout, " NONLEAF");
00085         else
00086                 fprintf (stdout, " TYPE=?");
00087         fprintf (stdout, "  level=%d  count=%d  address=%o\n", n->level, n->count, (unsigned) n);
00088 
00089         for (i=0; i<n->count; i++)
00090         {
00091                 if(n->level == 0) {
00092                         /* RTreeTabIn(depth); */
00093                         /* fprintf (stdout, "\t%d: data = %d\n", i, n->branch[i].child); */
00094                 }
00095                 else {
00096                         RTreeTabIn(depth);
00097                         fprintf (stdout, "branch %d\n", i);
00098                         RTreePrintBranch(&n->branch[i], depth+1);
00099                 }
00100         }
00101 }
00102 
00103 /*
00104  * Find the smallest rectangle that includes all rectangles in
00105  * branches of a node.
00106 */
00107 struct Rect RTreeNodeCover(struct Node *N)
00108 {
00109         register struct Node *n = N;
00110         register int i, first_time=1;
00111         struct Rect r;
00112         assert(n);
00113 
00114         RTreeInitRect(&r);
00115         for (i = 0; i < MAXKIDS(n); i++)
00116                 if (n->branch[i].child)
00117                 {
00118                         if (first_time)
00119                         {
00120                                 r = n->branch[i].rect;
00121                                 first_time = 0;
00122                         }
00123                         else
00124                                 r = RTreeCombineRect(&r, &(n->branch[i].rect));
00125                 }
00126         return r;
00127 }
00128 
00129 /*
00130  * Pick a branch.  Pick the one that will need the smallest increase
00131  * in area to accomodate the new rectangle.  This will result in the
00132  * least total area for the covering rectangles in the current node.
00133  * In case of a tie, pick the one which was smaller before, to get
00134  * the best resolution when searching.
00135  */
00136 int RTreePickBranch(struct Rect *R, struct Node *N)
00137 {
00138         register struct Rect *r = R;
00139         register struct Node *n = N;
00140         register struct Rect *rr;
00141         register int i, first_time=1;
00142         RectReal increase, bestIncr=(RectReal)-1, area, bestArea=0;
00143         int best=0;
00144         struct Rect tmp_rect;
00145         assert(r && n);
00146 
00147         for (i=0; i<MAXKIDS(n); i++)
00148         {
00149                 if (n->branch[i].child)
00150                 {
00151                         rr = &n->branch[i].rect;
00152                         area = RTreeRectSphericalVolume(rr);
00153                         tmp_rect = RTreeCombineRect(r, rr);
00154                         increase = RTreeRectSphericalVolume(&tmp_rect) - area;
00155                         if (increase < bestIncr || first_time)
00156                         {
00157                                 best = i;
00158                                 bestArea = area;
00159                                 bestIncr = increase;
00160                                 first_time = 0;
00161                         }
00162                         else if (increase == bestIncr && area < bestArea)
00163                         {
00164                                 best = i;
00165                                 bestArea = area;
00166                                 bestIncr = increase;
00167                         }
00168                 }
00169         }
00170         return best;
00171 }
00172 
00173 /*
00174  * Add a branch to a node.  Split the node if necessary.
00175  * Returns 0 if node not split.  Old node updated.
00176  * Returns 1 if node split, sets *new_node to address of new node.
00177  * Old node updated, becomes one of two.
00178  */
00179 int RTreeAddBranch(struct Branch *B, struct Node *N, struct Node **New_node)
00180 {
00181         register struct Branch *b = B;
00182         register struct Node *n = N;
00183         register struct Node **new_node = New_node;
00184         register int i;
00185 
00186         assert(b);
00187         assert(n);
00188 
00189         if (n->count < MAXKIDS(n))  /* split won't be necessary */
00190         {
00191                 for (i = 0; i < MAXKIDS(n); i++)  /* find empty branch */
00192                 {
00193                         if (n->branch[i].child == NULL)
00194                         {
00195                                 n->branch[i] = *b;
00196                                 n->count++;
00197                                 break;
00198                         }
00199                 }
00200                 return 0;
00201         }
00202         else
00203         {
00204                 assert(new_node);
00205                 RTreeSplitNode(n, b, new_node);
00206                 return 1;
00207         }
00208 }
00209 
00210 /* Disconnect a dependent node. */
00211 void RTreeDisconnectBranch(struct Node *n, int i)
00212 {
00213         assert(n && i>=0 && i<MAXKIDS(n));
00214         assert(n->branch[i].child);
00215 
00216         RTreeInitBranch(&(n->branch[i]));
00217         n->count--;
00218 }
00219 
00220 /* Destroy (free) node recursively. */
00221 void RTreeDestroyNode (struct Node *n)
00222 {
00223         int i;
00224 
00225         if (n->level > 0) { /* it is not leaf -> destroy childs */
00226             for ( i = 0; i < NODECARD; i++) {
00227                 if ( n->branch[i].child ) {
00228                     RTreeDestroyNode ( n->branch[i].child );
00229                 }
00230             }
00231         }
00232 
00233         /* Free this node */
00234         RTreeFreeNode( n );
00235 }
00236 

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