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)  

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----------------------------------------------------------------------*/
37static 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----------------------------------------------------------------------*/
77static 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----------------------------------------------------------------------*/
106static 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----------------------------------------------------------------------*/
137static 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----------------------------------------------------------------------*/
154void 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----------------------------------------------------------------------*/
176static 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----------------------------------------------------------------------*/
225static 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----------------------------------------------------------------------*/
300static 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----------------------------------------------------------------------*/
313static 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----------------------------------------------------------------------*/
324static 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----------------------------------------------------------------------*/
340static 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 */
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;
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) {
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----------------------------------------------------------------------*/
399static 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----------------------------------------------------------------------*/
443static 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----------------------------------------------------------------------*/
600void 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 MAXKIDS(level, t)
Definition: card.h:28
#define MINFILL(level, t)
Definition: card.h:29
#define NULL
Definition: ccmath.h:32
#define TRUE
Definition: gis.h:59
#define FALSE
Definition: gis.h:63
static int first
Definition: gsd_label.c:27
int RTreeAddBranch(struct RTree_Branch *, struct RTree_Node *, struct RTree_Node **, struct RTree_ListBranch **, struct RTree_Rect *, char *, struct RTree *)
Definition: node.c:542
RectReal RTreeRectSphericalVolume(struct RTree_Rect *, struct RTree *)
Definition: rect.c:435
void RTreeNullRect(struct RTree_Rect *, struct RTree *)
Definition: rect.c:227
#define NODETYPE(l, fd)
Definition: index.h:31
void RTreeCopyBranch(struct RTree_Branch *, struct RTree_Branch *, struct RTree *)
Definition: node.c:126
RectReal RTreeRectVolume(struct RTree_Rect *, struct RTree *)
Definition: rect.c:325
RectReal RTreeRectMargin(struct RTree_Rect *, struct RTree *)
Definition: rect.c:487
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 assert(condition)
Definition: lz4.c:324
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 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
void RTreeInitPVars(struct RTree_PartitionVars *p, int maxrects, int minfill, struct RTree *t)
Definition: split.c:154
static void RTreeGetBranches(struct RTree_Node *n, struct RTree_Branch *b, RectReal *CoverSplitArea, struct RTree *t)
Definition: split.c:37
static void RTreeSwapBranches(struct RTree_Branch *a, struct RTree_Branch *b, struct RTree *t)
Definition: split.c:300
static void RTreeMethodOne(struct RTree_PartitionVars *p, int minfill, int maxkids, struct RTree *t)
Definition: split.c:443
static void RTreePickSeeds(struct RTree_PartitionVars *p, RectReal CoverSplitArea, struct RTree *t)
Definition: split.c:106
static int RTreePartitionBranchBuf(int first, int last, int side, struct RTree *t)
Definition: split.c:340
void RTreeSplitNode(struct RTree_Node *n, struct RTree_Branch *b, struct RTree_Node *nn, struct RTree *t)
Definition: split.c:600
static void RTreeClassify(int i, int group, struct RTree_PartitionVars *p, struct RTree *t)
Definition: split.c:77
static void RTreeQuicksortBranchBuf(int side, struct RTree *t)
Definition: split.c:399
static void RTreeMethodZero(struct RTree_PartitionVars *p, int minfill, RectReal CoverSplitArea, struct RTree *t)
Definition: split.c:225
static void RTreeLoadNodes(struct RTree_Node *n, struct RTree_Node *q, struct RTree_PartitionVars *p, struct RTree *t)
Definition: split.c:137
static void RTreePrintPVars(struct RTree_PartitionVars *p, struct RTree *t, RectReal CoverSplitArea)
Definition: split.c:176
static int RTreeBranchBufIsSorted(int first, int last, int side, struct RTree *t)
Definition: split.c:324
#define DBL_MAX
Definition: split.c:31
static int RTreeCompareBranches(struct RTree_Branch *a, struct RTree_Branch *b, int side)
Definition: split.c:313
#define METHOD
Definition: split.h:25
union RTree_Child child
Definition: rtree.h:74
int count
Definition: rtree.h:79
int level
Definition: rtree.h:80
struct RTree_Branch * branch
Definition: rtree.h:81
int taken[9+1]
Definition: rtree.h:122
RectReal area[2]
Definition: rtree.h:125
struct RTree_Rect cover[2]
Definition: rtree.h:124
int partition[9+1]
Definition: rtree.h:120
RectReal * boundary
Definition: rtree.h:59
Definition: rtree.h:129
static unsigned int a
Definition: unfl.c:8
static unsigned int s
Definition: unfl.c:9
int id
Definition: rtree.h:66
#define MAXLEVEL
Maximum verbosity level.
Definition: verbose.c:30