← Back to branch summary

~ubuntu-branches/ubuntu/vivid/grass/vivid-proposed

« back to all changes in this revision

Viewing changes to lib/vector/rtree/node.c

  • Committer: Package Import Robot
  • Author(s): Bas Couwenberg
  • Date: 2015-02-20 23:12:08 UTC
  • mfrom: (8.2.6 experimental)
  • Revision ID: package-import@ubuntu.com-20150220231208-1u6qvqm84v430b10
Tags: 7.0.0-1~exp1
* New upstream release.
* Update python-ctypes-ternary.patch to use if/else instead of and/or.
* Drop check4dev patch, rely on upstream check.
* Add build dependency on libpq-dev to grass-dev for libpq-fe.h.
* Drop patches applied upstream, refresh remaining patches.
* Update symlinks for images switched from jpg to png.

Show diffs side-by-side

added added

removed removed

Lines of Context:
lib/vector/rtree/node.c
5
5
* AUTHOR(S):    Antonin Guttman - original code
6
6
*               Daniel Green (green@superliminal.com) - major clean-up
7
7
*                               and implementation of bounding spheres
 
8
*               Markus Metz - file-based and memory-based R*-tree
8
9
*               
9
10
* PURPOSE:      Multidimensional index
10
11
*
11
 
* COPYRIGHT:    (C) 2001 by the GRASS Development Team
 
12
* COPYRIGHT:    (C) 2010 by the GRASS Development Team
12
13
*
13
14
*               This program is free software under the GNU General Public
14
15
*               License (>=v2). Read the file COPYING that comes with GRASS
17
18
 
18
19
#include <stdio.h>
19
20
#include <stdlib.h>
20
 
#include "assert.h"
 
21
#include <string.h>
 
22
#include <assert.h>
 
23
#include <grass/gis.h>
21
24
#include "index.h"
 
25
#include "split.h"
22
26
#include "card.h"
23
27
 
24
 
/* Initialize one branch cell in a node. */
25
 
static void RTreeInitBranch(struct Branch *b)
26
 
{
27
 
    RTreeInitRect(&(b->rect));
28
 
    b->child = NULL;
29
 
}
 
28
/* rectangle distances for forced removal */
 
29
struct 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. */
 
36
static 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. */
 
44
static 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. */
 
52
static 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
 
 
59
static void (*RTreeInitBranch[3]) (struct RTree_Branch *b, struct RTree *t) = {
 
60
    RTreeInitLeafBranch, RTreeInitNodeBranchM, RTreeInitNodeBranchF
 
61
};
30
62
 
31
63
/* Initialize a Node structure. */
32
 
void RTreeInitNode(struct Node *N)
 
64
/* type = 1: leaf, type = 2: internal, memory, type = 3: internal, file */
 
65
void RTreeInitNode(struct RTree *t, struct RTree_Node *n, int type)
33
66
{
34
 
    register struct Node *n = N;
35
 
    register int i;
 
67
    int i;
36
68
 
37
69
    n->count = 0;
38
70
    n->level = -1;
 
71
 
39
72
    for (i = 0; i < MAXCARD; i++)
40
 
        RTreeInitBranch(&(n->branch[i]));
 
73
        RTreeInitBranch[type](&(n->branch[i]), t);
41
74
}
42
75
 
43
76
/* Make a new node and initialize to have all branch cells empty. */
44
 
struct Node *RTreeNewNode(void)
 
77
struct RTree_Node *RTreeAllocNode(struct RTree *t, int level)
45
78
{
46
 
    register struct Node *n;
 
79
    int i;
 
80
    struct RTree_Node *n;
47
81
 
48
 
    /* n = new Node; */
49
 
    n = (struct Node *)malloc(sizeof(struct Node));
 
82
    n = (struct RTree_Node *)malloc(sizeof(struct RTree_Node));
50
83
    assert(n);
51
 
    RTreeInitNode(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++) {
 
91
        n->branch[i].rect.boundary = RTreeAllocBoundary(t);
 
92
        RTreeInitBranch[NODETYPE(level, t->fd)](&(n->branch[i]), t);
 
93
    }
 
94
 
52
95
    return n;
53
96
}
54
97
 
55
 
void RTreeFreeNode(struct Node *p)
56
 
{
57
 
    assert(p);
58
 
    /* delete p; */
59
 
    free(p);
60
 
}
61
 
 
62
 
static void RTreePrintBranch(struct Branch *b, int depth)
63
 
{
64
 
    RTreePrintRect(&(b->rect), depth);
65
 
    RTreePrintNode(b->child, depth);
66
 
}
67
 
 
68
 
