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)  

index.c
Go to the documentation of this file.
1/*!
2 \file lib/vector/rtree/index.c
3
4 \brief R-Tree library - Multidimensional index
5
6 Higher level functions for managing R*-Trees.
7
8 (C) 2010-2012 by the GRASS Development Team
9
10 This program is free software under the
11 GNU General Public License (>=v2).
12 Read the file COPYING that comes with GRASS
13 for details.
14
15 \author Antonin Guttman - original code
16 \author Daniel Green (green@superliminal.com) - major clean-up
17 and implementation of bounding spheres
18 \author Markus Metz - file-based and memory-based R*-tree
19 */
20
21/* Read these articles first before attempting to modify the code
22 *
23 * R-Tree reference:
24 * Guttman, A. (1984). "R-Trees: A Dynamic Index Structure for Spatial
25 * Searching". Proceedings of the 1984 ACM SIGMOD international
26 * conference on Management of data - SIGMOD '84. pp. 47.
27 * DOI:10.1145/602259.602266
28 * ISBN 0897911288
29 *
30 * R*-Tree reference:
31 * Beckmann, N.; Kriegel, H. P.; Schneider, R.; Seeger, B. (1990).
32 * "The R*-tree: an efficient and robust access method for points and
33 * rectangles". Proceedings of the 1990 ACM SIGMOD international
34 * conference on Management of data - SIGMOD '90. pp. 322.
35 * DOI:10.1145/93597.98741
36 * ISBN 0897913655
37 */
38
39#include <stdlib.h>
40#include <sys/types.h>
41#include <unistd.h>
42#include <assert.h>
43#include <grass/gis.h>
44#include "index.h"
45
46/*!
47 \brief Create new empty R*-Tree
48
49 This method creates a new RTree, either in memory (fd < 0) or in file.
50 If the file descriptor is positive, the corresponding file must have
51 been opened for reading and writing.
52 This method must also be called if an existing tree previously saved
53 to file is going to be accessed.
54
55 \param fd file descriptor to hold data, negative toggles memory mode
56 \param rootpos offset in file to root node (past any header info)
57 \param ndims number of dimensions for the new tree: min 2, max 20
58
59 \return pointer to new RTree structure
60*/
61struct RTree *RTreeCreateTree(int fd, off_t rootpos, int ndims)
62{
63 struct RTree *new_rtree;
64 struct RTree_Node *n;
65 int i, j, k;
66
67 new_rtree = (struct RTree *)malloc(sizeof(struct RTree));
68
69 new_rtree->fd = fd;
70 new_rtree->rootpos = rootpos;
71 new_rtree->ndims = ndims;
72 new_rtree->nsides = 2 * ndims;
73 /* hack to keep compatibility */
74 if (ndims < 3)
75 new_rtree->ndims_alloc = 3;
76 else
77 new_rtree->ndims_alloc = ndims;
78
79 new_rtree->nsides_alloc = 2 * new_rtree->ndims_alloc;
80
81 /* init free node positions */
82 new_rtree->free_nodes.avail = 0;
83 new_rtree->free_nodes.alloc = 0;
84 new_rtree->free_nodes.pos = NULL;
85
86 new_rtree->rectsize = new_rtree->nsides_alloc * sizeof(RectReal);
87 new_rtree->branchsize = sizeof(struct RTree_Branch) -
88 sizeof(struct RTree_Rect) +
89 new_rtree->rectsize;
90 new_rtree->nodesize = sizeof(struct RTree_Node) -
91 sizeof(struct RTree_Branch *) +
92 MAXCARD * new_rtree->branchsize;
93
94 /* create empty root node */
95 n = RTreeAllocNode(new_rtree, 0);
96 new_rtree->rootlevel = n->level = 0; /* leaf */
97
98 /* use overflow by default */
99 new_rtree->overflow = 1;
100
101 if (fd > -1) { /* file based */
102 /* nodecard and leafcard can be adjusted, must NOT be larger than MAXCARD */
103 new_rtree->nodecard = MAXCARD;
104 new_rtree->leafcard = MAXCARD;
105
106 /* initialize node buffer */
107 new_rtree->nb = calloc(MAXLEVEL, sizeof(struct NodeBuffer *));
108 new_rtree->nb[0] = calloc(MAXLEVEL * NODE_BUFFER_SIZE, sizeof(struct NodeBuffer));
109 for (i = 1; i < MAXLEVEL; i++) {
110 new_rtree->nb[i] = new_rtree->nb[i - 1] + NODE_BUFFER_SIZE;
111 }
112
113 new_rtree->used = malloc(MAXLEVEL * sizeof(int *));
114 new_rtree->used[0] = malloc(MAXLEVEL * NODE_BUFFER_SIZE * sizeof(int));
115 for (i = 0; i < MAXLEVEL; i++) {
116 if (i)
117 new_rtree->used[i] = new_rtree->used[i - 1] + NODE_BUFFER_SIZE;
118 for (j = 0; j < NODE_BUFFER_SIZE; j++) {
119 new_rtree->nb[i][j].dirty = 0;
120 new_rtree->nb[i][j].pos = -1;
121 /* usage order */
122 new_rtree->used[i][j] = j;
123
124 new_rtree->nb[i][j].n.branch = malloc(MAXCARD * sizeof(struct RTree_Branch));
125
126 /* alloc memory for rectangles */
127 for (k = 0; k < MAXCARD; k++) {
128 new_rtree->nb[i][j].n.branch[k].rect.boundary = RTreeAllocBoundary(new_rtree);
129 }
130 }
131 }
132
133 /* write empty root node */
134 lseek(new_rtree->fd, rootpos, SEEK_SET);
135 RTreeWriteNode(n, new_rtree);
136 RTreeFreeNode(n);
137 new_rtree->root = NULL;
138
139 new_rtree->insert_rect = RTreeInsertRectF;
140 new_rtree->delete_rect = RTreeDeleteRectF;
141 new_rtree->search_rect = RTreeSearchF;
142 new_rtree->valid_child = RTreeValidChildF;
143 }
144 else { /* memory based */
145 new_rtree->nodecard = MAXCARD;
146 new_rtree->leafcard = MAXCARD;
147
148 new_rtree->insert_rect = RTreeInsertRectM;
149 new_rtree->delete_rect = RTreeDeleteRectM;
150 new_rtree->search_rect = RTreeSearchM;
151 new_rtree->valid_child = RTreeValidChildM;
152
153 new_rtree->root = n;
154 }
155
156 /* minimum number of remaining children for RTreeDeleteRect */
157 /* NOTE: min fill can be changed if needed, must be < nodecard and leafcard. */
158 new_rtree->min_node_fill = (new_rtree->nodecard - 2) / 2;
159 new_rtree->min_leaf_fill = (new_rtree->leafcard - 2) / 2;
160
161 /* balance criteria for node splitting */
162 new_rtree->minfill_node_split = (new_rtree->nodecard - 1) / 2;
163 new_rtree->minfill_leaf_split = (new_rtree->leafcard - 1) / 2;
164
165 new_rtree->n_nodes = 1;
166 new_rtree->n_leafs = 0;
167
168 /* initialize temp variables */
169 new_rtree->ns = malloc(MAXLEVEL * sizeof(struct nstack));
170
171 new_rtree->p.cover[0].boundary = RTreeAllocBoundary(new_rtree);
172 new_rtree->p.cover[1].boundary = RTreeAllocBoundary(new_rtree);
173
174 new_rtree->tmpb1.rect.boundary = RTreeAllocBoundary(new_rtree);
175 new_rtree->tmpb2.rect.boundary = RTreeAllocBoundary(new_rtree);
176 new_rtree->c.rect.boundary = RTreeAllocBoundary(new_rtree);
177
178 new_rtree->BranchBuf = malloc((MAXCARD + 1) * sizeof(struct RTree_Branch));
179 for (i = 0; i <= MAXCARD; i++) {
180 new_rtree->BranchBuf[i].rect.boundary = RTreeAllocBoundary(new_rtree);
181 }
182 new_rtree->rect_0.boundary = RTreeAllocBoundary(new_rtree);
183 new_rtree->rect_1.boundary = RTreeAllocBoundary(new_rtree);
184 new_rtree->upperrect.boundary = RTreeAllocBoundary(new_rtree);
185 new_rtree->orect.boundary = RTreeAllocBoundary(new_rtree);
186 new_rtree->center_n = (RectReal *)malloc(new_rtree->ndims_alloc * sizeof(RectReal));
187
188 return new_rtree;
189}
190
191/*!
192 \brief Enable/disable R*-tree forced reinsertion (overflow)
193
194 For dynamic R*-trees with runtime insertion and deletion,
195 forced reinsertion results in a more compact tree, searches are a bit
196 faster. For static R*-trees (no insertion/deletion after creation)
197 forced reinsertion can be disabled at the cost of slower searches.
198
199 \param t pointer to RTree structure
200 \param overflow binary flag
201
202 \return nothing
203*/
204void RTreeSetOverflow(struct RTree *t, char overflow)
205{
206 t->overflow = overflow != 0;
207}
208
209/*!
210 \brief Destroy an R*-Tree
211
212 This method releases all memory allocated to a RTree. It deletes all
213 rectangles and all memory allocated for internal support data.
214 Note that for a file-based RTree, the file is not deleted and not
215 closed. The file can thus be used to permanently store an RTree.
216
217 \param t pointer to RTree structure
218
219 \return nothing
220*/
221
223{
224 int i;
225
226 assert(t);
227
228 if (t->fd > -1) {
229 int j, k;
230
231 for (i = 0; i < MAXLEVEL; i++) {
232 for (j = 0; j < NODE_BUFFER_SIZE; j++) {
233 for (k = 0; k < MAXCARD; k++) {
234 RTreeFreeBoundary(&t->nb[i][j].n.branch[k].rect);
235 }
236 free(t->nb[i][j].n.branch);
237 }
238 }
239
240 if (t->free_nodes.alloc)
241 free(t->free_nodes.pos);
242 free(t->nb[0]);
243 free(t->nb);
244 free(t->used[0]);
245 free(t->used);
246 }
247 else if (t->root)
248 RTreeDestroyNode(t->root, t->root->level ? t->nodecard : t->leafcard);
249
250 /* free temp variables */
251 free(t->ns);
252
253 RTreeFreeBoundary(&(t->p.cover[0]));
254 RTreeFreeBoundary(&(t->p.cover[1]));
255
256 RTreeFreeBoundary(&(t->tmpb1.rect));
257 RTreeFreeBoundary(&(t->tmpb2.rect));
258 RTreeFreeBoundary(&(t->c.rect));
259 for (i = 0; i <= MAXCARD; i++) {
260 RTreeFreeBoundary(&(t->BranchBuf[i].rect));
261 }
262 free(t->BranchBuf);
263 RTreeFreeBoundary(&(t->rect_0));
264 RTreeFreeBoundary(&(t->rect_1));
265 RTreeFreeBoundary(&(t->upperrect));
266 RTreeFreeBoundary(&(t->orect));
267 free(t->center_n);
268
269 free(t);
270
271 return;
272}
273
274/*!
275 \brief Search an R*-Tree
276
277 Search in an RTree for all data retangles that overlap or touch the
278 argument rectangle.
279 Return the number of qualifying data rectangles.
280 The search stops if the SearchHitCallBack function returns 0 (zero)
281 or if there are no more qualifying data rectangles.
282
283 \param t pointer to RTree structure
284 \param r pointer to rectangle to use for searching
285 \param shcb Search Hit CallBack function
286 \param cbarg custom pointer used as argument for the shcb fn
287
288 \return number of qualifying data rectangles
289*/
290/*
291 *
292 * add option to select operator to select rectangles ?
293 * current: overlap
294 * possible alternatives:
295 * - select all rectangles that are fully contained in r
296 * - select all rectangles that fully contain r
297 */
298int RTreeSearch(struct RTree *t, struct RTree_Rect *r,
299 SearchHitCallback *shcb, void *cbarg)
300{
301 assert(r && t);
302
303 return t->search_rect(t, r, shcb, cbarg);
304}
305
306/*!
307 \brief Insert an item into a R*-Tree
308
309 \param r pointer to rectangle to use for searching
310 \param tid data id stored with rectangle, must be > 0
311 \param t pointer to RTree structure
312
313 \return number of qualifying data rectangles
314*/
315int RTreeInsertRect(struct RTree_Rect *r, int tid, struct RTree *t)
316{
317 union RTree_Child newchild;
318
319 assert(r && t && tid > 0);
320
321 t->n_leafs++;
322 newchild.id = tid;
323
324 return t->insert_rect(r, newchild, 0, t);
325}
326
327/*!
328 \brief Delete an item from a R*-Tree
329
330 This method deletes an item from the RTree. The rectangle passed to
331 this method does not need to be the exact rectangle, the only
332 requirement is that this rectangle overlaps with the rectangle to
333 be deleted. The rectangle to be deleted is identified by its id.
334
335 \param r pointer to rectangle to use for searching
336 \param tid id of the data to be deleted, must be > 0
337 \param t pointer to RTree structure
338
339 \return 0 on success
340 \return 1 if data item not found
341*/
342int RTreeDeleteRect(struct RTree_Rect *r, int tid, struct RTree *t)
343{
344 union RTree_Child child;
345
346 assert(r && t && tid > 0);
347
348 child.id = tid;
349
350 return t->delete_rect(r, child, t);
351}
352
353
354/***********************************
355 * internally used functions *
356 ***********************************/
357
358
359/*
360 * Allocate space for a node in the list used in DeleteRect to
361 * store Nodes that are too empty.
362 */
364{
365 return (struct RTree_ListNode *)malloc(sizeof(struct RTree_ListNode));
366}
367
369{
370 free(p);
371}
372
373/*
374 * Add a node to the reinsertion list. All its branches will later
375 * be reinserted into the index structure.
376 */
377void RTreeReInsertNode(struct RTree_Node *n, struct RTree_ListNode **ee)
378{
380
381 l->node = n;
382 l->next = *ee;
383 *ee = l;
384}
385
386/*
387 * Free ListBranch, used by R*-type forced reinsertion
388 */
390{
391 RTreeFreeBoundary(&(p->b.rect));
392 free(p);
393}
394
395
396
#define NULL
Definition: ccmath.h:32
int RTreeSearchM(struct RTree *, struct RTree_Rect *, SearchHitCallback *, void *)
Definition: indexm.c:34
int RTreeInsertRectF(struct RTree_Rect *, union RTree_Child, int, struct RTree *)
Definition: indexf.c:214
int RTreeDeleteRectM(struct RTree_Rect *, union RTree_Child, struct RTree *)
Definition: indexm.c:354
int RTreeSearchF(struct RTree *, struct RTree_Rect *, SearchHitCallback *, void *)
Definition: indexf.c:37
int RTreeInsertRectM(struct RTree_Rect *, union RTree_Child, int, struct RTree *)
Definition: indexm.c:186
int RTreeDeleteRectF(struct RTree_Rect *, union RTree_Child, struct RTree *)
Definition: indexf.c:408
int RTreeValidChildM(union RTree_Child *child)
Definition: indexm.c:24
int RTreeValidChildF(union RTree_Child *)
Definition: indexf.c:27
size_t RTreeWriteNode(struct RTree_Node *n, struct RTree *t)
Definition: io.c:169
#define assert(condition)
Definition: lz4.c:324
void RTreeFreeNode(struct RTree_Node *n)
Definition: node.c:98
void RTreeDestroyNode(struct RTree_Node *n, int nodes)
Definition: node.c:291
struct RTree_Node * RTreeAllocNode(struct RTree *t, int level)
Definition: node.c:77
double l
Definition: r_raster.c:39
double t
Definition: r_raster.c:39
double r
Definition: r_raster.c:39
void RTreeFreeBoundary(struct RTree_Rect *r)
Delete the boundary of a rectangle.
Definition: rect.c:101
RectReal * RTreeAllocBoundary(struct RTree *t)
Allocate the boundary array of a rectangle for a given tree.
Definition: rect.c:84
#define MAXCARD
Definition: rtree.h:46
int SearchHitCallback(int id, const struct RTree_Rect *rect, void *arg)
Definition: rtree.h:91
#define NODE_BUFFER_SIZE
Definition: rtree.h:55
double RectReal
Definition: rtree.h:28
struct RTree_Node n
Definition: rtree.h:113
char dirty
Definition: rtree.h:115
off_t pos
Definition: rtree.h:114
off_t * pos
Definition: rtree.h:158
struct RTree_Rect rect
Definition: rtree.h:73
struct RTree_Branch b
Definition: index.h:49
int level
Definition: rtree.h:80
struct RTree_Branch * branch
Definition: rtree.h:81
struct RTree_Rect cover[2]
Definition: rtree.h:124
RectReal * boundary
Definition: rtree.h:59
Definition: rtree.h:129
unsigned char ndims_alloc
Definition: rtree.h:134
unsigned char nsides
Definition: rtree.h:133
int branchsize
Definition: rtree.h:137
int min_leaf_fill
Definition: rtree.h:149
int minfill_node_split
Definition: rtree.h:150
int n_nodes
Definition: rtree.h:141
int rootlevel
Definition: rtree.h:143
off_t rootpos
Definition: rtree.h:192
RectReal * center_n
Definition: rtree.h:190
struct RTree::_recycle free_nodes
int n_leafs
Definition: rtree.h:142
struct RTree_Rect rect_0 rect_1 upperrect orect
Definition: rtree.h:189
int ** used
Definition: rtree.h:167
struct RTree_Branch tmpb1 tmpb2 c
Definition: rtree.h:186
int minfill_leaf_split
Definition: rtree.h:151
int min_node_fill
Definition: rtree.h:148
struct RTree_Branch * BranchBuf
Definition: rtree.h:184
rt_delete_fn * delete_rect
Definition: rtree.h:171
int nodesize
Definition: rtree.h:136
int fd
Definition: rtree.h:131
rt_search_fn * search_rect
Definition: rtree.h:172
unsigned char nsides_alloc
Definition: rtree.h:135
rt_valid_child_fn * valid_child
Definition: rtree.h:173
int leafcard
Definition: rtree.h:147
int rectsize
Definition: rtree.h:138
unsigned char ndims
Definition: rtree.h:132
rt_insert_fn * insert_rect
Definition: rtree.h:170
struct RTree_Node * root
Definition: rtree.h:175
int nodecard
Definition: rtree.h:146
char overflow
Definition: rtree.h:152
struct RTree_PartitionVars p
Definition: rtree.h:183
struct NodeBuffer ** nb
Definition: rtree.h:162
struct nstack * ns
Definition: rtree.h:180
Definition: rtree.h:104
int id
Definition: rtree.h:66
int RTreeDeleteRect(struct RTree_Rect *r, int tid, struct RTree *t)
Delete an item from a R*-Tree.
Definition: index.c:342
void RTreeSetOverflow(struct RTree *t, char overflow)
Enable/disable R*-tree forced reinsertion (overflow)
Definition: index.c:204
void RTreeFreeListNode(struct RTree_ListNode *p)
Definition: index.c:368
void RTreeReInsertNode(struct RTree_Node *n, struct RTree_ListNode **ee)
Definition: index.c:377
struct RTree * RTreeCreateTree(int fd, off_t rootpos, int ndims)
Create new empty R*-Tree.
Definition: index.c:61
struct RTree_ListNode * RTreeNewListNode(void)
Definition: index.c:363
int RTreeInsertRect(struct RTree_Rect *r, int tid, struct RTree *t)
Insert an item into a R*-Tree.
Definition: index.c:315
void RTreeDestroyTree(struct RTree *t)
Destroy an R*-Tree.
Definition: index.c:222
int RTreeSearch(struct RTree *t, struct RTree_Rect *r, SearchHitCallback *shcb, void *cbarg)
Search an R*-Tree.
Definition: index.c:298
void RTreeFreeListBranch(struct RTree_ListBranch *p)
Definition: index.c:389
#define MAXLEVEL
Maximum verbosity level.
Definition: verbose.c:30