GRASS GIS 7 Programmer's Manual  7.5.svn(2017)-r71933
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
split.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) 2001 by the GRASS Development Team
13 *
14 * This program is free software under the GNU General
15 * Public License (>=v2). Read the file COPYING that comes
16 * with GRASS for details.
17 *
18 ***********************************************************************/
19 
20 #include <stdlib.h>
21 #include <stdio.h>
22 #include <assert.h>
23 #include <float.h>
24 /* remove after debug */
25 #include <grass/gis.h>
26 #include "index.h"
27 #include "card.h"
28 #include "split.h"
29 
30 #ifndef DBL_MAX
31 #define DBL_MAX 1.797693E308 /* DBL_MAX approximation */
32 #endif
33 
34 /*----------------------------------------------------------------------
35 | Load branch buffer with branches from full node plus the extra branch.
36 ----------------------------------------------------------------------*/
37 static void RTreeGetBranches(struct RTree_Node *n, struct RTree_Branch *b,
38  RectReal *CoverSplitArea, struct RTree *t)
39 {
40  int i, maxkids = 0;
41 
42  if ((n)->level > 0) {
43  maxkids = t->nodecard;
44  /* load the branch buffer */
45  for (i = 0; i < maxkids; i++) {
46  assert(t->valid_child(&(n->branch[i].child))); /* n should have every entry full */
47  RTreeCopyBranch(&(t->BranchBuf[i]), &(n->branch[i]), t);
48  }
49  }
50  else {
51  maxkids = t->leafcard;
52  /* load the branch buffer */
53  for (i = 0; i < maxkids; i++) {
54  assert(n->branch[i].child.id); /* n should have every entry full */
55  RTreeCopyBranch(&(t->BranchBuf[i]), &(n->branch[i]), t);
56  }
57  }
58 
59  RTreeCopyBranch(&(t->BranchBuf[maxkids]), b, t);
60  t->BranchCount = maxkids + 1;
61 
62  if (METHOD == 0) { /* quadratic split */
63  /* calculate rect containing all in the set */
64  RTreeCopyRect(&(t->orect), &(t->BranchBuf[0].rect), t);
65  for (i = 1; i < maxkids + 1; i++) {
66  RTreeExpandRect(&(t->orect), &(t->BranchBuf[i].rect), t);
67  }
68  *CoverSplitArea = RTreeRectSphericalVolume(&(t->orect), t);
69  }
70 
71  RTreeInitNode(t, n, NODETYPE(n->level, t->fd));
72 }
73 
74 /*----------------------------------------------------------------------
75 | Put a branch in one of the groups.
76 ----------------------------------------------------------------------*/
77 static void RTreeClassify(int i, int group, struct RTree_PartitionVars *p,
78  struct RTree *t)
79 {
80  assert(!p->taken[i]);
81 
82  p->partition[i] = group;
83  p->taken[i] = TRUE;
84 
85  if (METHOD == 0) {
86  if (p->count[group] == 0)
87  RTreeCopyRect(&(p->cover[group]), &(t->BranchBuf[i].rect), t);
88  else
89  RTreeExpandRect(&(p->cover[group]), &(t->BranchBuf[i].rect), t);
90  p->area[group] = RTreeRectSphericalVolume(&(p->cover[group]), t);
91  }
92  p->count[group]++;
93 }
94 
95 /***************************************************
96  * *
97  * Toni Guttman's quadratic splitting method *
98  * *
99  ***************************************************/
100 
101 /*----------------------------------------------------------------------
102 | Pick two rects from set to be the first elements of the two groups.
103 | Pick the two that waste the most area if covered by a single
104 | rectangle.
105 ----------------------------------------------------------------------*/
106 static void RTreePickSeeds(struct RTree_PartitionVars *p, RectReal CoverSplitArea, struct RTree *t)
107 {
108  int i, j, seed0 = 0, seed1 = 0;
109  RectReal worst, waste, area[MAXCARD + 1];
110 
111  for (i = 0; i < p->total; i++)
112  area[i] = RTreeRectSphericalVolume(&(t->BranchBuf[i]).rect, t);
113 
114  worst = -CoverSplitArea - 1;
115  for (i = 0; i < p->total - 1; i++) {
116  for (j = i + 1; j < p->total; j++) {
117 
118  RTreeCombineRect(&(t->BranchBuf[i].rect), &(t->BranchBuf[j].rect),
119  &(t->orect), t);
120  waste =
121  RTreeRectSphericalVolume(&(t->orect), t) - area[i] - area[j];
122  if (waste > worst) {
123  worst = waste;
124  seed0 = i;
125  seed1 = j;
126  }
127  }
128  }
129  RTreeClassify(seed0, 0, p, t);
130  RTreeClassify(seed1, 1, p, t);
131 }
132 
133 /*----------------------------------------------------------------------
134 | Copy branches from the buffer into two nodes according to the
135 | partition.
136 ----------------------------------------------------------------------*/
137 static void RTreeLoadNodes(struct RTree_Node *n, struct RTree_Node *q,
138  struct RTree_PartitionVars *p, struct RTree *t)
139 {
140  int i;
141 
142  for (i = 0; i < p->total; i++) {
143  assert(p->partition[i] == 0 || p->partition[i] == 1);
144  if (p->partition[i] == 0)
145  RTreeAddBranch(&(t->BranchBuf[i]), n, NULL, NULL, NULL, NULL, t);
146  else if (p->partition[i] == 1)
147  RTreeAddBranch(&(t->BranchBuf[i]), q, NULL, NULL, NULL, NULL, t);
148  }
149 }
150 
151 /*----------------------------------------------------------------------
152 | Initialize a PartitionVars structure.
153 ----------------------------------------------------------------------*/
154 void RTreeInitPVars(struct RTree_PartitionVars *p, int maxrects, int minfill, struct RTree *t)
155 {
156  int i;
157 
158  p->count[0] = p->count[1] = 0;
159  if (METHOD == 0) {
160  RTreeNullRect(&(p->cover[0]), t);
161  RTreeNullRect(&(p->cover[1]), t);
162  p->area[0] = p->area[1] = (RectReal) 0;
163  }
164  p->total = maxrects;
165  p->minfill = minfill;
166  for (i = 0; i < maxrects; i++) {
167  p->taken[i] = FALSE;
168  p->partition[i] = -1;
169  }
170 }
171 
172 /*----------------------------------------------------------------------
173 | Print out data for a partition from PartitionVars struct.
174 | Unused, for debugging only
175 ----------------------------------------------------------------------*/
176 static void RTreePrintPVars(struct RTree_PartitionVars *p, struct RTree *t, RectReal CoverSplitArea)
177 {
178  int i;
179 
180  fprintf(stdout, "\npartition:\n");
181  for (i = 0; i < p->total; i++) {
182  fprintf(stdout, "%3d\t", i);
183  }
184  fprintf(stdout, "\n");
185  for (i = 0; i < p->total; i++) {
186  if (p->taken[i])
187  fprintf(stdout, " t\t");
188  else
189  fprintf(stdout, "\t");
190  }
191  fprintf(stdout, "\n");
192  for (i = 0; i < p->total; i++) {
193  fprintf(stdout, "%3d\t", p->partition[i]);
194  }
195  fprintf(stdout, "\n");
196 
197  fprintf(stdout, "count[0] = %d area = %f\n", p->count[0], p->area[0]);
198  fprintf(stdout, "count[1] = %d area = %f\n", p->count[1], p->area[1]);
199  if (p->area[0] + p->area[1] > 0) {
200  fprintf(stdout, "total area = %f effectiveness = %3.2f\n",
201  p->area[0] + p->area[1],
202  (float)CoverSplitArea / (p->area[0] + p->area[1]));
203  }
204  fprintf(stdout, "cover[0]:\n");
205  RTreePrintRect(&p->cover[0], 0, t);
206 
207  fprintf(stdout, "cover[1]:\n");
208  RTreePrintRect(&p->cover[1], 0, t);
209 }
210 
211 /*----------------------------------------------------------------------
212 | Method #0 for choosing a partition: this is Toni Guttman's quadratic
213 | split
214 |
215 | As the seeds for the two groups, pick the two rects that would waste
216 | the most area if covered by a single rectangle, i.e. evidently the
217 | worst pair to have in the same group. Of the remaining, one at a time
218 | is chosen to be put in one of the two groups. The one chosen is the
219 | one with the greatest difference in area expansion depending on which
220 | group - the rect most strongly attracted to one group and repelled
221 | from the other. If one group gets too full (more would force other
222 | group to violate min fill requirement) then other group gets the rest.
223 | These last are the ones that can go in either group most easily.
224 ----------------------------------------------------------------------*/
225 static void RTreeMethodZero(struct RTree_PartitionVars *p, int minfill,
226  RectReal CoverSplitArea, struct RTree *t)
227 {
228  int i;
229  RectReal biggestDiff;
230  int group, chosen = 0, betterGroup = 0;
231  struct RTree_Rect *r, *rect_0, *rect_1;
232 
233  RTreeInitPVars(p, t->BranchCount, minfill, t);
234  RTreePickSeeds(p, CoverSplitArea, t);
235 
236  rect_0 = &(t->rect_0);
237  rect_1 = &(t->rect_1);
238 
239  while (p->count[0] + p->count[1] < p->total
240  && p->count[0] < p->total - p->minfill
241  && p->count[1] < p->total - p->minfill) {
242  biggestDiff = (RectReal) - 1.;
243  for (i = 0; i < p->total; i++) {
244  if (!p->taken[i]) {
245  RectReal growth0, growth1, diff;
246 
247  r = &(t->BranchBuf[i].rect);
248  RTreeCombineRect(r, &(p->cover[0]), rect_0, t);
249  RTreeCombineRect(r, &(p->cover[1]), rect_1, t);
250  growth0 = RTreeRectSphericalVolume(rect_0, t) - p->area[0];
251  growth1 = RTreeRectSphericalVolume(rect_1, t) - p->area[1];
252  diff = growth1 - growth0;
253  if (diff >= 0)
254  group = 0;
255  else {
256  group = 1;
257  diff = -diff;
258  }
259 
260  if (diff > biggestDiff) {
261  biggestDiff = diff;
262  chosen = i;
263  betterGroup = group;
264  }
265  else if (diff == biggestDiff &&
266  p->count[group] < p->count[betterGroup]) {
267  chosen = i;
268  betterGroup = group;
269  }
270  }
271  }
272  RTreeClassify(chosen, betterGroup, p, t);
273  }
274 
275  /* if one group too full, put remaining rects in the other */
276  if (p->count[0] + p->count[1] < p->total) {
277  if (p->count[0] >= p->total - p->minfill)
278  group = 1;
279  else
280  group = 0;
281  for (i = 0; i < p->total; i++) {
282  if (!p->taken[i])
283  RTreeClassify(i, group, p, t);
284  }
285  }
286 
287  assert(p->count[0] + p->count[1] == p->total);
288  assert(p->count[0] >= p->minfill && p->count[1] >= p->minfill);
289 }
290 
291 /**********************************************************************
292  * *
293  * Norbert Beckmann's R*-tree splitting method *
294  * *
295  **********************************************************************/
296 
297 /*----------------------------------------------------------------------
298 | swap branches
299 ----------------------------------------------------------------------*/
300 static void RTreeSwapBranches(struct RTree_Branch *a, struct RTree_Branch *b, struct RTree *t)
301 {
302  RTreeCopyBranch(&(t->c), a, t);
303  RTreeCopyBranch(a, b, t);
304  RTreeCopyBranch(b, &(t->c), t);
305 }
306 
307 /*----------------------------------------------------------------------
308 | compare branches for given rectangle side
309 | return 1 if a > b
310 | return 0 if a == b
311 | return -1 if a < b
312 ----------------------------------------------------------------------*/
313 static int RTreeCompareBranches(struct RTree_Branch *a, struct RTree_Branch *b, int side)
314 {
315  if (a->rect.boundary[side] < b->rect.boundary[side])
316  return -1;
317 
318  return (a->rect.boundary[side] > b->rect.boundary[side]);
319 }
320 
321 /*----------------------------------------------------------------------
322 | check if BranchBuf is sorted along given axis (dimension)
323 ----------------------------------------------------------------------*/
324 static int RTreeBranchBufIsSorted(int first, int last, int side, struct RTree *t)
325 {
326  int i;
327 
328  for (i = first; i < last; i++) {
329  if (RTreeCompareBranches(&(t->BranchBuf[i]), &(t->BranchBuf[i + 1]), side)
330  == 1)
331  return 0;
332  }
333 
334  return 1;
335 }
336 
337 /*----------------------------------------------------------------------
338 | partition BranchBuf for quicksort along given axis (dimension)
339 ----------------------------------------------------------------------*/
340 static int RTreePartitionBranchBuf(int first, int last, int side, struct RTree *t)
341 {
342  int pivot, mid = ((first + last) >> 1);
343  int larger, smaller;
344 
345  if (last - first == 1) { /* only two items in list */
346  if (RTreeCompareBranches
347  (&(t->BranchBuf[first]), &(t->BranchBuf[last]), side) == 1) {
348  RTreeSwapBranches(&(t->BranchBuf[first]), &(t->BranchBuf[last]), t);
349  }
350  return last;
351  }
352 
353  /* larger of two */
354  larger = pivot = mid;
355  smaller = first;
356  if (RTreeCompareBranches(&(t->BranchBuf[first]), &(t->BranchBuf[mid]), side)
357  == 1) {
358  larger = pivot = first;
359  smaller = mid;
360  }
361 
362  if (RTreeCompareBranches(&(t->BranchBuf[larger]), &(t->BranchBuf[last]), side)
363  == 1) {
364  /* larger is largest, get the larger of smaller and last */
365  pivot = last;
366  if (RTreeCompareBranches
367  (&(t->BranchBuf[smaller]), &(t->BranchBuf[last]), side) == 1) {
368  pivot = smaller;
369  }
370  }
371 
372  if (pivot != last) {
373  RTreeSwapBranches(&(t->BranchBuf[pivot]), &(t->BranchBuf[last]), t);
374  }
375 
376  pivot = first;
377 
378  while (first < last) {
379  if (RTreeCompareBranches
380  (&(t->BranchBuf[first]), &(t->BranchBuf[last]), side) != 1) {
381  if (pivot != first) {
382  RTreeSwapBranches(&(t->BranchBuf[pivot]), &(t->BranchBuf[first]), t);
383  }
384  pivot++;
385  }
386  ++first;
387  }
388 
389  if (pivot != last) {
390  RTreeSwapBranches(&(t->BranchBuf[pivot]), &(t->BranchBuf[last]), t);
391  }
392 
393  return pivot;
394 }
395 
396 /*----------------------------------------------------------------------
397 | quicksort BranchBuf along given side
398 ----------------------------------------------------------------------*/
399 static void RTreeQuicksortBranchBuf(int side, struct RTree *t)
400 {
401  int pivot, first, last;
402  int s_first[MAXCARD + 1], s_last[MAXCARD + 1], stacksize;
403 
404  s_first[0] = 0;
405  s_last[0] = t->BranchCount - 1;
406 
407  stacksize = 1;
408 
409  /* use stack */
410  while (stacksize) {
411  stacksize--;
412  first = s_first[stacksize];
413  last = s_last[stacksize];
414  if (first < last) {
415  if (!RTreeBranchBufIsSorted(first, last, side, t)) {
416 
417  pivot = RTreePartitionBranchBuf(first, last, side, t);
418 
419  s_first[stacksize] = first;
420  s_last[stacksize] = pivot - 1;
421  stacksize++;
422 
423  s_first[stacksize] = pivot + 1;
424  s_last[stacksize] = last;
425  stacksize++;
426  }
427  }
428  }
429 }
430 
431 /*----------------------------------------------------------------------
432 | Method #1 for choosing a partition: this is the R*-tree method
433 |
434 | Pick the axis with the smallest margin increase (keep rectangles
435 | square).
436 | Along the chosen split axis, choose the distribution with the minimum
437 | overlap-value. Resolve ties by choosing the distribution with the
438 | minimum area-value.
439 | If one group gets too full (more would force other group to violate min
440 | fill requirement) then other group gets the rest.
441 | These last are the ones that can go in either group most easily.
442 ----------------------------------------------------------------------*/
443 static void RTreeMethodOne(struct RTree_PartitionVars *p, int minfill,
444  int maxkids, struct RTree *t)
445 {
446  int i, j, k, l, s;
447  int axis = 0, best_axis = 0, side = 0;
448  RectReal margin, smallest_margin = 0;
449  struct RTree_Rect *r1, *r2;
450  struct RTree_Rect *rect_0, *rect_1, *orect, *upperrect;
451  int minfill1 = minfill - 1;
452  RectReal overlap, vol, smallest_overlap = -1, smallest_vol = -1;
453 
454  static int *best_cut = NULL, *best_side = NULL;
455  static int one_init = 0;
456 
457  if (!one_init) {
458  best_cut = (int *)malloc(MAXLEVEL * sizeof(int));
459  best_side = (int *)malloc(MAXLEVEL * sizeof(int));
460  one_init = 1;
461  }
462 
463  rect_0 = &(t->rect_0);
464  rect_1 = &(t->rect_1);
465  orect = &(t->orect);
466  upperrect = &(t->upperrect);
467 
468  RTreeInitPVars(p, t->BranchCount, minfill, t);
469  RTreeInitRect(orect, t);
470 
471  margin = DBL_MAX;
472 
473  /* choose split axis */
474  /* For each dimension, sort rectangles first by lower boundary then
475  * by upper boundary. Get the smallest margin. */
476  for (i = 0; i < t->ndims; i++) {
477  axis = i;
478  best_cut[i] = 0;
479  best_side[i] = 0;
480 
481  smallest_overlap = DBL_MAX;
482  smallest_vol = DBL_MAX;
483 
484  /* first upper then lower bounds for each axis */
485  s = 1;
486  do {
487  RTreeQuicksortBranchBuf(i + s * t->ndims_alloc, t);
488 
489  side = s;
490 
491  RTreeCopyRect(rect_0, &(t->BranchBuf[0].rect), t);
492  RTreeCopyRect(upperrect, &(t->BranchBuf[maxkids].rect), t);
493 
494  for (j = 1; j < minfill1; j++) {
495  r1 = &(t->BranchBuf[j].rect);
496  RTreeExpandRect(rect_0, r1, t);
497  r2 = &(t->BranchBuf[maxkids - j].rect);
498  RTreeExpandRect(upperrect, r2, t);
499  }
500  r2 = &(t->BranchBuf[maxkids - minfill1].rect);
501  RTreeExpandRect(upperrect, r2, t);
502 
503  /* check distributions for this axis, adhere the minimum node fill */
504  for (j = minfill1; j < t->BranchCount - minfill; j++) {
505 
506  r1 = &(t->BranchBuf[j].rect);
507  RTreeExpandRect(rect_0, r1, t);
508 
509  RTreeCopyRect(rect_1, upperrect, t);
510  for (k = j + 1; k < t->BranchCount - minfill; k++) {
511  r2 = &(t->BranchBuf[k].rect);
512  RTreeExpandRect(rect_1, r2, t);
513  }
514 
515  /* the margin is the sum of the lengths of the edges of a rectangle */
516  margin =
517  RTreeRectMargin(rect_0, t) +
518  RTreeRectMargin(rect_1, t);
519 
520  /* remember best axis */
521  if (margin <= smallest_margin) {
522  smallest_margin = margin;
523  best_axis = i;
524  }
525 
526  /* remember best distribution for this axis */
527 
528  /* overlap size */
529  overlap = 1;
530 
531  for (k = 0; k < t->ndims; k++) {
532  /* no overlap */
533  if (rect_0->boundary[k] > rect_1->boundary[k + t->ndims_alloc] ||
534  rect_0->boundary[k + t->ndims_alloc] < rect_1->boundary[k]) {
535  overlap = 0;
536  break;
537  }
538  /* get overlap */
539  else {
540  if (rect_0->boundary[k] > rect_1->boundary[k])
541  orect->boundary[k] = rect_0->boundary[k];
542  else
543  orect->boundary[k] = rect_1->boundary[k];
544 
545  l = k + t->ndims_alloc;
546  if (rect_0->boundary[l] < rect_1->boundary[l])
547  orect->boundary[l] = rect_0->boundary[l];
548  else
549  orect->boundary[l] = rect_1->boundary[l];
550  }
551  }
552  if (overlap)
553  overlap = RTreeRectVolume(orect, t);
554 
555  vol =
556  RTreeRectVolume(rect_0, t) +
557  RTreeRectVolume(rect_1, t);
558 
559  /* get best cut for this axis */
560  if (overlap <= smallest_overlap) {
561  smallest_overlap = overlap;
562  smallest_vol = vol;
563  best_cut[i] = j;
564  best_side[i] = s;
565  }
566  else if (overlap == smallest_overlap) {
567  /* resolve ties by minimum volume */
568  if (vol <= smallest_vol) {
569  smallest_vol = vol;
570  best_cut[i] = j;
571  best_side[i] = s;
572  }
573  }
574  } /* end of distribution check */
575  } while (s--); /* end of side check */
576  } /* end of axis check */
577 
578  /* Use best distribution to classify branches */
579  if (best_axis != axis || best_side[best_axis] != side)
580  RTreeQuicksortBranchBuf(best_axis + best_side[best_axis] * t->ndims_alloc, t);
581 
582  best_cut[best_axis]++;
583 
584  for (i = 0; i < best_cut[best_axis]; i++)
585  RTreeClassify(i, 0, p, t);
586 
587  for (i = best_cut[best_axis]; i < t->BranchCount; i++)
588  RTreeClassify(i, 1, p, t);
589 
590  assert(p->count[0] + p->count[1] == p->total);
591  assert(p->count[0] >= p->minfill && p->count[1] >= p->minfill);
592 }
593 
594 /*----------------------------------------------------------------------
595 | Split a node.
596 | Divides the nodes branches and the extra one between two nodes.
597 | Old node is one of the new ones, and one really new one is created.
598 | May use quadratic split or R*-tree split.
599 ----------------------------------------------------------------------*/
600 void RTreeSplitNode(struct RTree_Node *n, struct RTree_Branch *b,
601  struct RTree_Node *nn, struct RTree *t)
602 {
603  struct RTree_PartitionVars *p;
604  RectReal CoverSplitArea;
605  int level;
606 
607  /* load all the branches into a buffer, initialize old node */
608  level = n->level;
609  RTreeGetBranches(n, b, &CoverSplitArea, t);
610 
611  /* find partition */
612  p = &(t->p);
613 
614  if (METHOD == 1) /* R* split */
615  RTreeMethodOne(&(t->p), MINFILL(level, t), MAXKIDS(level, t), t);
616  else
617  RTreeMethodZero(&(t->p), MINFILL(level, t), CoverSplitArea, t);
618 
619  /*
620  * put branches from buffer into 2 nodes
621  * according to chosen partition
622  */
623  (nn)->level = n->level = level;
624  RTreeLoadNodes(n, nn, p, t);
625  assert(n->count + nn->count == p->total);
626 }
#define TRUE
Definition: gis.h:49
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
int level
Definition: rtree.h:80
RectReal RTreeRectSphericalVolume(struct RTree_Rect *, struct RTree *)
Definition: rect.c:435
int partition[MAXCARD+1]
Definition: rtree.h:120
#define METHOD
Definition: split.h:25
RectReal RTreeRectMargin(struct RTree_Rect *, struct RTree *)
Definition: rect.c:487
RectReal RTreeRectVolume(struct RTree_Rect *, struct RTree *)
Definition: rect.c:325
#define MAXLEVEL
Maximum verbosity level.
Definition: verbose.c:30
int count
Definition: rtree.h:79
void RTreeNullRect(struct RTree_Rect *, struct RTree *)
Definition: rect.c:227
#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 * malloc(YYSIZE_T)
unsigned char ndims_alloc
Definition: rtree.h:134
double l
Definition: r_raster.c:39
double t
Definition: r_raster.c:39
double b
Definition: r_raster.c:39
void RTreeCombineRect(struct RTree_Rect *, struct RTree_Rect *, struct RTree_Rect *, struct RTree *)
Definition: rect.c:505
#define FALSE
Definition: gis.h:53
struct RTree_Branch tmpb1 tmpb2 c
Definition: rtree.h:186
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
int RTreeAddBranch(struct RTree_Branch *, struct RTree_Node *, struct RTree_Node **, struct RTree_ListBranch **, struct RTree_Rect *, char *, struct RTree *)
Definition: node.c:542
int fd
Definition: rtree.h:131
union RTree_Child child
Definition: rtree.h:74
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
void RTreeCopyBranch(struct RTree_Branch *, struct RTree_Branch *, struct RTree *)
Definition: node.c:126
int BranchCount
Definition: rtree.h:187
#define MINFILL(level, t)
Definition: card.h:29
#define DBL_MAX
Definition: split.c:31
void RTreePrintRect(struct RTree_Rect *R, int depth, struct RTree *t)
Definition: rect.c:307
void RTreeInitPVars(struct RTree_PartitionVars *p, int maxrects, int minfill, struct RTree *t)
Definition: split.c:154
struct RTree_Rect rect
Definition: rtree.h:73
Definition: rtree.h:128
struct RTree_Rect cover[2]
Definition: rtree.h:124
double r
Definition: r_raster.c:39
int leafcard
Definition: rtree.h:147
int taken[MAXCARD+1]
Definition: rtree.h:122
struct RTree_PartitionVars p
Definition: rtree.h:183
RectReal area[2]
Definition: rtree.h:125