GRASS GIS 8 Programmer's Manual  8.4.0dev(2024)-7413740dd8
rtree.h
Go to the documentation of this file.
1 /****************************************************************************
2  * MODULE: R-Tree library
3  *
4  * AUTHOR(S): Antonin Guttman - original code
5  * Daniel Green (green@superliminal.com) - major clean-up
6  * and implementation of bounding spheres
7  * Markus Metz - file-based and memory-based R*-tree
8  *
9  * PURPOSE: Multidimensional index
10  *
11  * COPYRIGHT: (C) 2010-2012 by the GRASS Development Team
12  *
13  * This program is free software under the GNU General Public
14  * License (>=v2). Read the file COPYING that comes with GRASS
15  * for details.
16  *****************************************************************************/
17 #ifndef _R_TREE_H_
18 #define _R_TREE_H_
19 
20 #include <stdlib.h>
21 #include <stdio.h>
22 #include <string.h>
23 #include <sys/types.h>
24 #include <grass/config.h> /* needed for LFS */
25 
26 typedef double RectReal;
27 
28 /*-----------------------------------------------------------------------------
29 | Global definitions.
30 -----------------------------------------------------------------------------*/
31 
32 #ifndef TRUE
33 #define TRUE 1
34 #endif
35 #ifndef FALSE
36 #define FALSE 0
37 #endif
38 
39 /* max branching factor of a node */
40 /* was (PGSIZE-(2 * sizeof(int))) / sizeof(struct Branch)
41  * this is LFS dependent, not good
42  * on 32 bit without LFS this is 9.69
43  * on 32 bit with LFS and on 64 bit this is 9 */
44 #define MAXCARD 9
45 #define NODECARD MAXCARD
46 #define LEAFCARD MAXCARD
47 
48 /* maximum no of levels = tree depth */
49 #define MAXLEVEL 20 /* 8^MAXLEVEL items are guaranteed to fit into the tree */
50 
51 /* number of nodes buffered per level */
52 #define NODE_BUFFER_SIZE 32
53 
54 struct RTree_Rect {
55  RectReal *boundary; /* xmin,ymin,...,xmax,ymax,... */
56 };
57 
58 struct RTree_Node; /* node for spatial index */
59 
60 union RTree_Child {
61  int id; /* child id */
62  struct RTree_Node *ptr; /* pointer to child node */
63  off_t pos; /* position of child node in file */
64 };
65 
66 struct RTree_Branch /* branch for spatial index */
67 {
68  struct RTree_Rect rect;
69  union RTree_Child child;
70 };
71 
72 struct RTree_Node /* node for spatial index */
73 {
74  int count; /* number of branches */
75  int level; /* 0 is leaf, others positive */
77 };
78 
79 /*
80  * If passed to a tree search, this callback function will be called
81  * with the ID of each data rect that overlaps the search rect
82  * plus whatever user specific pointer was passed to the search.
83  * It can terminate the search early by returning 0 in which case
84  * the search will return the number of hits found up to that point.
85  */
86 typedef int SearchHitCallback(int id, const struct RTree_Rect *rect, void *arg);
87 
88 struct RTree;
89 
90 typedef int rt_search_fn(struct RTree *, struct RTree_Rect *,
91  SearchHitCallback *, void *);
92 typedef int rt_insert_fn(struct RTree_Rect *, union RTree_Child, int,
93  struct RTree *);
94 typedef int rt_delete_fn(struct RTree_Rect *, union RTree_Child,
95  struct RTree *);
96 typedef int rt_valid_child_fn(union RTree_Child *);
97 
98 /* temp vars for each tree */
99 /* node stack used for non-recursive insertion/deletion */
100 struct nstack {
101  struct RTree_Node *sn; /* stack node */
102  int branch_id; /* branch number to follow down */
103  off_t pos; /* file position of stack node */
104 };
105 
106 /* node buffer for file-based index */
107 struct NodeBuffer {
108  struct RTree_Node n; /* buffered node */
109  off_t pos; /* file position of buffered node */
110  char dirty; /* node in buffer was modified */
111 };
112 
113 /* temp vars for node splitting */
115  int partition[MAXCARD + 1];
117  int taken[MAXCARD + 1];
118  int count[2];
119  struct RTree_Rect cover[2];
121 };
122 
123 struct RTree {
124  /* RTree setup info */
125  int fd; /* file descriptor */
126  unsigned char ndims; /* number of dimensions */
127  unsigned char nsides; /* number of sides = 2 * ndims */
128  unsigned char ndims_alloc; /* number of dimensions allocated */
129  unsigned char
130  nsides_alloc; /* number of sides allocated = 2 * ndims allocated */
131  int nodesize; /* node size in bytes */
132  int branchsize; /* branch size in bytes */
133  int rectsize; /* rectangle size in bytes */
134 
135  /* RTree info, useful to calculate space requirements */
136  int n_nodes; /* number of nodes */
137  int n_leafs; /* number of data items (level 0 leafs) */
138  int rootlevel; /* root level = tree depth */
139 
140  /* settings for RTree building */
141  int nodecard; /* max number of children in node */
142  int leafcard; /* max number of children in leaf */
143  int min_node_fill; /* balance criteria for node removal */
144  int min_leaf_fill; /* balance criteria for leaf removal */
145  int minfill_node_split; /* balance criteria for splitting */
146  int minfill_leaf_split; /* balance criteria for splitting */
147  char overflow; /* enable/disable overflow */
148 
149  /* free node positions for recycling */
150  struct _recycle {
151  int avail; /* number of available positions */
152  int alloc; /* number of allocated positions in *pos */
153  off_t *pos; /* array of available positions */
155 
156  /* node buffer for file-based index */
157  struct NodeBuffer **nb;
158 
159  /* usage order of buffered nodes per level
160  * used[level][0] = most recently used
161  * used[level][NODE_BUFFER_SIZE - 1] = least recently used */
162  int **used;
163 
164  /* insert, delete, search */
169 
170  struct RTree_Node *root; /* pointer to root node */
171 
172  /* internal variables, specific for each tree,
173  * allocated with tree initialization */
174  /* node stack for tree traversal */
175  struct nstack *ns;
176 
177  /* variables for splitting / forced reinsertion */
178  struct RTree_PartitionVars p;
180 
181  struct RTree_Branch tmpb1, tmpb2, c;
183 
184  struct RTree_Rect rect_0, rect_1, upperrect, orect;
186 
187  off_t rootpos; /* root node position in file */
188 };
189 
190 /* RTree main functions */
191 int RTreeSearch(struct RTree *, struct RTree_Rect *, SearchHitCallback *,
192  void *);
193 int RTreeInsertRect(struct RTree_Rect *, int, struct RTree *);
194 void RTreeSetRect1D(struct RTree_Rect *r, struct RTree *t, double x_min,
195  double x_max);
196 void RTreeSetRect2D(struct RTree_Rect *r, struct RTree *t, double x_min,
197  double x_max, double y_min, double y_max);
198 void RTreeSetRect3D(struct RTree_Rect *r, struct RTree *t, double x_min,
199  double x_max, double y_min, double y_max, double z_min,
200  double z_max);
201 void RTreeSetRect4D(struct RTree_Rect *r, struct RTree *t, double x_min,
202  double x_max, double y_min, double y_max, double z_min,
203  double z_max, double t_min, double t_max);
204 int RTreeDeleteRect(struct RTree_Rect *, int, struct RTree *);
205 void RTreePrintRect(struct RTree_Rect *, int, struct RTree *);
206 struct RTree *RTreeCreateTree(int, off_t, int);
207 void RTreeSetOverflow(struct RTree *, char);
208 void RTreeDestroyTree(struct RTree *);
209 int RTreeOverlap(struct RTree_Rect *, struct RTree_Rect *, struct RTree *);
210 int RTreeContained(struct RTree_Rect *, struct RTree_Rect *, struct RTree *);
211 int RTreeContains(struct RTree_Rect *, struct RTree_Rect *, struct RTree *);
212 
213 /* RTree node management */
214 struct RTree_Node *RTreeAllocNode(struct RTree *, int);
215 void RTreeInitNode(struct RTree *, struct RTree_Node *, int);
216 void RTreeCopyNode(struct RTree_Node *, struct RTree_Node *, struct RTree *);
217 void RTreeFreeNode(struct RTree_Node *);
218 void RTreeDestroyNode(struct RTree_Node *, int);
219 
220 /* RTree rectangle allocation and deletion */
221 struct RTree_Rect *RTreeAllocRect(struct RTree *t);
222 void RTreeFreeRect(struct RTree_Rect *r);
224 void RTreeFreeBoundary(struct RTree_Rect *r);
225 
226 /* RTree IO */
227 size_t RTreeReadNode(struct RTree_Node *, off_t, struct RTree *);
228 size_t RTreeWriteNode(struct RTree_Node *, struct RTree *);
229 off_t RTreeGetNodePos(struct RTree *);
230 void RTreeFlushBuffer(struct RTree *);
231 
232 #endif
double t
Definition: r_raster.c:39
double r
Definition: r_raster.c:39
void RTreeFreeNode(struct RTree_Node *)
Definition: node.c:95
RectReal * RTreeAllocBoundary(struct RTree *t)
Allocate the boundary array of a rectangle for a given tree.
Definition: rect.c:81
#define MAXCARD
Definition: rtree.h:44
void RTreeFreeRect(struct RTree_Rect *r)
Delete a rectangle.
Definition: rect.c:63
size_t RTreeWriteNode(struct RTree_Node *, struct RTree *)
Definition: io.c:170
void RTreeDestroyNode(struct RTree_Node *, int)
Definition: node.c:291
int RTreeContains(struct RTree_Rect *, struct RTree_Rect *, struct RTree *)
Definition: rect.c:634
int SearchHitCallback(int id, const struct RTree_Rect *rect, void *arg)
Definition: rtree.h:86
void RTreeInitNode(struct RTree *, struct RTree_Node *, int)
Definition: node.c:62
struct RTree_Node * RTreeAllocNode(struct RTree *, int)
Definition: node.c:74
int rt_delete_fn(struct RTree_Rect *, union RTree_Child, struct RTree *)
Definition: rtree.h:94
int RTreeDeleteRect(struct RTree_Rect *, int, struct RTree *)
Delete an item from a R*-Tree.
void RTreeFlushBuffer(struct RTree *)
Definition: io.c:233
int rt_insert_fn(struct RTree_Rect *, union RTree_Child, int, struct RTree *)
Definition: rtree.h:92
int RTreeContained(struct RTree_Rect *, struct RTree_Rect *, struct RTree *)
Definition: rect.c:609
int RTreeSearch(struct RTree *, struct RTree_Rect *, SearchHitCallback *, void *)
Search an R*-Tree.
struct RTree * RTreeCreateTree(int, off_t, int)
Create new empty R*-Tree.
struct RTree_Rect * RTreeAllocRect(struct RTree *t)
Create a new rectangle for a given tree.
Definition: rect.c:42
int rt_search_fn(struct RTree *, struct RTree_Rect *, SearchHitCallback *, void *)
Definition: rtree.h:90
size_t RTreeReadNode(struct RTree_Node *, off_t, struct RTree *)
Definition: io.c:94
void RTreeFreeBoundary(struct RTree_Rect *r)
Delete the boundary of a rectangle.
Definition: rect.c:98
void RTreeSetRect1D(struct RTree_Rect *r, struct RTree *t, double x_min, double x_max)
Set one dimensional coordinates of a rectangle for a given tree.
Definition: rect.c:128
int RTreeOverlap(struct RTree_Rect *, struct RTree_Rect *, struct RTree *)
Definition: rect.c:590
void RTreeSetRect2D(struct RTree_Rect *r, struct RTree *t, double x_min, double x_max, double y_min, double y_max)
Set two dimensional coordinates of a rectangle for a given tree.
Definition: rect.c:149
void RTreeSetRect4D(struct RTree_Rect *r, struct RTree *t, double x_min, double x_max, double y_min, double y_max, double z_min, double z_max, double t_min, double t_max)
Set 4 dimensional coordinates of a rectangle for a given tree.
Definition: rect.c:204
int rt_valid_child_fn(union RTree_Child *)
Definition: rtree.h:96
int RTreeInsertRect(struct RTree_Rect *, int, struct RTree *)
Insert an item into a R*-Tree.
off_t RTreeGetNodePos(struct RTree *)
Definition: io.c:71
void RTreePrintRect(struct RTree_Rect *, int, struct RTree *)
Definition: rect.c:304
void RTreeDestroyTree(struct RTree *)
Destroy an R*-Tree.
double RectReal
Definition: rtree.h:26
void RTreeSetOverflow(struct RTree *, char)
Enable/disable R*-tree forced reinsertion (overflow)
void RTreeSetRect3D(struct RTree_Rect *r, struct RTree *t, double x_min, double x_max, double y_min, double y_max, double z_min, double z_max)
Set three dimensional coordinates of a rectangle for a given tree.
Definition: rect.c:174
void RTreeCopyNode(struct RTree_Node *, struct RTree_Node *, struct RTree *)
Definition: node.c:109
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
union RTree_Child child
Definition: rtree.h:69
int count
Definition: rtree.h:74
int level
Definition: rtree.h:75
struct RTree_Branch * branch
Definition: rtree.h:76
int partition[MAXCARD+1]
Definition: rtree.h:115
RectReal area[2]
Definition: rtree.h:120
struct RTree_Rect cover[2]
Definition: rtree.h:119
int taken[MAXCARD+1]
Definition: rtree.h:117
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 BranchCount
Definition: rtree.h:182
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
off_t pos
Definition: rtree.h:103
struct RTree_Node * sn
Definition: rtree.h:101
int branch_id
Definition: rtree.h:102
off_t pos
Definition: rtree.h:63
struct RTree_Node * ptr
Definition: rtree.h:62
int id
Definition: rtree.h:61