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)  

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
28typedef 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
58{
59 RectReal *boundary; /* xmin,ymin,...,xmax,ymax,... */
60};
61
62struct 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
71struct RTree_Branch /* branch for spatial index */
72{
75};
76
77struct 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 */
91typedef int SearchHitCallback(int id, const struct RTree_Rect *rect, void *arg);
92
93struct RTree;
94
95typedef int rt_search_fn(struct RTree *, struct RTree_Rect *,
96 SearchHitCallback *, void *);
97typedef int rt_insert_fn(struct RTree_Rect *, union RTree_Child, int, struct RTree *);
98typedef int rt_delete_fn(struct RTree_Rect *, union RTree_Child, struct RTree *);
99typedef int rt_valid_child_fn(union RTree_Child *);
100
101/* temp vars for each tree */
102/* node stack used for non-recursive insertion/deletion */
103struct 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 */
122 int taken[MAXCARD + 1];
123 int count[2];
124 struct RTree_Rect cover[2];
126};
127
128struct 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 */
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 */
196int RTreeSearch(struct RTree *, struct RTree_Rect *,
197 SearchHitCallback *, void *);
198int RTreeInsertRect(struct RTree_Rect *, int, struct RTree *);
199void RTreeSetRect1D(struct RTree_Rect *r, struct RTree *t, double x_min,
200 double x_max);
201void RTreeSetRect2D(struct RTree_Rect *r, struct RTree *t, double x_min,
202 double x_max, double y_min, double y_max);
203void 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);
206void 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);
209int RTreeDeleteRect(struct RTree_Rect *, int, struct RTree *);
210void RTreePrintRect(struct RTree_Rect *, int, struct RTree *);
211struct RTree *RTreeCreateTree(int, off_t, int);
212void RTreeSetOverflow(struct RTree *, char);
213void RTreeDestroyTree(struct RTree *);
214int RTreeOverlap(struct RTree_Rect *, struct RTree_Rect *, struct RTree *);
215int RTreeContained(struct RTree_Rect *, struct RTree_Rect *, struct RTree *);
216int RTreeContains(struct RTree_Rect *, struct RTree_Rect *, struct RTree *);
217
218/* RTree node management */
219struct RTree_Node *RTreeAllocNode(struct RTree *, int);
220void RTreeInitNode(struct RTree *, struct RTree_Node *, int);
221void RTreeCopyNode(struct RTree_Node *, struct RTree_Node *, struct RTree *);
222void RTreeFreeNode(struct RTree_Node *);
223void RTreeDestroyNode(struct RTree_Node *, int);
224
225/* RTree rectangle allocation and deletion */
226struct RTree_Rect *RTreeAllocRect(struct RTree *t);
227void RTreeFreeRect(struct RTree_Rect *r);
229void RTreeFreeBoundary(struct RTree_Rect *r);
230
231/* RTree IO */
232size_t RTreeReadNode(struct RTree_Node *, off_t, struct RTree *);
233size_t RTreeWriteNode(struct RTree_Node *, struct RTree *);
234off_t RTreeGetNodePos(struct RTree *);
235void RTreeFlushBuffer(struct RTree *);
236
237#endif
double t
Definition: r_raster.c:39
double r
Definition: r_raster.c:39
void RTreeFreeNode(struct RTree_Node *)
Definition: node.c:98
struct RTree_Rect * RTreeAllocRect(struct RTree *t)
Create a new rectangle for a given tree.
Definition: rect.c:45
#define MAXCARD
Definition: rtree.h:46
void RTreeFreeRect(struct RTree_Rect *r)
Delete a rectangle.
Definition: rect.c:66
size_t RTreeWriteNode(struct RTree_Node *, struct RTree *)
Definition: io.c:169
void RTreeDestroyNode(struct RTree_Node *, int)
Definition: node.c:291
struct RTree * RTreeCreateTree(int, off_t, int)
Create new empty R*-Tree.
Definition: index.c:61
int RTreeContains(struct RTree_Rect *, struct RTree_Rect *, struct RTree *)
Definition: rect.c:644
int SearchHitCallback(int id, const struct RTree_Rect *rect, void *arg)
Definition: rtree.h:91
void RTreeInitNode(struct RTree *, struct RTree_Node *, int)
Definition: node.c:65
int rt_delete_fn(struct RTree_Rect *, union RTree_Child, struct RTree *)
Definition: rtree.h:98
int RTreeDeleteRect(struct RTree_Rect *, int, struct RTree *)
Delete an item from a R*-Tree.
Definition: index.c:342
void RTreeFlushBuffer(struct RTree *)
Definition: io.c:230
int rt_insert_fn(struct RTree_Rect *, union RTree_Child, int, struct RTree *)
Definition: rtree.h:97
int RTreeContained(struct RTree_Rect *, struct RTree_Rect *, struct RTree *)
Definition: rect.c:617
int RTreeSearch(struct RTree *, struct RTree_Rect *, SearchHitCallback *, void *)
Search an R*-Tree.
Definition: index.c:298
int rt_search_fn(struct RTree *, struct RTree_Rect *, SearchHitCallback *, void *)
Definition: rtree.h:95
size_t RTreeReadNode(struct RTree_Node *, off_t, struct RTree *)
Definition: io.c:95
void RTreeFreeBoundary(struct RTree_Rect *r)
Delete the boundary of a rectangle.
Definition: rect.c:101
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:131
int RTreeOverlap(struct RTree_Rect *, struct RTree_Rect *, struct RTree *)
Definition: rect.c:597
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:152
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:207
RectReal * RTreeAllocBoundary(struct RTree *t)
Allocate the boundary array of a rectangle for a given tree.
Definition: rect.c:84
int rt_valid_child_fn(union RTree_Child *)
Definition: rtree.h:99
int RTreeInsertRect(struct RTree_Rect *, int, struct RTree *)
Insert an item into a R*-Tree.
Definition: index.c:315
off_t RTreeGetNodePos(struct RTree *)
Definition: io.c:72
void RTreePrintRect(struct RTree_Rect *, int, struct RTree *)
Definition: rect.c:307
void RTreeDestroyTree(struct RTree *)
Destroy an R*-Tree.
Definition: index.c:222
double RectReal
Definition: rtree.h:28
void RTreeSetOverflow(struct RTree *, char)
Enable/disable R*-tree forced reinsertion (overflow)
Definition: index.c:204
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:177
struct RTree_Node * RTreeAllocNode(struct RTree *, int)
Definition: node.c:77
void RTreeCopyNode(struct RTree_Node *, struct RTree_Node *, struct RTree *)
Definition: node.c:112
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
union RTree_Child child
Definition: rtree.h:74
int count
Definition: rtree.h:79
int level
Definition: rtree.h:80
struct RTree_Branch * branch
Definition: rtree.h:81
int taken[9+1]
Definition: rtree.h:122
RectReal area[2]
Definition: rtree.h:125
struct RTree_Rect cover[2]
Definition: rtree.h:124
int partition[9+1]
Definition: rtree.h:120
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 BranchCount
Definition: rtree.h:187
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
off_t pos
Definition: rtree.h:107
struct RTree_Node * sn
Definition: rtree.h:105
int branch_id
Definition: rtree.h:106
off_t pos
Definition: rtree.h:68
struct RTree_Node * ptr
Definition: rtree.h:67
int id
Definition: rtree.h:66