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