GRASS GIS 7 Programmer's Manual  7.9.dev(2021)-e5379bbd7
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 * Markus Metz - file-based and memory-based R*-tree
9 *
10 * PURPOSE: Multidimensional index
11 *
12 * COPYRIGHT: (C) 2010 by the GRASS Development Team
13 *
14 * This program is free software under the GNU General Public
15 * License (>=v2). Read the file COPYING that comes with GRASS
16 * for details.
17 *****************************************************************************/
18 
19 #include <stdio.h>
20 #include <stdlib.h>
21 #include <string.h>
22 #include <assert.h>
23 #include <grass/gis.h>
24 #include "index.h"
25 #include "split.h"
26 #include "card.h"
27 
28 /* rectangle distances for forced removal */
29 struct dist
30 {
31  int id; /* branch id */
32  RectReal distance; /* distance to node center */
33 };
34 
35 /* Initialize one branch cell in an internal node. */
36 static void RTreeInitNodeBranchM(struct RTree_Branch *b, struct RTree *t)
37 {
38  RTreeInitRect(&(b->rect), t);
39  memset(&(b->child), 0, sizeof(union RTree_Child));
40  b->child.ptr = NULL;
41 }
42 
43 /* Initialize one branch cell in an internal node. */
44 static void RTreeInitNodeBranchF(struct RTree_Branch *b, struct RTree *t)
45 {
46  RTreeInitRect(&(b->rect), t);
47  memset(&(b->child), 0, sizeof(union RTree_Child));
48  b->child.pos = -1;
49 }
50 
51 /* Initialize one branch cell in a leaf node. */
52 static void RTreeInitLeafBranch(struct RTree_Branch *b, struct RTree *t)
53 {
54  RTreeInitRect(&(b->rect), t);
55  memset(&(b->child), 0, sizeof(union RTree_Child));
56  b->child.id = 0;
57 }
58 
59 static void (*RTreeInitBranch[3]) (struct RTree_Branch *b, struct RTree *t) = {
60  RTreeInitLeafBranch, RTreeInitNodeBranchM, RTreeInitNodeBranchF
61 };
62 
63 /* Initialize a Node structure. */
64 /* type = 1: leaf, type = 2: internal, memory, type = 3: internal, file */
65 void RTreeInitNode(struct RTree *t, struct RTree_Node *n, int type)
66 {
67  int i;
68 
69  n->count = 0;
70  n->level = -1;
71 
72  for (i = 0; i < MAXCARD; i++)
73  RTreeInitBranch[type](&(n->branch[i]), t);
74 }
75 
76 /* Make a new node and initialize to have all branch cells empty. */
77 struct RTree_Node *RTreeAllocNode(struct RTree *t, int level)
78 {
79  int i;
80  struct RTree_Node *n;
81 
82  n = (struct RTree_Node *)malloc(sizeof(struct RTree_Node));
83  assert(n);
84 
85  n->count = 0;
86  n->level = level;
87 
88  n->branch = malloc(MAXCARD * sizeof(struct RTree_Branch));
89 
90  for (i = 0; i < MAXCARD; i++) {
92  RTreeInitBranch[NODETYPE(level, t->fd)](&(n->branch[i]), t);
93  }
94 
95  return n;
96 }
97 
98 void RTreeFreeNode(struct RTree_Node *n)
99 {
100  int i;
101 
102  assert(n);
103 
104  for (i = 0; i < MAXCARD; i++)
105  RTreeFreeBoundary(&(n->branch[i].rect));
106 
107  free(n->branch);
108  free(n);
109 }
110 
111 /* copy node 2 to node 1 */
112 void RTreeCopyNode(struct RTree_Node *n1, struct RTree_Node *n2, struct RTree *t)
113 {
114  int i;
115 
116  assert(n1 && n2);
117 
118  n1->count = n2->count;
119  n1->level = n2->level;
120  for (i = 0; i < MAXCARD; i++) {
121  RTreeCopyBranch(&(n1->branch[i]), &(n2->branch[i]), t);
122  }
123 }
124 
125 /* copy branch 2 to branch 1 */
126 void RTreeCopyBranch(struct RTree_Branch *b1, struct RTree_Branch *b2, struct RTree *t)
127 {
128  b1->child = b2->child;
129  RTreeCopyRect(&(b1->rect), &(b2->rect), t);
130 }
131 
132 /*
133  * Find the smallest rectangle that includes all rectangles in
134  * branches of a node.
135  */
136 void RTreeNodeCover(struct RTree_Node *n, struct RTree_Rect *r, struct RTree *t)
137 {
138  int i, first_time = 1;
139 
140  if ((n)->level > 0) { /* internal node */
141  for (i = 0; i < t->nodecard; i++) {
142  if (t->valid_child(&(n->branch[i].child))) {
143  if (first_time) {
144  RTreeCopyRect(r, &(n->branch[i].rect), t);
145  first_time = 0;
146  }
147  else
148  RTreeExpandRect(r, &(n->branch[i].rect), t);
149  }
150  }
151  }
152  else { /* leaf */
153  for (i = 0; i < t->leafcard; i++) {
154  if (n->branch[i].child.id) {
155  if (first_time) {
156  RTreeCopyRect(r, &(n->branch[i].rect), t);
157  first_time = 0;
158  }
159  else
160  RTreeExpandRect(r, &(n->branch[i].rect), t);
161  }
162  }
163  }
164 }
165 
166 /*
167  * Idea from R*-tree, modified: not overlap size but overlap number
168  *
169  * Pick a branch from leaf nodes (current node has level 1). Pick the
170  * one that will result in the smallest number of overlapping siblings.
171  * This will result in the least ambiguous node covering the new
172  * rectangle, improving search speed.
173  * In case of a tie, pick the one which needs the smallest increase in
174  * area to accommodate the new rectangle, then the smallest area before,
175  * to get the best resolution when searching.
176  */
177 
178 static int RTreePickLeafBranch(struct RTree_Rect *r, struct RTree_Node *n, 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 childs */
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, struct RTree_Rect *cover,
470  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] = (new_cover->boundary[j + t->ndims_alloc] + new_cover->boundary[j]) / 2;
491  }
492 
493  /* compute distances of child rectangle centers to node cover center */
494  for (i = 0; i < maxkids; i++) {
495  RTreeCopyBranch(&(t->BranchBuf[i]), &(n->branch[i]), t);
496  rdist[i].distance = 0;
497  rdist[i].id = i;
498  for (j = 0; j < t->ndims; j++) {
499  center_r =
500  (t->BranchBuf[i].rect.boundary[j + t->ndims_alloc] +
501  t->BranchBuf[i].rect.boundary[j]) / 2;
502  delta = center_n[j] - center_r;
503  rdist[i].distance += delta * delta;
504  }
505 
506  RTreeInitBranch[type](&(n->branch[i]), t);
507  }
508 
509  /* new branch */
510  RTreeCopyBranch(&(t->BranchBuf[maxkids]), b, t);
511  rdist[maxkids].distance = 0;
512  for (j = 0; j < t->ndims; j++) {
513  center_r =
514  (b->rect.boundary[j + t->ndims_alloc] +
515  b->rect.boundary[j]) / 2;
516  delta = center_n[j] - center_r;
517  rdist[maxkids].distance += delta * delta;
518  }
519  rdist[maxkids].id = maxkids;
520 
521  /* quicksort dist */
522  RTreeQuicksortDist(rdist, maxkids);
523 
524  /* put largest three in branch list, farthest from center first */
525  for (i = 0; i < FORCECARD; i++) {
526  RTreeReInsertBranch(t->BranchBuf[rdist[maxkids - i].id], n->level, ee, t);
527  }
528  /* put remaining in node, closest to center first */
529  for (i = 0; i < maxkids - FORCECARD + 1; i++) {
530  RTreeCopyBranch(&(n->branch[i]), &(t->BranchBuf[rdist[i].id]), t);
531  }
532  n->count = maxkids - FORCECARD + 1;
533 }
534 
535 /*
536  * Add a branch to a node. Split the node if necessary.
537  * Returns 0 if node not split. Old node updated.
538  * Returns 1 if node split, sets *new_node to address of new node.
539  * Old node updated, becomes one of two.
540  * Returns 2 if branches were removed for forced reinsertion
541  */
542 int RTreeAddBranch(struct RTree_Branch *b, struct RTree_Node *n,
543  struct RTree_Node **newnode, struct RTree_ListBranch **ee,
544  struct RTree_Rect *cover, char *overflow, struct RTree *t)
545 {
546  int i, maxkids;
547 
548  maxkids = MAXKIDS((n)->level, t);
549 
550  if (n->count < maxkids) { /* split won't be necessary */
551  if ((n)->level > 0) { /* internal node */
552  for (i = 0; i < maxkids; i++) { /* find empty branch */
553  if (!t->valid_child(&(n->branch[i].child))) {
554  /* copy branch */
555  n->branch[i].child = b->child;
556  RTreeCopyRect(&(n->branch[i].rect), &(b->rect), t);
557  n->count++;
558  break;
559  }
560  }
561  return 0;
562  }
563  else if ((n)->level == 0) { /* leaf */
564  for (i = 0; i < maxkids; i++) { /* find empty branch */
565  if (n->branch[i].child.id == 0) {
566  /* copy branch */
567  n->branch[i].child = b->child;
568  RTreeCopyRect(&(n->branch[i].rect), &(b->rect), t);
569  n->count++;
570  break;
571  }
572  }
573  return 0;
574  }
575  }
576  else {
577  if (n->level < t->rootlevel && overflow[n->level]) {
578  /* R*-tree forced reinsert */
579  RTreeRemoveBranches(n, b, ee, cover, t);
580  overflow[n->level] = 0;
581  return 2;
582  }
583  else {
584  if (t->fd > -1)
585  RTreeInitNode(t, *newnode, NODETYPE(n->level, t->fd));
586  else
587  *newnode = RTreeAllocNode(t, (n)->level);
588  RTreeSplitNode(n, b, *newnode, t);
589  return 1;
590  }
591  }
592 
593  /* should not be reached */
594  assert(0);
595  return -1;
596 }
597 
598 /*
599  * for debugging only: print items to stdout
600  */
601 
602 void RTreeTabIn(int depth)
603 {
604  int i;
605 
606  for (i = 0; i < depth; i++)
607  putchar('\t');
608 }
609 
610 static void RTreePrintBranch(struct RTree_Branch *b, int depth, struct RTree *t)
611 {
612  RTreePrintRect(&(b->rect), depth, t);
613  RTreePrintNode(b->child.ptr, depth, t);
614 }
615 
616 /* Print out the data in a node. */
617 void RTreePrintNode(struct RTree_Node *n, int depth, struct RTree *t)
618 {
619  int i, maxkids;
620 
621  RTreeTabIn(depth);
622 
623  maxkids = (n->level > 0 ? t->nodecard : t->leafcard);
624 
625  fprintf(stdout, "node");
626  if (n->level == 0)
627  fprintf(stdout, " LEAF");
628  else if (n->level > 0)
629  fprintf(stdout, " NONLEAF");
630  else
631  fprintf(stdout, " TYPE=?");
632  fprintf(stdout, " level=%d count=%d", n->level, n->count);
633 
634  for (i = 0; i < maxkids; i++) {
635  if (n->level == 0) {
636  RTreeTabIn(depth);
637  RTreePrintRect(&(n->branch[i].rect), depth, t);
638  fprintf(stdout, "\t%d: data id = %d\n", i,
639  n->branch[i].child.id);
640  }
641  else {
642  RTreeTabIn(depth);
643  fprintf(stdout, "branch %d\n", i);
644  RTreePrintBranch(&(n->branch[i]), depth + 1, t);
645  }
646  }
647 }
648 
int RTreePickBranch(struct RTree_Rect *r, struct RTree_Node *n, struct RTree *t)
Definition: node.c:236
struct RTree_Rect rect_0 rect_1 upperrect orect
Definition: rtree.h:189
double RectReal
Definition: rtree.h:28
#define RTreeCopyRect(r1, r2, t)
Definition: index.h:99
void RTreeFreeNode(struct RTree_Node *n)
Definition: node.c:98
int level
Definition: rtree.h:80
RectReal RTreeRectSphericalVolume(struct RTree_Rect *, struct RTree *)
Definition: rect.c:435
int rootlevel
Definition: rtree.h:143
void RTreeNodeCover(struct RTree_Node *n, struct RTree_Rect *r, struct RTree *t)
Definition: node.c:136
void RTreeDisconnectBranch(struct RTree_Node *n, int i, struct RTree *t)
Definition: node.c:270
void RTreeCopyNode(struct RTree_Node *n1, struct RTree_Node *n2, struct RTree *t)
Definition: node.c:112
int count
Definition: rtree.h:79
off_t pos
Definition: rtree.h:68
struct RTree_ListBranch * next
Definition: index.h:48
#define FORCECARD
Definition: index.h:29
void free(void *)
#define NULL
Definition: ccmath.h:32
int nodecard
Definition: rtree.h:146
unsigned char ndims
Definition: rtree.h:132
#define MAXKIDS(level, t)
Definition: card.h:28
void RTreeSplitNode(struct RTree_Node *, struct RTree_Branch *, struct RTree_Node *, struct RTree *)
Definition: split.c:600
void RTreeInitNode(struct RTree *t, struct RTree_Node *n, int type)
Definition: node.c:65
rt_valid_child_fn * valid_child
Definition: rtree.h:173
void RTreeTabIn(int depth)
Definition: node.c:602
void * malloc(YYSIZE_T)
void RTreeDestroyNode(struct RTree_Node *n, int nodes)
Definition: node.c:291
void RTreeCopyBranch(struct RTree_Branch *b1, struct RTree_Branch *b2, struct RTree *t)
Definition: node.c:126
void RTreePrintNode(struct RTree_Node *n, int depth, struct RTree *t)
Definition: node.c:617
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:542
unsigned char ndims_alloc
Definition: rtree.h:134
double l
Definition: r_raster.c:39
double t
Definition: r_raster.c:39
#define assert(condition)
Definition: lz4.c:324
double b
Definition: r_raster.c:39
void RTreeFreeBoundary(struct RTree_Rect *r)
Delete the boundary of a rectangle.
Definition: rect.c:101
void RTreeCombineRect(struct RTree_Rect *, struct RTree_Rect *, struct RTree_Rect *, struct RTree *)
Definition: rect.c:505
struct RTree_Branch * BranchBuf
Definition: rtree.h:184
struct RTree_Branch * branch
Definition: rtree.h:81
void RTreeInitRect(struct RTree_Rect *, struct RTree *)
Initialize a rectangle to have all 0 coordinates.
Definition: rect.c:112
int RTreeExpandRect(struct RTree_Rect *, struct RTree_Rect *, struct RTree *)
Definition: rect.c:542
struct RTree_Node * RTreeAllocNode(struct RTree *t, int level)
Definition: node.c:77
RectReal * RTreeAllocBoundary(struct RTree *t)
Allocate the boundary array of a rectangle for a given tree.
Definition: rect.c:84
int fd
Definition: rtree.h:131
union RTree_Child child
Definition: rtree.h:74
struct RTree_Branch b
Definition: index.h:49
RectReal * center_n
Definition: rtree.h:190
RectReal * boundary
Definition: rtree.h:59
#define MAXCARD
Definition: rtree.h:46
int id
Definition: rtree.h:66
#define NODETYPE(l, fd)
Definition: index.h:31
int RTreeOverlap(struct RTree_Rect *r, struct RTree_Rect *s, struct RTree *t)
Definition: rect.c:597
void RTreePrintRect(struct RTree_Rect *R, int depth, struct RTree *t)
Definition: rect.c:307
struct RTree_Node * ptr
Definition: rtree.h:67
struct RTree_Rect rect
Definition: rtree.h:73
Definition: rtree.h:128
double r
Definition: r_raster.c:39
int leafcard
Definition: rtree.h:147