extern void RTreeTabIn(int depth)
69
 
{
70
 
    int i;
71
 
 
72
 
    for (i = 0; i < depth; i++)
73
 
        putchar('\t');
74
 
}
75
 
 
76
 
/* Print out the data in a node. */
77
 
void RTreePrintNode(struct Node *n, int depth)
 
98
void RTreeFreeNode(struct RTree_Node *n)
78
99
{
79
100
    int i;
80
101
 
81
102
    assert(n);
82
103
 
83
 
    RTreeTabIn(depth);
84
 
    fprintf(stdout, "node");
85
 
    if (n->level == 0)
86
 
        fprintf(stdout, " LEAF");
87
 
    else if (n->level > 0)
88
 
        fprintf(stdout, " NONLEAF");
89
 
    else
90
 
        fprintf(stdout, " TYPE=?");
91
 
    fprintf(stdout, "  level=%d  count=%d  address=%o\n", n->level, n->count,
92
 
            (unsigned)n);
93
 
 
94
 
    for (i = 0; i < n->count; i++) {
95
 
        if (n->level == 0) {
96
 
            /* RTreeTabIn(depth); */
97
 
            /* fprintf (stdout, "\t%d: data = %d\n", i, n->branch[i].child); */
98
 
        }
99
 
        else {
100
 
            RTreeTabIn(depth);
101
 
            fprintf(stdout, "branch %d\n", i);
102
 
            RTreePrintBranch(&n->branch[i], depth + 1);
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 */
 
112
void 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);
104
122
    }
105
123
}
106
124
 
 
125
/* copy branch 2 to branch 1 */
 
126
void 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
 
107
132
/*
108
133
 * Find the smallest rectangle that includes all rectangles in
109
134
 * branches of a node.
110
135
 */
111
 
struct Rect RTreeNodeCover(struct Node *N)
112
 
{
113
 
    register struct Node *n = N;
114
 
    register int i, first_time = 1;
115
 
    struct Rect r;
116
 
 
117
 
    assert(n);
118
 
 
119
 
    RTreeInitRect(&r);
120
 
    for (i = 0; i < MAXKIDS(n); i++)
121
 
        if (n->branch[i].child) {
122
 
            if (first_time) {
123
 
                r = n->branch[i].rect;
124
 
                first_time = 0;
125
 
            }
126
 
            else
127
 
                r = RTreeCombineRect(&r, &(n->branch[i].rect));
128
 
        }
129
 
    return r;
 
136
void 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 accomodate the new rectangle, then the smallest area before,
 
175
 * to get the best resolution when searching.
 
176
 */
 
177
 
 
178
static 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;
130
227
}
131
228
 
132
229
/*
136
233
 * In case of a tie, pick the one which was smaller before, to get
137
234
 * the best resolution when searching.
138
235
 */
139
 
int RTreePickBranch(struct Rect *R, struct Node *N)
 
236
int RTreePickBranch(struct RTree_Rect *r, struct RTree_Node *n, struct RTree *t)
140
237
{
141
 
    register struct Rect *r = R;
142
 
    register struct Node *n = N;
143
 
    register struct Rect *rr;
144
 
    register int i, first_time = 1;
145
 
    RectReal increase, bestIncr = (RectReal) - 1, area, bestArea = 0;
 
238
    struct RTree_Rect *rr;
 
239
    int i, first_time = 1;
 
240
    RectReal increase, bestIncr = (RectReal) -1, area, bestArea = 0;
146
241
    int best = 0;
147
 
    struct Rect tmp_rect;
148
 
 
149
 
    assert(r && n);
150
 
 
151
 
    for (i = 0; i < MAXKIDS(n); i++) {
152
 
        if (n->branch[i].child) {
 
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))) {
153
250
            rr = &n->branch[i].rect;
154
 
            area = RTreeRectSphericalVolume(rr);
155
 
            tmp_rect = RTreeCombineRect(r, rr);
156
 
            increase = RTreeRectSphericalVolume(&tmp_rect) - area;
 
251
            area = RTreeRectSphericalVolume(rr, t);
 
252
            RTreeCombineRect(r, rr, &(t->orect), t);
 
253
            increase = RTreeRectSphericalVolume(&(t->orect), t) - area;
157
254
            if (increase < bestIncr || first_time) {
158
255
                best = i;
159
256
                bestArea = area;
163
260
            else if (increase == bestIncr && area < bestArea) {
164
261
                best = i;
165
262
                bestArea = area;
166
 
                bestIncr = increase;
167
263
            }
168
264
        }
169
265
    }
