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