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 /* Make a new index, empty. Consists of a single node. */ 00025 struct Node *RTreeNewIndex(void) 00026 { 00027 struct Node *x; 00028 00029 x = RTreeNewNode(); 00030 x->level = 0; /* leaf */ 00031 return x; 00032 } 00033 00034 /* 00035 * Search in an index tree or subtree for all data retangles that 00036 * overlap the argument rectangle. 00037 * Return the number of qualifying data rects. 00038 */ 00039 int RTreeSearch(struct Node *N, struct Rect *R, SearchHitCallback shcb, 00040 void *cbarg) 00041 { 00042 register struct Node *n = N; 00043 register struct Rect *r = R; /* NOTE: Suspected bug was R sent in as Node* and cast to Rect* here. */ 00044 00045 /* Fix not yet tested. */ 00046 register int hitCount = 0; 00047 register int i; 00048 00049 assert(n); 00050 assert(n->level >= 0); 00051 assert(r); 00052 00053 if (n->level > 0) { /* this is an internal node in the tree */ 00054 for (i = 0; i < NODECARD; i++) 00055 if (n->branch[i].child && RTreeOverlap(r, &n->branch[i].rect)) { 00056 hitCount += RTreeSearch(n->branch[i].child, r, shcb, cbarg); 00057 } 00058 } 00059 else { /* this is a leaf node */ 00060 00061 for (i = 0; i < LEAFCARD; i++) 00062 if (n->branch[i].child && RTreeOverlap(r, &n->branch[i].rect)) { 00063 hitCount++; 00064 if (shcb) /* call the user-provided callback */ 00065 if (!shcb((int)n->branch[i].child, cbarg)) 00066 return hitCount; /* callback wants to terminate search early */ 00067 } 00068 } 00069 return hitCount; 00070 } 00071 00072 /* 00073 * Inserts a new data rectangle into the index structure. 00074 * Recursively descends tree, propagates splits back up. 00075 * Returns 0 if node was not split. Old node updated. 00076 * If node was split, returns 1 and sets the pointer pointed to by 00077 * new_node to point to the new node. Old node updated to become one of two. 00078 * The level argument specifies the number of steps up from the leaf 00079 * level to insert; e.g. a data rectangle goes in at level = 0. 00080 */ 00081 static int RTreeInsertRect2(struct Rect *r, 00082 struct Node *child, struct Node *n, struct Node **new_node, 00083 int level) 00084 { 00085 /* 00086 register struct Rect *r = R; 00087 register int tid = Tid; 00088 register struct Node *n = N, **new_node = New_node; 00089 register int level = Level; 00090 */ 00091 00092 register int i; 00093 struct Branch b; 00094 struct Node *n2; 00095 00096 assert(r && n && new_node); 00097 assert(level >= 0 && level <= n->level); 00098 00099 /* Still above level for insertion, go down tree recursively */ 00100 if (n->level > level) { 00101 i = RTreePickBranch(r, n); 00102 if (!RTreeInsertRect2(r, child, n->branch[i].child, &n2, level)) { 00103 /* child was not split */ 00104 n->branch[i].rect = RTreeCombineRect(r, &(n->branch[i].rect)); 00105 return 0; 00106 } 00107 else { /* child was split */ 00108 00109 n->branch[i].rect = RTreeNodeCover(n->branch[i].child); 00110 b.child = n2; 00111 b.rect = RTreeNodeCover(n2); 00112 return RTreeAddBranch(&b, n, new_node); 00113 } 00114 } 00115 00116 /* Have reached level for insertion. Add rect, split if necessary */ 00117 else if (n->level == level) { 00118 b.rect = *r; 00119 b.child = child; 00120 /* child field of leaves contains tid of data record */ 00121 return RTreeAddBranch(&b, n, new_node); 00122 } 00123 else { 00124 /* Not supposed to happen */ 00125 assert(FALSE); 00126 return 0; 00127 } 00128 } 00129 00130 /* 00131 * Insert a data rectangle into an index structure. 00132 * RTreeInsertRect provides for splitting the root; 00133 * returns 1 if root was split, 0 if it was not. 00134 * The level argument specifies the number of steps up from the leaf 00135 * level to insert; e.g. a data rectangle goes in at level = 0. 00136 * RTreeInsertRect2 does the recursion. 00137 */ 00138 int RTreeInsertRect(struct Rect *R, int Tid, struct Node **Root, int Level) 00139 { 00140 assert(Level == 0); 00141 return RTreeInsertRect1(R, (struct Node *) Tid, Root, Level); 00142 } 00143 00144 int RTreeInsertRect1(struct Rect *R, struct Node *Child, struct Node **Root, int Level) 00145 { 00146 register struct Rect *r = R; 00147 register struct Node *child = Child; 00148 register struct Node **root = Root; 00149 register int level = Level; 00150 register int i; 00151 register struct Node *newroot; 00152 struct Node *newnode; 00153 struct Branch b; 00154 int result; 00155 00156 assert(r && root); 00157 assert(level >= 0 && level <= (*root)->level); 00158 for (i = 0; i < NUMDIMS; i++) { 00159 assert(r->boundary[i] <= r->boundary[NUMDIMS + i]); 00160 } 00161 00162 if (RTreeInsertRect2(r, child, *root, &newnode, level)) { /* root split */ 00163 newroot = RTreeNewNode(); /* grow a new root, & tree taller */ 00164 newroot->level = (*root)->level + 1; 00165 b.rect = RTreeNodeCover(*root); 00166 b.child = *root; 00167 RTreeAddBranch(&b, newroot, NULL); 00168 b.rect = RTreeNodeCover(newnode); 00169 b.child = newnode; 00170 RTreeAddBranch(&b, newroot, NULL); 00171 *root = newroot; 00172 result = 1; 00173 } 00174 else 00175 result = 0; 00176 00177 return result; 00178 } 00179 00180 /* 00181 * Allocate space for a node in the list used in DeletRect to 00182 * store Nodes that are too empty. 00183 */ 00184 static struct ListNode *RTreeNewListNode(void) 00185 { 00186 return (struct ListNode *)malloc(sizeof(struct ListNode)); 00187 /* return new ListNode; */ 00188 } 00189 00190 static void RTreeFreeListNode(struct ListNode *p) 00191 { 00192 free(p); 00193 /* delete(p); */ 00194 } 00195 00196 /* 00197 * Add a node to the reinsertion list. All its branches will later 00198 * be reinserted into the index structure. 00199 */ 00200 static void RTreeReInsert(struct Node *n, struct ListNode **ee) 00201 { 00202 register struct ListNode *l; 00203 00204 l = RTreeNewListNode(); 00205 l->node = n; 00206 l->next = *ee; 00207 *ee = l; 00208 } 00209 00210 /* 00211 * Delete a rectangle from non-root part of an index structure. 00212 * Called by RTreeDeleteRect. Descends tree recursively, 00213 * merges branches on the way back up. 00214 * Returns 1 if record not found, 0 if success. 00215 */ 00216 static int 00217 RTreeDeleteRect2(struct Rect *R, struct Node *Child, struct Node *N, 00218 struct ListNode **Ee) 00219 { 00220 register struct Rect *r = R; 00221 register struct Node *child = Child; 00222 register struct Node *n = N; 00223 register struct ListNode **ee = Ee; 00224 register int i; 00225 00226 assert(r && n && ee); 00227 assert(child); 00228 assert(n->level >= 0); 00229 00230 if (n->level > 0) { /* not a leaf node */ 00231 for (i = 0; i < NODECARD; i++) { 00232 if (n->branch[i].child && RTreeOverlap(r, &(n->branch[i].rect))) { 00233 if (!RTreeDeleteRect2(r, child, n->branch[i].child, ee)) { 00234 if (n->branch[i].child->count >= MinNodeFill) { 00235 n->branch[i].rect = 00236 RTreeNodeCover(n->branch[i].child); 00237 } 00238 else { 00239 /* not enough entries in child, eliminate child node */ 00240 RTreeReInsert(n->branch[i].child, ee); 00241 RTreeDisconnectBranch(n, i); 00242 } 00243 return 0; 00244 } 00245 } 00246 } 00247 return 1; 00248 } 00249 else { /* a leaf node */ 00250 00251 for (i = 0; i < LEAFCARD; i++) { 00252 if (n->branch[i].child && 00253 n->branch[i].child == child) { 00254 RTreeDisconnectBranch(n, i); 00255 return 0; 00256 } 00257 } 00258 return 1; 00259 } 00260 } 00261 00262 /* 00263 * Delete a data rectangle from an index structure. 00264 * Pass in a pointer to a Rect, the tid of the record, ptr to ptr to root node. 00265 * Returns 1 if record not found, 0 if success. 00266 * RTreeDeleteRect provides for eliminating the root. 00267 */ 00268 int RTreeDeleteRect(struct Rect *R, int Tid, struct Node **Nn) 00269 { 00270 /* wrapper not really needed, but restricts compile warnings to rtree lib */ 00271 /* this way it's easier to fix if necessary? */ 00272 return RTreeDeleteRect1(R, (struct Node *) Tid, Nn); 00273 } 00274 00275 int RTreeDeleteRect1(struct Rect *R, struct Node *Child, struct Node **Nn) 00276 { 00277 register struct Rect *r = R; 00278 register struct Node *child = Child; 00279 register struct Node **nn = Nn; 00280 register int i; 00281 struct Node *tmp_nptr = NULL; 00282 struct ListNode *reInsertList = NULL; 00283 register struct ListNode *e; 00284 00285 assert(r && nn); 00286 assert(*nn); 00287 assert(child); 00288 00289 if (!RTreeDeleteRect2(r, child, *nn, &reInsertList)) { 00290 /* found and deleted a data item */ 00291 00292 /* reinsert any branches from eliminated nodes */ 00293 while (reInsertList) { 00294 tmp_nptr = reInsertList->node; 00295 for (i = 0; i < MAXKIDS(tmp_nptr); i++) { 00296 if (tmp_nptr->branch[i].child) { 00297 RTreeInsertRect1(&(tmp_nptr->branch[i].rect), 00298 tmp_nptr->branch[i].child, 00299 nn, tmp_nptr->level); 00300 } 00301 } 00302 e = reInsertList; 00303 reInsertList = reInsertList->next; 00304 RTreeFreeNode(e->node); 00305 RTreeFreeListNode(e); 00306 } 00307 00308 /* check for redundant root (not leaf, 1 child) and eliminate */ 00309 if ((*nn)->count == 1 && (*nn)->level > 0) { 00310 for (i = 0; i < NODECARD; i++) { 00311 tmp_nptr = (*nn)->branch[i].child; 00312 if (tmp_nptr) 00313 break; 00314 } 00315 assert(tmp_nptr); 00316 RTreeFreeNode(*nn); 00317 *nn = tmp_nptr; 00318 } 00319 return 0; 00320 } 00321 else { 00322 return 1; 00323 } 00324 }