GRASS GIS 8 Programmer's Manual  8.4.0dev(2024)-535c39c9fc
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) + new_rtree->rectsize;
89  new_rtree->nodesize = sizeof(struct RTree_Node) -
90  sizeof(struct RTree_Branch *) +
91  MAXCARD * new_rtree->branchsize;
92 
93  /* create empty root node */
94  n = RTreeAllocNode(new_rtree, 0);
95  new_rtree->rootlevel = n->level = 0; /* leaf */
96 
97  /* use overflow by default */
98  new_rtree->overflow = 1;
99 
100  if (fd > -1) { /* file based */
101  /* nodecard and leafcard can be adjusted, must NOT be larger than
102  * 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] =
109  calloc(MAXLEVEL * NODE_BUFFER_SIZE, sizeof(struct NodeBuffer));
110  for (i = 1; i < MAXLEVEL; i++) {
111  new_rtree->nb[i] = new_rtree->nb[i - 1] + NODE_BUFFER_SIZE;
112  }
113 
114  new_rtree->used = malloc(MAXLEVEL * sizeof(int *));
115  new_rtree->used[0] = malloc(MAXLEVEL * NODE_BUFFER_SIZE * sizeof(int));
116  for (i = 0; i < MAXLEVEL; i++) {
117  if (i)
118  new_rtree->used[i] = new_rtree->used[i - 1] + NODE_BUFFER_SIZE;
119  for (j = 0; j < NODE_BUFFER_SIZE; j++) {
120  new_rtree->nb[i][j].dirty = 0;
121  new_rtree->nb[i][j].pos = -1;
122  /* usage order */
123  new_rtree->used[i][j] = j;
124 
125  new_rtree->nb[i][j].n.branch =
126  malloc(MAXCARD * sizeof(struct RTree_Branch));
127 
128  /* alloc memory for rectangles */
129  for (k = 0; k < MAXCARD; k++) {
130  new_rtree->nb[i][j].n.branch[k].rect.boundary =
131  RTreeAllocBoundary(new_rtree);
132  }
133  }
134  }
135 
136  /* write empty root node */
137  lseek(new_rtree->fd, rootpos, SEEK_SET);
138  RTreeWriteNode(n, new_rtree);
139  RTreeFreeNode(n);
140  new_rtree->root = NULL;
141 
142  new_rtree->insert_rect = RTreeInsertRectF;
143  new_rtree->delete_rect = RTreeDeleteRectF;
144  new_rtree->search_rect = RTreeSearchF;
145  new_rtree->valid_child = RTreeValidChildF;
146  }
147  else { /* memory based */
148  new_rtree->nodecard = MAXCARD;
149  new_rtree->leafcard = MAXCARD;
150 
151  new_rtree->insert_rect = RTreeInsertRectM;
152  new_rtree->delete_rect = RTreeDeleteRectM;
153  new_rtree->search_rect = RTreeSearchM;
154  new_rtree->valid_child = RTreeValidChildM;
155 
156  new_rtree->root = n;
157  }
158 
159  /* minimum number of remaining children for RTreeDeleteRect */
160  /* NOTE: min fill can be changed if needed, must be < nodecard and leafcard.
161  */
162  new_rtree->min_node_fill = (new_rtree->nodecard - 2) / 2;
163  new_rtree->min_leaf_fill = (new_rtree->leafcard - 2) / 2;
164 
165  /* balance criteria for node splitting */
166  new_rtree->minfill_node_split = (new_rtree->nodecard - 1) / 2;
167  new_rtree->minfill_leaf_split = (new_rtree->leafcard - 1) / 2;
168 
169  new_rtree->n_nodes = 1;
170  new_rtree->n_leafs = 0;
171 
172  /* initialize temp variables */
173  new_rtree->ns = malloc(MAXLEVEL * sizeof(struct nstack));
174 
175  new_rtree->p.cover[0].boundary = RTreeAllocBoundary(new_rtree);
176  new_rtree->p.cover[1].boundary = RTreeAllocBoundary(new_rtree);
177 
178  new_rtree->tmpb1.rect.boundary = RTreeAllocBoundary(new_rtree);
179  new_rtree->tmpb2.rect.boundary = RTreeAllocBoundary(new_rtree);
180  new_rtree->c.rect.boundary = RTreeAllocBoundary(new_rtree);
181 
182  new_rtree->BranchBuf = malloc((MAXCARD + 1) * sizeof(struct RTree_Branch));
183  for (i = 0; i <= MAXCARD; i++) {
184  new_rtree->BranchBuf[i].rect.boundary = RTreeAllocBoundary(new_rtree);
185  }
186  new_rtree->rect_0.boundary = RTreeAllocBoundary(new_rtree);
187  new_rtree->rect_1.boundary = RTreeAllocBoundary(new_rtree);
188  new_rtree->upperrect.boundary = RTreeAllocBoundary(new_rtree);
189  new_rtree->orect.boundary = RTreeAllocBoundary(new_rtree);
190  new_rtree->center_n =
191  (RectReal *)malloc(new_rtree->ndims_alloc * sizeof(RectReal));
192 
193  return new_rtree;
194 }
195 
196 /*!
197  \brief Enable/disable R*-tree forced reinsertion (overflow)
198 
199  For dynamic R*-trees with runtime insertion and deletion,
200  forced reinsertion results in a more compact tree, searches are a bit
201  faster. For static R*-trees (no insertion/deletion after creation)
202  forced reinsertion can be disabled at the cost of slower searches.
203 
204  \param t pointer to RTree structure
205  \param overflow binary flag
206 
207  \return nothing
208  */
209 void RTreeSetOverflow(struct RTree *t, char overflow)
210 {
211  t->overflow = overflow != 0;
212 }
213 
214 /*!
215  \brief Destroy an R*-Tree
216 
217  This method releases all memory allocated to a RTree. It deletes all
218  rectangles and all memory allocated for internal support data.
219  Note that for a file-based RTree, the file is not deleted and not
220  closed. The file can thus be used to permanently store an RTree.
221 
222  \param t pointer to RTree structure
223 
224  \return nothing
225  */
226 
227 void RTreeDestroyTree(struct RTree *t)
228 {
229  int i;
230 
231  assert(t);
232 
233  if (t->fd > -1) {
234  int j, k;
235 
236  for (i = 0; i < MAXLEVEL; i++) {
237  for (j = 0; j < NODE_BUFFER_SIZE; j++) {
238  for (k = 0; k < MAXCARD; k++) {
239  RTreeFreeBoundary(&t->nb[i][j].n.branch[k].rect);
240  }
241  free(t->nb[i][j].n.branch);
242  }
243  }
244 
245  if (t->free_nodes.alloc)
246  free(t->free_nodes.pos);
247  free(t->nb[0]);
248  free(t->nb);
249  free(t->used[0]);
250  free(t->used);
251  }
252  else if (t->root)
253  RTreeDestroyNode(t->root, t->root->level ? t->nodecard : t->leafcard);
254 
255  /* free temp variables */
256  free(t->ns);
257 
258  RTreeFreeBoundary(&(t->p.cover[0]));
259  RTreeFreeBoundary(&(t->p.cover[1]));
260 
261  RTreeFreeBoundary(&(t->tmpb1.rect));
262  RTreeFreeBoundary(&(t->tmpb2.rect));
263  RTreeFreeBoundary(&(t->c.rect));
264  for (i = 0; i <= MAXCARD; i++) {
265  RTreeFreeBoundary(&(t->BranchBuf[i].rect));
266  }
267  free(t->BranchBuf);
268  RTreeFreeBoundary(&(t->rect_0));
269  RTreeFreeBoundary(&(t->rect_1));
270  RTreeFreeBoundary(&(t->upperrect));
271  RTreeFreeBoundary(&(t->orect));
272  free(t->center_n);
273 
274  free(t);
275 
276  return;
277 }
278 
279 /*!
280  \brief Search an R*-Tree
281 
282  Search in an RTree for all data rectangles that overlap or touch the
283  argument rectangle.
284  Return the number of qualifying data rectangles.
285  The search stops if the SearchHitCallBack function returns 0 (zero)
286  or if there are no more qualifying data rectangles.
287 
288  \param t pointer to RTree structure
289  \param r pointer to rectangle to use for searching
290  \param shcb Search Hit CallBack function
291  \param cbarg custom pointer used as argument for the shcb fn
292 
293  \return number of qualifying data rectangles
294  */
295 /*
296  *
297  * add option to select operator to select rectangles ?
298  * current: overlap
299  * possible alternatives:
300  * - select all rectangles that are fully contained in r
301  * - select all rectangles that fully contain r
302  */
303 int RTreeSearch(struct RTree *t, struct RTree_Rect *r, SearchHitCallback *shcb,
304  void *cbarg)
305 {
306  assert(r && t);
307 
308  return t->search_rect(t, r, shcb, cbarg);
309 }
310 
311 /*!
312  \brief Insert an item into a R*-Tree
313 
314  \param r pointer to rectangle to use for searching
315  \param tid data id stored with rectangle, must be > 0
316  \param t pointer to RTree structure
317 
318  \return number of qualifying data rectangles
319  */
320 int RTreeInsertRect(struct RTree_Rect *r, int tid, struct RTree *t)
321 {
322  union RTree_Child newchild;
323 
324  assert(r && t && tid > 0);
325 
326  t->n_leafs++;
327  newchild.id = tid;
328 
329  return t->insert_rect(r, newchild, 0, t);
330 }
331 
332 /*!
333  \brief Delete an item from a R*-Tree
334 
335  This method deletes an item from the RTree. The rectangle passed to
336  this method does not need to be the exact rectangle, the only
337  requirement is that this rectangle overlaps with the rectangle to
338  be deleted. The rectangle to be deleted is identified by its id.
339 
340  \param r pointer to rectangle to use for searching
341  \param tid id of the data to be deleted, must be > 0
342  \param t pointer to RTree structure
343 
344  \return 0 on success
345  \return 1 if data item not found
346  */
347 int RTreeDeleteRect(struct RTree_Rect *r, int tid, struct RTree *t)
348 {
349  union RTree_Child child;
350 
351  assert(r && t && tid > 0);
352 
353  child.id = tid;
354 
355  return t->delete_rect(r, child, t);
356 }
357 
358 /***********************************
359  * internally used functions *
360  ***********************************/
361 
362 /*
363  * Allocate space for a node in the list used in DeleteRect to
364  * store Nodes that are too empty.
365  */
367 {
368  return (struct RTree_ListNode *)malloc(sizeof(struct RTree_ListNode));
369 }
370 
372 {
373  free(p);
374 }
375 
376 /*
377  * Add a node to the reinsertion list. All its branches will later
378  * be reinserted into the index structure.
379  */
380 void RTreeReInsertNode(struct RTree_Node *n, struct RTree_ListNode **ee)
381 {
382  struct RTree_ListNode *l = RTreeNewListNode();
383 
384  l->node = n;
385  l->next = *ee;
386  *ee = l;
387 }
388 
389 /*
390  * Free ListBranch, used by R*-type forced reinsertion
391  */
393 {
394  RTreeFreeBoundary(&(p->b.rect));
395  free(p);
396 }
#define NULL
Definition: ccmath.h:32
int RTreeSearchM(struct RTree *, struct RTree_Rect *, SearchHitCallback *, void *)
Definition: indexm.c:33
int RTreeInsertRectF(struct RTree_Rect *, union RTree_Child, int, struct RTree *)
Definition: indexf.c:213
int RTreeDeleteRectM(struct RTree_Rect *, union RTree_Child, struct RTree *)
Definition: indexm.c:352
int RTreeSearchF(struct RTree *, struct RTree_Rect *, SearchHitCallback *, void *)
Definition: indexf.c:36
int RTreeInsertRectM(struct RTree_Rect *, union RTree_Child, int, struct RTree *)
Definition: indexm.c:185
int RTreeDeleteRectF(struct RTree_Rect *, union RTree_Child, struct RTree *)
Definition: indexf.c:408
int RTreeValidChildM(union RTree_Child *child)
Definition: indexm.c:23
int RTreeValidChildF(union RTree_Child *)
Definition: indexf.c:26
size_t RTreeWriteNode(struct RTree_Node *n, struct RTree *t)
Definition: io.c:170
#define assert(condition)
Definition: lz4.c:393
void RTreeFreeNode(struct RTree_Node *n)
Definition: node.c:95
struct RTree_Node * RTreeAllocNode(struct RTree *t, int level)
Definition: node.c:74
void RTreeDestroyNode(struct RTree_Node *n, int nodes)
Definition: node.c:291
double l
Definition: r_raster.c:39
double t
Definition: r_raster.c:39
double r
Definition: r_raster.c:39
RectReal * RTreeAllocBoundary(struct RTree *t)
Allocate the boundary array of a rectangle for a given tree.
Definition: rect.c:81
void RTreeFreeBoundary(struct RTree_Rect *r)
Delete the boundary of a rectangle.
Definition: rect.c:98
#define MAXCARD
Definition: rtree.h:44
int SearchHitCallback(int id, const struct RTree_Rect *rect, void *arg)
Definition: rtree.h:86
#define NODE_BUFFER_SIZE
Definition: rtree.h:52
double RectReal
Definition: rtree.h:26
void * malloc(YYSIZE_T)
void free(void *)
struct RTree_Node n
Definition: rtree.h:108
char dirty
Definition: rtree.h:110
off_t pos
Definition: rtree.h:109
off_t * pos
Definition: rtree.h:153
struct RTree_Rect rect
Definition: rtree.h:68
struct RTree_Branch b
Definition: index.h:45
int level
Definition: rtree.h:75
struct RTree_Branch * branch
Definition: rtree.h:76
struct RTree_Rect cover[2]
Definition: rtree.h:119
RectReal * boundary
Definition: rtree.h:55
Definition: rtree.h:123
unsigned char ndims_alloc
Definition: rtree.h:128
unsigned char nsides
Definition: rtree.h:127
int branchsize
Definition: rtree.h:132
int min_leaf_fill
Definition: rtree.h:144
int minfill_node_split
Definition: rtree.h:145
int n_nodes
Definition: rtree.h:136
int rootlevel
Definition: rtree.h:138
off_t rootpos
Definition: rtree.h:187
RectReal * center_n
Definition: rtree.h:185
struct RTree::_recycle free_nodes
int n_leafs
Definition: rtree.h:137
struct RTree_Rect rect_0 rect_1 upperrect orect
Definition: rtree.h:184
int ** used
Definition: rtree.h:162
struct RTree_Branch tmpb1 tmpb2 c
Definition: rtree.h:181
int minfill_leaf_split
Definition: rtree.h:146
int min_node_fill
Definition: rtree.h:143
struct RTree_Branch * BranchBuf
Definition: rtree.h:179
rt_delete_fn * delete_rect
Definition: rtree.h:166
int nodesize
Definition: rtree.h:131
int fd
Definition: rtree.h:125
rt_search_fn * search_rect
Definition: rtree.h:167
unsigned char nsides_alloc
Definition: rtree.h:130
rt_valid_child_fn * valid_child
Definition: rtree.h:168
int leafcard
Definition: rtree.h:142
int rectsize
Definition: rtree.h:133
unsigned char ndims
Definition: rtree.h:126
rt_insert_fn * insert_rect
Definition: rtree.h:165
struct RTree_Node * root
Definition: rtree.h:170
int nodecard
Definition: rtree.h:141
char overflow
Definition: rtree.h:147
struct RTree_PartitionVars p
Definition: rtree.h:178
struct NodeBuffer ** nb
Definition: rtree.h:157
struct nstack * ns
Definition: rtree.h:175
Definition: rtree.h:100
int id
Definition: rtree.h:61
struct RTree_ListNode * RTreeNewListNode(void)
int RTreeDeleteRect(struct RTree_Rect *r, int tid, struct RTree *t)
Delete an item from a R*-Tree.
void RTreeSetOverflow(struct RTree *t, char overflow)
Enable/disable R*-tree forced reinsertion (overflow)
void RTreeFreeListNode(struct RTree_ListNode *p)
void RTreeReInsertNode(struct RTree_Node *n, struct RTree_ListNode **ee)
int RTreeInsertRect(struct RTree_Rect *r, int tid, struct RTree *t)
Insert an item into a R*-Tree.
void RTreeDestroyTree(struct RTree *t)
Destroy an R*-Tree.
int RTreeSearch(struct RTree *t, struct RTree_Rect *r, SearchHitCallback *shcb, void *cbarg)
Search an R*-Tree.
struct RTree * RTreeCreateTree(int fd, off_t rootpos, int ndims)
Create new empty R*-Tree.
void RTreeFreeListBranch(struct RTree_ListBranch *p)
#define MAXLEVEL
Maximum verbosity level.
Definition: verbose.c:30