GRASS Programmer's Manual
6.4.1(2011)
|
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 }