GRASS GIS 8 Programmer's Manual  8.2.2dev(2023)-3d2c704037
vector/rtree/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 */
61 struct 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 */
204 void 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 
222 void RTreeDestroyTree(struct RTree *t)
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  */
298 int 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 */
315 int 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 */
342 int 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  */
377 void RTreeReInsertNode(struct RTree_Node *n, struct RTree_ListNode **ee)
378 {
379  struct RTree_ListNode *l = RTreeNewListNode();
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 
struct RTree_Rect rect_0 rect_1 upperrect orect
Definition: rtree.h:189
int RTreeInsertRect(struct RTree_Rect *r, int tid, struct RTree *t)
Insert an item into a R*-Tree.
double RectReal
Definition: rtree.h:28
struct RTree_Node * root
Definition: rtree.h:175
struct RTree_Node * node
Definition: index.h:37
int RTreeDeleteRectM(struct RTree_Rect *, union RTree_Child, struct RTree *)
Definition: indexm.c:354
void RTreeFreeNode(struct RTree_Node *n)
Definition: node.c:98
int level
Definition: rtree.h:80
int SearchHitCallback(int id, const struct RTree_Rect *rect, void *arg)
Definition: rtree.h:91
struct RTree::_recycle free_nodes
struct NodeBuffer ** nb
Definition: rtree.h:162
void RTreeDestroyTree(struct RTree *t)
Destroy an R*-Tree.
rt_search_fn * search_rect
Definition: rtree.h:172
#define NODE_BUFFER_SIZE
Definition: rtree.h:55
#define MAXLEVEL
Maximum verbosity level.
Definition: verbose.c:30
rt_delete_fn * delete_rect
Definition: rtree.h:171
int RTreeSearch(struct RTree *t, struct RTree_Rect *r, SearchHitCallback *shcb, void *cbarg)
Search an R*-Tree.
struct RTree_ListNode * RTreeNewListNode(void)
off_t * pos
Definition: rtree.h:158
int branchsize
Definition: rtree.h:137
int RTreeValidChildM(union RTree_Child *child)
Definition: indexm.c:24
struct RTree_ListNode * next
Definition: index.h:36
void free(void *)
#define NULL
Definition: ccmath.h:32
int nodecard
Definition: rtree.h:146
unsigned char ndims
Definition: rtree.h:132
int RTreeDeleteRect(struct RTree_Rect *r, int tid, struct RTree *t)
Delete an item from a R*-Tree.
void * malloc(YYSIZE_T)
void RTreeDestroyNode(struct RTree_Node *n, int nodes)
Definition: node.c:291
unsigned char ndims_alloc
Definition: rtree.h:134
double l
Definition: r_raster.c:39
double t
Definition: r_raster.c:39
unsigned char nsides
Definition: rtree.h:133
Definition: rtree.h:103
int RTreeDeleteRectF(struct RTree_Rect *, union RTree_Child, struct RTree *)
Definition: indexf.c:408
#define assert(condition)
Definition: lz4.c:324
int RTreeSearchF(struct RTree *, struct RTree_Rect *, SearchHitCallback *, void *)
Definition: indexf.c:37
void RTreeFreeListNode(struct RTree_ListNode *p)
void RTreeFreeBoundary(struct RTree_Rect *r)
Delete the boundary of a rectangle.
Definition: rect.c:100
struct RTree_Branch tmpb1 tmpb2 c
Definition: rtree.h:186
struct RTree_Branch * BranchBuf
Definition: rtree.h:184
struct RTree_Branch * branch
Definition: rtree.h:81
off_t rootpos
Definition: rtree.h:192
void RTreeSetOverflow(struct RTree *t, char overflow)
Enable/disable R*-tree forced reinsertion (overflow)
void RTreeFreeListBranch(struct RTree_ListBranch *p)
struct RTree_Node * RTreeAllocNode(struct RTree *t, int level)
Definition: node.c:77
char overflow
Definition: rtree.h:152
int rectsize
Definition: rtree.h:138
unsigned char nsides_alloc
Definition: rtree.h:135
int RTreeInsertRectF(struct RTree_Rect *, union RTree_Child, int, struct RTree *)
Definition: indexf.c:214
int RTreeInsertRectM(struct RTree_Rect *, union RTree_Child, int, struct RTree *)
Definition: indexm.c:186
struct nstack * ns
Definition: rtree.h:180
RectReal * RTreeAllocBoundary(struct RTree *t)
Allocate the boundary array of a rectangle for a given tree.
Definition: rect.c:83
int fd
Definition: rtree.h:131
int ** used
Definition: rtree.h:167
struct RTree_Branch b
Definition: index.h:49
RectReal * center_n
Definition: rtree.h:190
RectReal * boundary
Definition: rtree.h:59
#define MAXCARD
Definition: rtree.h:46
struct RTree_Node n
Definition: rtree.h:113
int RTreeValidChildF(union RTree_Child *)
Definition: indexf.c:27
rt_insert_fn * insert_rect
Definition: rtree.h:170
int id
Definition: rtree.h:66
size_t RTreeWriteNode(struct RTree_Node *n, struct RTree *t)
Definition: io.c:169
void RTreeReInsertNode(struct RTree_Node *n, struct RTree_ListNode **ee)
int RTreeSearchM(struct RTree *, struct RTree_Rect *, SearchHitCallback *, void *)
Definition: indexm.c:34
struct RTree_Rect rect
Definition: rtree.h:73
Definition: rtree.h:128
struct RTree_Rect cover[2]
Definition: rtree.h:124
int n_leafs
Definition: rtree.h:142
double r
Definition: r_raster.c:39
struct RTree * RTreeCreateTree(int fd, off_t rootpos, int ndims)
Create new empty R*-Tree.
int leafcard
Definition: rtree.h:147
struct RTree_PartitionVars p
Definition: rtree.h:183