31 #define DBL_MAX 1.797693E308 45 for (i = 0; i < maxkids; i++) {
53 for (i = 0; i < maxkids; i++) {
65 for (i = 1; i < maxkids + 1; i++) {
86 if (p->
count[group] == 0)
108 int i, j, seed0 = 0, seed1 = 0;
111 for (i = 0; i < p->
total; i++)
114 worst = -CoverSplitArea - 1;
115 for (i = 0; i < p->
total - 1; i++) {
116 for (j = i + 1; j < p->
total; j++) {
129 RTreeClassify(seed0, 0, p, t);
130 RTreeClassify(seed1, 1, p, t);
142 for (i = 0; i < p->
total; i++) {
166 for (i = 0; i < maxrects; i++) {
180 fprintf(stdout,
"\npartition:\n");
181 for (i = 0; i < p->
total; i++) {
182 fprintf(stdout,
"%3d\t", i);
184 fprintf(stdout,
"\n");
185 for (i = 0; i < p->
total; i++) {
187 fprintf(stdout,
" t\t");
189 fprintf(stdout,
"\t");
191 fprintf(stdout,
"\n");
192 for (i = 0; i < p->
total; i++) {
193 fprintf(stdout,
"%3d\t", p->
partition[i]);
195 fprintf(stdout,
"\n");
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]);
200 fprintf(stdout,
"total area = %f effectiveness = %3.2f\n",
202 (
float)CoverSplitArea / (p->
area[0] + p->
area[1]));
204 fprintf(stdout,
"cover[0]:\n");
207 fprintf(stdout,
"cover[1]:\n");
230 int group, chosen = 0, betterGroup = 0;
234 RTreePickSeeds(p, CoverSplitArea, t);
236 rect_0 = &(t->rect_0);
237 rect_1 = &(t->rect_1);
243 for (i = 0; i < p->
total; i++) {
252 diff = growth1 - growth0;
260 if (diff > biggestDiff) {
265 else if (diff == biggestDiff &&
272 RTreeClassify(chosen, betterGroup, p, t);
281 for (i = 0; i < p->
total; i++) {
283 RTreeClassify(i, group, p, t);
324 static int RTreeBranchBufIsSorted(
int first,
int last,
int side,
struct RTree *t)
328 for (i = first; i < last; i++) {
340 static int RTreePartitionBranchBuf(
int first,
int last,
int side,
struct RTree *t)
342 int pivot, mid = ((first + last) >> 1);
345 if (last - first == 1) {
346 if (RTreeCompareBranches
354 larger = pivot = mid;
358 larger = pivot = first;
366 if (RTreeCompareBranches
378 while (first < last) {
379 if (RTreeCompareBranches
381 if (pivot != first) {
399 static void RTreeQuicksortBranchBuf(
int side,
struct RTree *t)
401 int pivot, first, last;
412 first = s_first[stacksize];
413 last = s_last[stacksize];
415 if (!RTreeBranchBufIsSorted(first, last, side, t)) {
417 pivot = RTreePartitionBranchBuf(first, last, side, t);
419 s_first[stacksize] = first;
420 s_last[stacksize] = pivot - 1;
423 s_first[stacksize] = pivot + 1;
424 s_last[stacksize] = last;
444 int maxkids,
struct RTree *t)
447 int axis = 0, best_axis = 0, side = 0;
448 RectReal margin, smallest_margin = 0;
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;
454 static int *best_cut =
NULL, *best_side =
NULL;
455 static int one_init = 0;
463 rect_0 = &(t->rect_0);
464 rect_1 = &(t->rect_1);
466 upperrect = &(t->upperrect);
476 for (i = 0; i < t->
ndims; i++) {
487 RTreeQuicksortBranchBuf(i + s * t->
ndims_alloc, t);
494 for (j = 1; j < minfill1; j++) {
504 for (j = minfill1; j < t->
BranchCount - minfill; j++) {
510 for (k = j + 1; k < t->
BranchCount - minfill; k++) {
521 if (margin <= smallest_margin) {
522 smallest_margin = margin;
531 for (k = 0; k < t->
ndims; k++) {
560 if (overlap <= smallest_overlap) {
561 smallest_overlap = overlap;
566 else if (overlap == smallest_overlap) {
568 if (vol <= smallest_vol) {
579 if (best_axis != axis || best_side[best_axis] != side)
580 RTreeQuicksortBranchBuf(best_axis + best_side[best_axis] * t->
ndims_alloc, t);
582 best_cut[best_axis]++;
584 for (i = 0; i < best_cut[best_axis]; i++)
585 RTreeClassify(i, 0, p, t);
587 for (i = best_cut[best_axis]; i < t->
BranchCount; i++)
588 RTreeClassify(i, 1, p, t);
609 RTreeGetBranches(n, b, &CoverSplitArea, t);
617 RTreeMethodZero(&(t->
p),
MINFILL(level, t), CoverSplitArea, t);
623 (nn)->level = n->
level = level;
624 RTreeLoadNodes(n, nn, p, t);
struct RTree_Rect rect_0 rect_1 upperrect orect
#define RTreeCopyRect(r1, r2, t)
RectReal RTreeRectSphericalVolume(struct RTree_Rect *, struct RTree *)
RectReal RTreeRectMargin(struct RTree_Rect *, struct RTree *)
RectReal RTreeRectVolume(struct RTree_Rect *, struct RTree *)
#define MAXLEVEL
Maximum verbosity level.
void RTreeNullRect(struct RTree_Rect *, struct RTree *)
#define MAXKIDS(level, t)
void RTreeInitNode(struct RTree *t, struct RTree_Node *n, int type)
rt_valid_child_fn * valid_child
unsigned char ndims_alloc
#define assert(condition)
void RTreeCombineRect(struct RTree_Rect *, struct RTree_Rect *, struct RTree_Rect *, struct RTree *)
struct RTree_Branch tmpb1 tmpb2 c
struct RTree_Branch * BranchBuf
struct RTree_Branch * branch
void RTreeInitRect(struct RTree_Rect *, struct RTree *)
Initialize a rectangle to have all 0 coordinates.
int RTreeExpandRect(struct RTree_Rect *, struct RTree_Rect *, struct RTree *)
int RTreeAddBranch(struct RTree_Branch *, struct RTree_Node *, struct RTree_Node **, struct RTree_ListBranch **, struct RTree_Rect *, char *, struct RTree *)
void RTreeSplitNode(struct RTree_Node *n, struct RTree_Branch *b, struct RTree_Node *nn, struct RTree *t)
void RTreeCopyBranch(struct RTree_Branch *, struct RTree_Branch *, struct RTree *)
#define MINFILL(level, t)
void RTreePrintRect(struct RTree_Rect *R, int depth, struct RTree *t)
void RTreeInitPVars(struct RTree_PartitionVars *p, int maxrects, int minfill, struct RTree *t)
struct RTree_Rect cover[2]
struct RTree_PartitionVars p