GRASS Programmer's Manual  6.5.svn(2014)-r66266
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
node.c
Go to the documentation of this file.
1 
2 /****************************************************************************
3 * MODULE: R-Tree library
4 *
5 * AUTHOR(S): Antonin Guttman - original code
6 * Daniel Green (green@superliminal.com) - major clean-up
7 * and implementation of bounding spheres
8 *
9 * PURPOSE: Multidimensional index
10 *
11 * COPYRIGHT: (C) 2001 by the GRASS Development Team
12 *
13 * This program is free software under the GNU General Public
14 * License (>=v2). Read the file COPYING that comes with GRASS
15 * for details.
16 *****************************************************************************/
17 
18 #include <stdio.h>
19 #include <stdlib.h>
20 #include "assert.h"
21 #include "index.h"
22 #include "card.h"
23 
24 /* Initialize one branch cell in a node. */
25 static void RTreeInitBranch(struct Branch *b)
26 {
27  RTreeInitRect(&(b->rect));
28  b->child = NULL;
29 }
30 
31 /* Initialize a Node structure. */
32 void RTreeInitNode(struct Node *N)
33 {
34  register struct Node *n = N;
35  register int i;
36 
37  n->count = 0;
38  n->level = -1;
39  for (i = 0; i < MAXCARD; i++)
40  RTreeInitBranch(&(n->branch[i]));
41 }
42 
43 /* Make a new node and initialize to have all branch cells empty. */
44 struct Node *RTreeNewNode(void)
45 {
46  register struct Node *n;
47 
48  /* n = new Node; */
49  n = (struct Node *)malloc(sizeof(struct Node));
50  assert(n);
51  RTreeInitNode(n);
52  return n;
53 }
54 
55 void RTreeFreeNode(struct Node *p)
56 {
57  assert(p);
58  /* delete p; */
59  free(p);
60 }
61 
62 static void RTreePrintBranch(struct Branch *b, int depth)
63 {
64  RTreePrintRect(&(b->rect), depth);
65  RTreePrintNode(b->child, depth);
66 }
67 
68 extern void RTreeTabIn(int depth)
69 {
70  int i;
71 
72  for (i = 0; i < depth; i++)
73  putchar('\t');
74 }
75 
76 /* Print out the data in a node. */
77 void RTreePrintNode(struct Node *n, int depth)
78 {
79  int i;
80 
81  assert(n);
82 
83  RTreeTabIn(depth);
84  fprintf(stdout, "node");
85  if (n->level == 0)
86  fprintf(stdout, " LEAF");
87  else if (n->level > 0)
88  fprintf(stdout, " NONLEAF");
89  else
90  fprintf(stdout, " TYPE=?");
91  fprintf(stdout, " level=%d count=%d address=%o\n", n->level, n->count,
92  (unsigned)n);
93 
94  for (i = 0; i < n->count; i++) {
95  if (n->level == 0) {
96  /* RTreeTabIn(depth); */
97  /* fprintf (stdout, "\t%d: data = %d\n", i, n->branch[i].child); */
98  }
99  else {
100  RTreeTabIn(depth);
101  fprintf(stdout, "branch %d\n", i);
102  RTreePrintBranch(&n->branch[i], depth + 1);
103  }
104  }
105 }
106 
107 /*
108  * Find the smallest rectangle that includes all rectangles in
109  * branches of a node.
110  */
111 struct Rect RTreeNodeCover(struct Node *N)
112 {
113  register struct Node *n = N;
114  register int i, first_time = 1;
115  struct Rect r;
116 
117  assert(n);
118 
119  RTreeInitRect(&r);
120  for (i = 0; i < MAXKIDS(n); i++)
121  if (n->branch[i].child) {
122  if (first_time) {
123  r = n->branch[i].rect;
124  first_time = 0;
125  }
126  else
127  r = RTreeCombineRect(&r, &(n->branch[i].rect));
128  }
129  return r;
130 }
131 
132 /*
133  * Pick a branch. Pick the one that will need the smallest increase
134  * in area to accomodate the new rectangle. This will result in the
135  * least total area for the covering rectangles in the current node.
136  * In case of a tie, pick the one which was smaller before, to get
137  * the best resolution when searching.
138  */
139 int RTreePickBranch(struct Rect *R, struct Node *N)
140 {
141  register struct Rect *r = R;
142  register struct Node *n = N;
143  register struct Rect *rr;
144  register int i, first_time = 1;
145  RectReal increase, bestIncr = (RectReal) - 1, area, bestArea = 0;
146  int best = 0;
147  struct Rect tmp_rect;
148 
149  assert(r && n);
150 
151  for (i = 0; i < MAXKIDS(n); i++) {
152  if (n->branch[i].child) {
153  rr = &n->branch[i].rect;
154  area = RTreeRectSphericalVolume(rr);
155  tmp_rect = RTreeCombineRect(r, rr);
156  increase = RTreeRectSphericalVolume(&tmp_rect) - area;
157  if (increase < bestIncr || first_time) {
158  best = i;
159  bestArea = area;
160  bestIncr = increase;
161  first_time = 0;
162  }
163  else if (increase == bestIncr && area < bestArea) {
164  best = i;
165  bestArea = area;
166  bestIncr = increase;
167  }
168  }
169  }
170  return best;
171 }
172 
173 /*
174  * Add a branch to a node. Split the node if necessary.
175  * Returns 0 if node not split. Old node updated.
176  * Returns 1 if node split, sets *new_node to address of new node.
177  * Old node updated, becomes one of two.
178  */
179 int RTreeAddBranch(struct Branch *B, struct Node *N, struct Node **New_node)
180 {
181  register struct Branch *b = B;
182  register struct Node *n = N;
183  register struct Node **new_node = New_node;
184  register int i;
185 
186  assert(b);
187  assert(n);
188 
189  if (n->count < MAXKIDS(n)) { /* split won't be necessary */
190  for (i = 0; i < MAXKIDS(n); i++) { /* find empty branch */
191  if (n->branch[i].child == NULL) {
192  n->branch[i] = *b;
193  n->count++;
194  break;
195  }
196  }
197  return 0;
198  }
199  else {
200  assert(new_node);
201  RTreeSplitNode(n, b, new_node);
202  return 1;
203  }
204 }
205 
206 /* Disconnect a dependent node. */
207 void RTreeDisconnectBranch(struct Node *n, int i)
208 {
209  assert(n && i >= 0 && i < MAXKIDS(n));
210  assert(n->branch[i].child);
211 
212  RTreeInitBranch(&(n->branch[i]));
213  n->count--;
214 }
215 
216 /* Destroy (free) node recursively. */
217 void RTreeDestroyNode(struct Node *n)
218 {
219  int i;
220 
221  if (n->level > 0) { /* it is not leaf -> destroy childs */
222  for (i = 0; i < NODECARD; i++) {
223  if (n->branch[i].child) {
225  }
226  }
227  }
228 
229  /* Free this node */
230  RTreeFreeNode(n);
231 }
double RectReal
Definition: index.h:25
int RTreePickBranch(struct Rect *, struct Node *)
Definition: node.c:139
float b
Definition: named_colr.c:8
struct Node * child
Definition: index.h:50
struct Rect rect
Definition: index.h:49
float r
Definition: named_colr.c:8
Definition: index.h:56
int RTreeAddBranch(struct Branch *, struct Node *, struct Node **)
Definition: node.c:179
void RTreeDestroyNode(struct Node *)
Definition: node.c:217
RectReal RTreeRectSphericalVolume(struct Rect *R)
Definition: rect.c:253
void RTreePrintNode(struct Node *, int)
Definition: node.c:77
void RTreeSplitNode(struct Node *, struct Branch *, struct Node **)
Definition: split_q.c:292
Definition: index.h:47
struct Node * RTreeNewNode(void)
Definition: node.c:44
void RTreeInitRect(struct Rect *)
Definition: rect.c:38
void * malloc(YYSIZE_T)
void RTreePrintRect(struct Rect *, int)
Definition: rect.c:130
struct Rect RTreeNodeCover(struct Node *)
Definition: node.c:111
return NULL
Definition: dbfopen.c:1394
struct Rect RTreeCombineRect(struct Rect *, struct Rect *)
Definition: rect.c:305
int count
Definition: index.h:58
void free(void *)
#define N
Definition: inverse.c:8
#define MAXKIDS(n)
Definition: card.h:29
int NODECARD
Definition: card.c:21
void RTreeInitNode(struct Node *)
Definition: node.c:32
int level
Definition: index.h:59
Definition: index.h:40
int n
Definition: dataquad.c:291
void RTreeFreeNode(struct Node *)
Definition: node.c:55
#define MAXCARD
Definition: index.h:54
struct Branch branch[MAXCARD]
Definition: index.h:60
void RTreeTabIn(int)
Definition: node.c:68
void RTreeDisconnectBranch(struct Node *, int)
Definition: node.c:207