170
266
    return best;
171
267
}
172
268
 
173
 
/*
174
 
 * Add a branch to a node.  Split the node if necessary.
175
 
 * Returns 0 if node not split.  Old node updated.
176
 
 * Returns 1 if node split, sets *new_node to address of new node.
177
 
 * Old node updated, becomes one of two.
178
 
 */
179
 
int RTreeAddBranch(struct Branch *B, struct Node *N, struct Node **New_node)
180
 
{
181
 
    register struct Branch *b = B;
182
 
    register struct Node *n = N;
183
 
    register struct Node **new_node = New_node;
184
 
    register int i;
185
 
 
186
 
    assert(b);
187
 
    assert(n);
188
 
 
189
 
    if (n->count < MAXKIDS(n)) {        /* split won't be necessary */
190
 
        for (i = 0; i < MAXKIDS(n); i++) {      /* find empty branch */
191
 
            if (n->branch[i].child == NULL) {
192
 
                n->branch[i] = *b;
193
 
                n->count++;
194
 
                break;
195
 
            }
196
 
        }
197
 
        return 0;
198
 
    }
199
 
    else {
200
 
        assert(new_node);
201
 
        RTreeSplitNode(n, b, new_node);
202
 
        return 1;
203
 
    }
204
 
}
205
 
 
206
269
/* Disconnect a dependent node. */
207
 
void RTreeDisconnectBranch(struct Node *n, int i)
 
270
void RTreeDisconnectBranch(struct RTree_Node *n, int i, struct RTree *t)
208
271
{
209
 
    assert(n && i >= 0 && i < MAXKIDS(n));
210
 
    assert(n->branch[i].child);
 
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
    }
211
285
 
212
 
    RTreeInitBranch(&(n->branch[i]));
213
286
    n->count--;
214
287
}
215
288
 
216
289
/* Destroy (free) node recursively. */
217
 
void RTreeDestroyNode(struct Node *n)
 
290
/* NOTE: only needed for memory based index */
 
291
void RTreeDestroyNode(struct RTree_Node *n, int nodes)
218
292
{
219
293
    int i;
220
294
 
221
295
    if (n->level > 0) {         /* it is not leaf -> destroy childs */
222
 
        for (i = 0; i < NODECARD; i++) {
223
 
            if (n->branch[i].child) {
224
 
                RTreeDestroyNode(n->branch[i].child);
 
296
        for (i = 0; i < nodes; i++) {
 
297
            if (n->branch[i].child.ptr) {
 
298
                RTreeDestroyNode(n->branch[i].child.ptr, nodes);
225
299
            }
226
300
        }
227
301
    }
228
302
 
229
303
    /* Free this node */
230
304
    RTreeFreeNode(n);
231
 
}
 
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
 */
 
318
static 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
 */
 
330
static 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
 */
 
345
static 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
 */
 
400
static 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
 */
 
436
static struct RTree_ListBranch *RTreeNewListBranch(struct RTree *t)
 
437
{
 
438
    struct RTree_ListBranch *p = 
 
439
       (struct RTree_ListBranch *)malloc(sizeof(struct RTree_ListBranch));
 
440
 
 
441
    assert(p);
 
442
    p->b.rect.boundary = RTreeAllocBoundary(t);
 
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
 */
 
451
static void RTreeReInsertBranch(struct RTree_Branch b, int level,
 
452
                                struct RTree_ListBranch **ee, struct RTree *t)
 
453
{
 
454
    register struct RTree_ListBranch *l;
 
455
 
 
456
    l = RTreeNewListBranch(t);
 
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
 */
 
468
static 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
 */
 
542
int RTreeAddBranch(struct RTree_Branch *b, struct RTree_Node *n,
 
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
 
 
602
void RTreeTabIn(int depth)
 
603
{
 
604
    int i;
 
605
 
 
606
    for (i = 0; i < depth; i++)
 
607
        putchar('\t');
 
608
}
 
609
 
 
610
static 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. */
 
617
void RTreePrintNode(struct RTree_Node *n, int depth, struct RTree *t)
 
618
{
 
619
    int i, maxkids;
 
620
 
 
621
    RTreeTabIn(depth);
 
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) {
 
636
            RTreeTabIn(depth);
 
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 {
 
642
            RTreeTabIn(depth);
 
643
            fprintf(stdout, "branch %d\n", i);
 
644
            RTreePrintBranch(&(n->branch[i]), depth + 1, t);
 
645
        }
 
646
    }
 
647
}
 
648