GRASS GIS 8 Programmer's Manual  8.4.0dev(2024)-381f661b3f
node.c
Go to the documentation of this file.
1 /****************************************************************************
2  * MODULE: R-Tree library
3  *
4  * AUTHOR(S): Antonin Guttman - original code
5  * Daniel Green (green@superliminal.com) - major clean-up
6  * and implementation of bounding spheres
7  * Markus Metz - file-based and memory-based R*-tree
8  *
9  * PURPOSE: Multidimensional index
10  *
11  * COPYRIGHT: (C) 2010 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 <string.h>
21 #include <assert.h>
22 #include <grass/gis.h>
23 #include "index.h"
24 #include "split.h"
25 #include "card.h"
26 
27 /* rectangle distances for forced removal */
28 struct dist {
29  int id; /* branch id */
30  RectReal distance; /* distance to node center */
31 };
32 
33 /* Initialize one branch cell in an internal node. */
34 static void RTreeInitNodeBranchM(struct RTree_Branch *b, struct RTree *t)
35 {
36  RTreeInitRect(&(b->rect), t);
37  memset(&(b->child), 0, sizeof(union RTree_Child));
38  b->child.ptr = NULL;
39 }
40 
41 /* Initialize one branch cell in an internal node. */
42 static void RTreeInitNodeBranchF(struct RTree_Branch *b, struct RTree *t)
43 {
44  RTreeInitRect(&(b->rect), t);
45  memset(&(b->child), 0, sizeof(union RTree_Child));
46  b->child.pos = -1;
47 }
48 
49 /* Initialize one branch cell in a leaf node. */
50 static void RTreeInitLeafBranch(struct RTree_Branch *b, struct RTree *t)
51 {
52  RTreeInitRect(&(b->rect), t);
53  memset(&(b->child), 0, sizeof(union RTree_Child));
54  b->child.id = 0;
55 }
56 
57 static void (*RTreeInitBranch[3])(struct RTree_Branch *b, struct RTree *t) = {
58  RTreeInitLeafBranch, RTreeInitNodeBranchM, RTreeInitNodeBranchF};
59 
60 /* Initialize a Node structure. */
61 /* type = 1: leaf, type = 2: internal, memory, type = 3: internal, file */
62 void RTreeInitNode(struct RTree *t, struct RTree_Node *n, int type)
63 {
64  int i;
65 
66  n->count = 0;
67  n->level = -1;
68 
69  for (i = 0; i < MAXCARD; i++)
70  RTreeInitBranch[type](&(n->branch[i]), t);
71 }
72 
73 /* Make a new node and initialize to have all branch cells empty. */
74 struct RTree_Node *RTreeAllocNode(struct RTree *t, int level)
75 {
76  int i;
77  struct RTree_Node *n;
78 
79  n = (struct RTree_Node *)malloc(sizeof(struct RTree_Node));
80  assert(n);
81 
82  n->count = 0;
83  n->level = level;
84 
85  n->branch = malloc(MAXCARD * sizeof(struct RTree_Branch));
86 
87  for (i = 0; i < MAXCARD; i++) {
89  RTreeInitBranch[NODETYPE(level, t->fd)](&(n->branch[i]), t);
90  }
91 
92  return n;
93 }
94 
95 void RTreeFreeNode(struct RTree_Node *n)
96 {
97  int i;
98 
99  assert(n);
100 
101  for (i = 0; i < MAXCARD; i++)
102  RTreeFreeBoundary(&(n->branch[i].rect));
103 
104  free(n->branch);
105  free(n);
106 }
107 
108 /* copy node 2 to node 1 */
109 void RTreeCopyNode(struct RTree_Node *n1, struct RTree_Node *n2,
110  struct RTree *t)
111 {
112  int i;
113 
114  assert(n1 && n2);
115 
116  n1->count = n2->count;
117  n1->level = n2->level;
118  for (i = 0; i < MAXCARD; i++) {
119  RTreeCopyBranch(&(n1->branch[i]), &(n2->branch[i]), t);
120  }
121 }
122 
123 /* copy branch 2 to branch 1 */
124 void RTreeCopyBranch(struct RTree_Branch *b1, struct RTree_Branch *b2,
125  struct RTree *t)
126 {
127  b1->child = b2->child;
128  RTreeCopyRect(&(b1->rect), &(b2->rect), t);
129 }
130 
131 /*
132  * Find the smallest rectangle that includes all rectangles in
133  * branches of a node.
134  */
135 void RTreeNodeCover(struct RTree_Node *n, struct RTree_Rect *r, struct RTree *t)
136 {
137  int i, first_time = 1;
138 
139  if ((n)->level > 0) { /* internal node */
140  for (i = 0; i < t->nodecard; i++) {
141  if (t->valid_child(&(n->branch[i].child))) {
142  if (first_time) {
143  RTreeCopyRect(r, &(n->branch[i].rect), t);
144  first_time = 0;
145  }
146  else
147  RTreeExpandRect(r, &(n->branch[i].rect), t);
148  }
149  }
150  }
151  else { /* leaf */
152  for (i = 0; i < t->leafcard; i++) {
153  if (n->branch[i].child.id) {
154  if (first_time) {
155  RTreeCopyRect(r, &(n->branch[i].rect), t);
156  first_time = 0;
157  }
158  else
159  RTreeExpandRect(r, &(n->branch[i].rect), t);
160  }
161  }
162  }
163 }
164 
165 /*
166  * Idea from R*-tree, modified: not overlap size but overlap number
167  *
168  * Pick a branch from leaf nodes (current node has level 1). Pick the
169  * one that will result in the smallest number of overlapping siblings.
170  * This will result in the least ambiguous node covering the new
171  * rectangle, improving search speed.
172  * In case of a tie, pick the one which needs the smallest increase in
173  * area to accommodate the new rectangle, then the smallest area before,
174  * to get the best resolution when searching.
175  */
176 
177 static int RTreePickLeafBranch(struct RTree_Rect *r, struct RTree_Node *n,
178  struct RTree *t)
179 {
180  struct RTree_Rect *rr;
181  int i, j;
182  RectReal increase, bestIncr = -1, area, bestArea = 0;
183  int best = 0, bestoverlap;
184  int overlap;
185 
186  bestoverlap = t->nodecard + 1;
187 
188  /* get the branch that will overlap with the smallest number of
189  * sibling branches when including the new rectangle */
190  for (i = 0; i < t->nodecard; i++) {
191  if (t->valid_child(&(n->branch[i].child))) {
192  rr = &n->branch[i].rect;
193  RTreeCombineRect(r, rr, &(t->orect), t);
194  area = RTreeRectSphericalVolume(rr, t);
195  increase = RTreeRectSphericalVolume(&(t->orect), t) - area;
196 
197  overlap = 0;
198  for (j = 0; j < t->leafcard; j++) {
199  if (j != i) {
200  rr = &n->branch[j].rect;
201  overlap += RTreeOverlap(&(t->orect), rr, t);
202  }
203  }
204 
205  if (overlap < bestoverlap) {
206  best = i;
207  bestoverlap = overlap;
208  bestArea = area;
209  bestIncr = increase;
210  }
211  else if (overlap == bestoverlap) {
212  /* resolve ties */
213  if (increase < bestIncr) {
214  best = i;
215  bestArea = area;
216  bestIncr = increase;
217  }
218  else if (increase == bestIncr && area < bestArea) {
219  best = i;
220  bestArea = area;
221  }
222  }
223  }
224  }
225 
226  return best;
227 }
228 
229 /*
230  * Pick a branch. Pick the one that will need the smallest increase
231  * in area to accommodate the new rectangle. This will result in the
232  * least total area for the covering rectangles in the current node.
233  * In case of a tie, pick the one which was smaller before, to get
234  * the best resolution when searching.
235  */
236 int RTreePickBranch(struct RTree_Rect *r, struct RTree_Node *n, struct RTree *t)
237 {
238  struct RTree_Rect *rr;
239  int i, first_time = 1;
240  RectReal increase, bestIncr = (RectReal)-1, area, bestArea = 0;
241  int best = 0;
242 
243  assert((n)->level > 0); /* must not be called on leaf node */
244 
245  if ((n)->level == 1)
246  return RTreePickLeafBranch(r, n, t);
247 
248  for (i = 0; i < t->nodecard; i++) {
249  if (t->valid_child(&(n->branch[i].child))) {
250  rr = &n->branch[i].rect;
251  area = RTreeRectSphericalVolume(rr, t);
252  RTreeCombineRect(r, rr, &(t->orect), t);
253  increase = RTreeRectSphericalVolume(&(t->orect), t) - area;
254  if (increase < bestIncr || first_time) {
255  best = i;
256  bestArea = area;
257  bestIncr = increase;
258  first_time = 0;
259  }
260  else if (increase == bestIncr && area < bestArea) {
261  best = i;
262  bestArea = area;
263  }
264  }
265  }
266  return best;
267 }
268 
269 /* Disconnect a dependent node. */
270 void RTreeDisconnectBranch(struct RTree_Node *n, int i, struct RTree *t)
271 {
272  if ((n)->level > 0) {
273  assert(n && i >= 0 && i < t->nodecard);
274  assert(t->valid_child(&(n->branch[i].child)));
275  if (t->fd < 0)
276  RTreeInitNodeBranchM(&(n->branch[i]), t);
277  else
278  RTreeInitNodeBranchF(&(n->branch[i]), t);
279  }
280  else {
281  assert(n && i >= 0 && i < t->leafcard);
282  assert(n->branch[i].child.id);
283  RTreeInitLeafBranch(&(n->branch[i]), t);
284  }
285 
286  n->count--;
287 }
288 
289 /* Destroy (free) node recursively. */
290 /* NOTE: only needed for memory based index */
291 void RTreeDestroyNode(struct RTree_Node *n, int nodes)
292 {
293  int i;
294 
295  if (n->level > 0) { /* it is not leaf -> destroy children */
296  for (i = 0; i < nodes; i++) {
297  if (n->branch[i].child.ptr) {
298  RTreeDestroyNode(n->branch[i].child.ptr, nodes);
299  }
300  }
301  }
302 
303  /* Free this node */
304  RTreeFreeNode(n);
305 
306  return;
307 }
308 
309 /****************************************************************
310  * *
311  * R*-tree: force remove FORCECARD branches for reinsertion *
312  * *
313  ****************************************************************/
314 
315 /*
316  * swap dist structs
317  */
318 static void RTreeSwapDist(struct dist *a, struct dist *b)
319 {
320  struct dist c;
321 
322  c = *a;
323  *a = *b;
324  *b = c;
325 }
326 
327 /*
328  * check if dist is sorted ascending to distance
329  */
330 static int RTreeDistIsSorted(struct dist *d, int first, int last)
331 {
332  int i;
333 
334  for (i = first; i < last; i++) {
335  if (d[i].distance > d[i + 1].distance)
336  return 0;
337  }
338 
339  return 1;
340 }
341 
342 /*
343  * partition dist for quicksort on distance
344  */
345 static int RTreePartitionDist(struct dist *d, int first, int last)
346 {
347  int pivot, mid = ((first + last) >> 1);
348  int larger, smaller;
349 
350  if (last - first == 1) { /* only two items in list */
351  if (d[first].distance > d[last].distance) {
352  RTreeSwapDist(&(d[first]), &(d[last]));
353  }
354  return last;
355  }
356 
357  /* Larger of two */
358  larger = pivot = mid;
359  smaller = first;
360  if (d[first].distance > d[mid].distance) {
361  larger = pivot = first;
362  smaller = mid;
363  }
364 
365  if (d[larger].distance > d[last].distance) {
366  /* larger is largest, get the larger of smaller and last */
367  pivot = last;
368  if (d[smaller].distance > d[last].distance) {
369  pivot = smaller;
370  }
371  }
372 
373  if (pivot != last) {
374  RTreeSwapDist(&(d[pivot]), &(d[last]));
375  }
376 
377  pivot = first;
378 
379  while (first < last) {
380  if (d[first].distance <= d[last].distance) {
381  if (pivot != first) {
382  RTreeSwapDist(&(d[pivot]), &(d[first]));
383  }
384  pivot++;
385  }
386  ++first;
387  }
388 
389  if (pivot != last) {
390  RTreeSwapDist(&(d[pivot]), &(d[last]));
391  }
392 
393  return pivot;
394 }
395 
396 /*
397  * quicksort dist struct ascending by distance
398  * n is last valid index
399  */
400 static void RTreeQuicksortDist(struct dist *d, int n)
401 {
402  int pivot, first, last;
403  int s_first[MAXCARD + 1], s_last[MAXCARD + 1], stacksize;
404 
405  s_first[0] = 0;
406  s_last[0] = n;
407 
408  stacksize = 1;
409 
410  /* use stack */
411  while (stacksize) {
412  stacksize--;
413  first = s_first[stacksize];
414  last = s_last[stacksize];
415  if (first < last) {
416  if (!RTreeDistIsSorted(d, first, last)) {
417 
418  pivot = RTreePartitionDist(d, first, last);
419 
420  s_first[stacksize] = first;
421  s_last[stacksize] = pivot - 1;
422  stacksize++;
423 
424  s_first[stacksize] = pivot + 1;
425  s_last[stacksize] = last;
426  stacksize++;
427  }
428  }
429  }
430 }
431 
432 /*
433  * Allocate space for a branch in the list used in InsertRect to
434  * store branches of nodes that are too full.
435  */
436 static struct RTree_ListBranch *RTreeNewListBranch(struct RTree *t)
437 {
438  struct RTree_ListBranch *p =
439  (struct RTree_ListBranch *)malloc(sizeof(struct RTree_ListBranch));
440 
441  assert(p);
443 
444  return p;
445 }
446 
447 /*
448  * Add a branch to the reinsertion list. It will later
449  * be reinserted into the index structure.
450  */
451 static void RTreeReInsertBranch(struct RTree_Branch b, int level,
452  struct RTree_ListBranch **ee, struct RTree *t)
453 {
454  register struct RTree_ListBranch *l;
455 
456  l = RTreeNewListBranch(t);
457  RTreeCopyBranch(&(l->b), &b, t);
458  l->level = level;
459  l->next = *ee;
460  *ee = l;
461 }
462 
463 /*
464  * Remove branches from a node. Select the 2 branches whose rectangle
465  * center is farthest away from node cover center.
466  * Old node updated.
467  */
468 static void RTreeRemoveBranches(struct RTree_Node *n, struct RTree_Branch *b,
469  struct RTree_ListBranch **ee,
470  struct RTree_Rect *cover, struct RTree *t)
471 {
472  int i, j, maxkids, type;
473  RectReal center_r, delta;
474  struct dist rdist[MAXCARD + 1];
475 
476  struct RTree_Rect *new_cover = &(t->orect);
477  RectReal *center_n = t->center_n;
478 
479  assert(cover);
480 
481  maxkids = MAXKIDS((n)->level, t);
482  type = NODETYPE((n)->level, t->fd);
483 
484  assert(n->count == maxkids); /* must be full */
485 
486  RTreeCombineRect(cover, &(b->rect), new_cover, t);
487 
488  /* center coords of node cover */
489  for (j = 0; j < t->ndims; j++) {
490  center_n[j] =
491  (new_cover->boundary[j + t->ndims_alloc] + new_cover->boundary[j]) /
492  2;
493  }
494 
495  /* compute distances of child rectangle centers to node cover center */
496  for (i = 0; i < maxkids; i++) {
497  RTreeCopyBranch(&(t->BranchBuf[i]), &(n->branch[i]), t);
498  rdist[i].distance = 0;
499  rdist[i].id = i;
500  for (j = 0; j < t->ndims; j++) {
501  center_r = (t->BranchBuf[i].rect.boundary[j + t->ndims_alloc] +
502  t->BranchBuf[i].rect.boundary[j]) /
503  2;
504  delta = center_n[j] - center_r;
505  rdist[i].distance += delta * delta;
506  }
507 
508  RTreeInitBranch[type](&(n->branch[i]), t);
509  }
510 
511  /* new branch */
512  RTreeCopyBranch(&(t->BranchBuf[maxkids]), b, t);
513  rdist[maxkids].distance = 0;
514  for (j = 0; j < t->ndims; j++) {
515  center_r =
516  (b->rect.boundary[j + t->ndims_alloc] + b->rect.boundary[j]) / 2;
517  delta = center_n[j] - center_r;
518  rdist[maxkids].distance += delta * delta;
519  }
520  rdist[maxkids].id = maxkids;
521 
522  /* quicksort dist */
523  RTreeQuicksortDist(rdist, maxkids);
524 
525  /* put largest three in branch list, farthest from center first */
526  for (i = 0; i < FORCECARD; i++) {
527  RTreeReInsertBranch(t->BranchBuf[rdist[maxkids - i].id], n->level, ee,
528  t);
529  }
530  /* put remaining in node, closest to center first */
531  for (i = 0; i < maxkids - FORCECARD + 1; i++) {
532  RTreeCopyBranch(&(n->branch[i]), &(t->BranchBuf[rdist[i].id]), t);
533  }
534  n->count = maxkids - FORCECARD + 1;
535 }
536 
537 /*
538  * Add a branch to a node. Split the node if necessary.
539  * Returns 0 if node not split. Old node updated.
540  * Returns 1 if node split, sets *new_node to address of new node.
541  * Old node updated, becomes one of two.
542  * Returns 2 if branches were removed for forced reinsertion
543  */
544 int RTreeAddBranch(struct RTree_Branch *b, struct RTree_Node *n,
545  struct RTree_Node **newnode, struct RTree_ListBranch **ee,
546  struct RTree_Rect *cover, char *overflow, struct RTree *t)
547 {
548  int i, maxkids;
549 
550  maxkids = MAXKIDS((n)->level, t);
551 
552  if (n->count < maxkids) { /* split won't be necessary */
553  if ((n)->level > 0) { /* internal node */
554  for (i = 0; i < maxkids; i++) { /* find empty branch */
555  if (!t->valid_child(&(n->branch[i].child))) {
556  /* copy branch */
557  n->branch[i].child = b->child;
558  RTreeCopyRect(&(n->branch[i].rect), &(b->rect), t);
559  n->count++;
560  break;
561  }
562  }
563  return 0;
564  }
565  else if ((n)->level == 0) { /* leaf */
566  for (i = 0; i < maxkids; i++) { /* find empty branch */
567  if (n->branch[i].child.id == 0) {
568  /* copy branch */
569  n->branch[i].child = b->child;
570  RTreeCopyRect(&(n->branch[i].rect), &(b->rect), t);
571  n->count++;
572  break;
573  }
574  }
575  return 0;
576  }
577  }
578  else {
579  if (n->level < t->rootlevel && overflow[n->level]) {
580  /* R*-tree forced reinsert */
581  RTreeRemoveBranches(n, b, ee, cover, t);
582  overflow[n->level] = 0;
583  return 2;
584  }
585  else {
586  if (t->fd > -1)
587  RTreeInitNode(t, *newnode, NODETYPE(n->level, t->fd));
588  else
589  *newnode = RTreeAllocNode(t, (n)->level);
590  RTreeSplitNode(n, b, *newnode, t);
591  return 1;
592  }
593  }
594 
595  /* should not be reached */
596  assert(0);
597  return -1;
598 }
599 
600 /*
601  * for debugging only: print items to stdout
602  */
603 
604 void RTreeTabIn(int depth)
605 {
606  int i;
607 
608  for (i = 0; i < depth; i++)
609  putchar('\t');
610 }
611 
612 static void RTreePrintBranch(struct RTree_Branch *b, int depth, struct RTree *t)
613 {
614  RTreePrintRect(&(b->rect), depth, t);
615  RTreePrintNode(b->child.ptr, depth, t);
616 }
617 
618 /* Print out the data in a node. */
619 void RTreePrintNode(struct RTree_Node *n, int depth, struct RTree *t)
620 {
621  int i, maxkids;
622 
623  RTreeTabIn(depth);
624 
625  maxkids = (n->level > 0 ? t->nodecard : t->leafcard);
626 
627  fprintf(stdout, "node");
628  if (n->level == 0)
629  fprintf(stdout, " LEAF");
630  else if (n->level > 0)
631  fprintf(stdout, " NONLEAF");
632  else
633  fprintf(stdout, " TYPE=?");
634  fprintf(stdout, " level=%d count=%d", n->level, n->count);
635 
636  for (i = 0; i < maxkids; i++) {
637  if (n->level == 0) {
638  RTreeTabIn(depth);
639  RTreePrintRect(&(n->branch[i].rect), depth, t);
640  fprintf(stdout, "\t%d: data id = %d\n", i, n->branch[i].child.id);
641  }
642  else {
643  RTreeTabIn(depth);
644  fprintf(stdout, "branch %d\n", i);
645  RTreePrintBranch(&(n->branch[i]), depth + 1, t);
646  }
647  }
648 }
#define MAXKIDS(level, t)
Definition: card.h:27
#define NULL
Definition: ccmath.h:32
RectReal RTreeRectSphericalVolume(struct RTree_Rect *, struct RTree *)
Definition: rect.c:432
#define NODETYPE(l, fd)
Definition: index.h:31
void RTreeSplitNode(struct RTree_Node *, struct RTree_Branch *, struct RTree_Node *, struct RTree *)
Definition: split.c:613
void RTreeCombineRect(struct RTree_Rect *, struct RTree_Rect *, struct RTree_Rect *, struct RTree *)
Definition: rect.c:500
int RTreeExpandRect(struct RTree_Rect *, struct RTree_Rect *, struct RTree *)
Definition: rect.c:536
void RTreeInitRect(struct RTree_Rect *, struct RTree *)
Initialize a rectangle to have all 0 coordinates.
Definition: rect.c:109
#define RTreeCopyRect(r1, r2, t)
Definition: index.h:100
#define FORCECARD
Definition: index.h:29
#define assert(condition)
Definition: lz4.c:393
void RTreePrintNode(struct RTree_Node *n, int depth, struct RTree *t)
Definition: node.c:619
void RTreeCopyNode(struct RTree_Node *n1, struct RTree_Node *n2, struct RTree *t)
Definition: node.c:109
void RTreeCopyBranch(struct RTree_Branch *b1, struct RTree_Branch *b2, struct RTree *t)
Definition: node.c:124
void RTreeFreeNode(struct RTree_Node *n)
Definition: node.c:95
void RTreeDisconnectBranch(struct RTree_Node *n, int i, struct RTree *t)
Definition: node.c:270
void RTreeNodeCover(struct RTree_Node *n, struct RTree_Rect *r, struct RTree *t)
Definition: node.c:135
struct RTree_Node * RTreeAllocNode(struct RTree *t, int level)
Definition: node.c:74
void RTreeDestroyNode(struct RTree_Node *n, int nodes)
Definition: node.c:291
void RTreeTabIn(int depth)
Definition: node.c:604
int RTreeAddBranch(struct RTree_Branch *b, struct RTree_Node *n, struct RTree_Node **newnode, struct RTree_ListBranch **ee, struct RTree_Rect *cover, char *overflow, struct RTree *t)
Definition: node.c:544
int RTreePickBranch(struct RTree_Rect *r, struct RTree_Node *n, struct RTree *t)
Definition: node.c:236
void RTreeInitNode(struct RTree *t, struct RTree_Node *n, int type)
Definition: node.c:62
double b
Definition: r_raster.c:39
double l
Definition: r_raster.c:39
double t
Definition: r_raster.c:39
double r
Definition: r_raster.c:39
RectReal * RTreeAllocBoundary(struct RTree *t)
Allocate the boundary array of a rectangle for a given tree.
Definition: rect.c:81
void RTreeFreeBoundary(struct RTree_Rect *r)
Delete the boundary of a rectangle.
Definition: rect.c:98
int RTreeOverlap(struct RTree_Rect *r, struct RTree_Rect *s, struct RTree *t)
Definition: rect.c:590
void RTreePrintRect(struct RTree_Rect *R, int depth, struct RTree *t)
Definition: rect.c:304
#define MAXCARD
Definition: rtree.h:44
double RectReal
Definition: rtree.h:26
void * malloc(YYSIZE_T)
void free(void *)
struct RTree_Rect rect
Definition: rtree.h:68
union RTree_Child child
Definition: rtree.h:69
struct RTree_Branch b
Definition: index.h:45
int count
Definition: rtree.h:74
int level
Definition: rtree.h:75
struct RTree_Branch * branch
Definition: rtree.h:76
RectReal * boundary
Definition: rtree.h:55
Definition: rtree.h:123
struct RTree_Node * ptr
Definition: rtree.h:62
int id
Definition: rtree.h:61