grass  7.8.6
About: GRASS (Geographic Resources Analysis Support System) is a raster- and vector-based GIS, image processing system, graphics production system and spatial modeling system.
  Fossies Dox: grass-7.8.6.tar.gz  ("unofficial" and yet experimental doxygen-generated source code documentation)  

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 */
29struct 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. */
36static 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. */
44static 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. */
52static 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
59static void (*RTreeInitBranch[3]) (struct RTree_Branch *b, struct RTree *t) = {
61};
62
63/* Initialize a Node structure. */
64/* type = 1: leaf, type = 2: internal, memory, type = 3: internal, file */
65void 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. */
77struct 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
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 */
112void 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 */
126void 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 */
136void 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
178static 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 */
236int 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. */
270void 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 */
291void 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 */
318static 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 */
330static 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 */
345static 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 */
400static 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 */
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 */
451static void RTreeReInsertBranch(struct RTree_Branch b, int level,
452 struct RTree_ListBranch **ee, struct RTree *t)
453{
454 register struct RTree_ListBranch *l;
455
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 */
468static 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 */
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
603{
604 int i;
605
606 for (i = 0; i < depth; i++)
607 putchar('\t');
608}
609
610static 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. */
617void RTreePrintNode(struct RTree_Node *n, int depth, struct RTree *t)
618{
619 int i, maxkids;
620
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) {
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 {
643 fprintf(stdout, "branch %d\n", i);
644 RTreePrintBranch(&(n->branch[i]), depth + 1, t);
645 }
646 }
647}
648
#define MAXKIDS(level, t)
Definition: card.h:28
#define NULL
Definition: ccmath.h:32
static int type
Definition: fpxdr.c:101
static int first
Definition: gsd_label.c:27
RectReal RTreeRectSphericalVolume(struct RTree_Rect *, struct RTree *)
Definition: rect.c:435
#define NODETYPE(l, fd)
Definition: index.h:31
void RTreeSplitNode(struct RTree_Node *, struct RTree_Branch *, struct RTree_Node *, struct RTree *)
Definition: split.c:600
void RTreeCombineRect(struct RTree_Rect *, struct RTree_Rect *, struct RTree_Rect *, struct RTree *)
Definition: rect.c:505
int RTreeExpandRect(struct RTree_Rect *, struct RTree_Rect *, struct RTree *)
Definition: rect.c:542
void RTreeInitRect(struct RTree_Rect *, struct RTree *)
Initialize a rectangle to have all 0 coordinates.
Definition: rect.c:112
#define RTreeCopyRect(r1, r2, t)
Definition: index.h:99
#define FORCECARD
Definition: index.h:29
#define assert(condition)
Definition: lz4.c:324
static void RTreeReInsertBranch(struct RTree_Branch b, int level, struct RTree_ListBranch **ee, struct RTree *t)
Definition: node.c:451
void RTreePrintNode(struct RTree_Node *n, int depth, struct RTree *t)
Definition: node.c:617
static int RTreeDistIsSorted(struct dist *d, int first, int last)
Definition: node.c:330
static void(* RTreeInitBranch[3])(struct RTree_Branch *b, struct RTree *t)
Definition: node.c:59
void RTreeCopyNode(struct RTree_Node *n1, struct RTree_Node *n2, struct RTree *t)
Definition: node.c:112
void RTreeCopyBranch(struct RTree_Branch *b1, struct RTree_Branch *b2, struct RTree *t)
Definition: node.c:126
void RTreeFreeNode(struct RTree_Node *n)
Definition: node.c:98
static void RTreeRemoveBranches(struct RTree_Node *n, struct RTree_Branch *b, struct RTree_ListBranch **ee, struct RTree_Rect *cover, struct RTree *t)
Definition: node.c:468
static void RTreeQuicksortDist(struct dist *d, int n)
Definition: node.c:400
static void RTreeSwapDist(struct dist *a, struct dist *b)
Definition: node.c:318
void RTreeDisconnectBranch(struct RTree_Node *n, int i, struct RTree *t)
Definition: node.c:270
static struct RTree_ListBranch * RTreeNewListBranch(struct RTree *t)
Definition: node.c:436
static void RTreePrintBranch(struct RTree_Branch *b, int depth, struct RTree *t)
Definition: node.c:610
void RTreeNodeCover(struct RTree_Node *n, struct RTree_Rect *r, struct RTree *t)
Definition: node.c:136
static int RTreePartitionDist(struct dist *d, int first, int last)
Definition: node.c:345
static void RTreeInitNodeBranchF(struct RTree_Branch *b, struct RTree *t)
Definition: node.c:44
void RTreeDestroyNode(struct RTree_Node *n, int nodes)
Definition: node.c:291
static void RTreeInitLeafBranch(struct RTree_Branch *b, struct RTree *t)
Definition: node.c:52
void RTreeTabIn(int depth)
Definition: node.c:602
struct RTree_Node * RTreeAllocNode(struct RTree *t, int level)
Definition: node.c:77
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
int RTreePickBranch(struct RTree_Rect *r, struct RTree_Node *n, struct RTree *t)
Definition: node.c:236
static void RTreeInitNodeBranchM(struct RTree_Branch *b, struct RTree *t)
Definition: node.c:36
static int RTreePickLeafBranch(struct RTree_Rect *r, struct RTree_Node *n, struct RTree *t)
Definition: node.c:178
void RTreeInitNode(struct RTree *t, struct RTree_Node *n, int type)
Definition: node.c:65
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
void RTreeFreeBoundary(struct RTree_Rect *r)
Delete the boundary of a rectangle.
Definition: rect.c:101
RectReal * RTreeAllocBoundary(struct RTree *t)
Allocate the boundary array of a rectangle for a given tree.
Definition: rect.c:84
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
#define MAXCARD
Definition: rtree.h:46
double RectReal
Definition: rtree.h:28
static int depth
Definition: sparse.c:29
struct RTree_Rect rect
Definition: rtree.h:73
union RTree_Child child
Definition: rtree.h:74
struct RTree_Branch b
Definition: index.h:49
int count
Definition: rtree.h:79
int level
Definition: rtree.h:80
struct RTree_Branch * branch
Definition: rtree.h:81
RectReal * boundary
Definition: rtree.h:59
Definition: rtree.h:129
Definition: node.c:30
int id
Definition: node.c:31
RectReal distance
Definition: node.c:32
static float d[4][4]
Definition: trans.c:49
static unsigned int a
Definition: unfl.c:8
static unsigned int c
Definition: unfl.c:8
struct RTree_Node * ptr
Definition: rtree.h:67
int id
Definition: rtree.h:66