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

Generated on Sat Oct 24 03:25:20 2009 for GRASS Programmer's Manual by  doxygen 1.6.1