GRASS Programmer's Manual  6.4.3(2013)-r
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Macros Pages
index.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 *
9 * PURPOSE: Multidimensional index
10 *
11 * COPYRIGHT: (C) 2001 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 _INDEX_
18 #define _INDEX_
19 
20 /* PGSIZE is normally the natural page size of the machine */
21 #define PGSIZE 512
22 #define NUMDIMS 3 /* number of dimensions */
23 
24 /* typedef float RectReal; */
25 typedef double RectReal;
26 
27 /*-----------------------------------------------------------------------------
28 | Global definitions.
29 -----------------------------------------------------------------------------*/
30 
31 #ifndef TRUE
32 #define TRUE 1
33 #endif
34 #ifndef FALSE
35 #define FALSE 0
36 #endif
37 
38 #define NUMSIDES 2*NUMDIMS
39 
40 struct Rect
41 {
42  RectReal boundary[NUMSIDES]; /* xmin,ymin,...,xmax,ymax,... */
43 };
44 
45 struct Node;
46 
47 struct Branch
48 {
49  struct Rect rect;
50  struct Node *child;
51 };
52 
53 /* max branching factor of a node */
54 #define MAXCARD (int)((PGSIZE-(2*sizeof(int))) / sizeof(struct Branch))
55 
56 struct Node
57 {
58  int count;
59  int level; /* 0 is leaf, others positive */
61 };
62 
63 struct ListNode
64 {
65  struct ListNode *next;
66  struct Node *node;
67 };
68 
69 /*
70  * If passed to a tree search, this callback function will be called
71  * with the ID of each data rect that overlaps the search rect
72  * plus whatever user specific pointer was passed to the search.
73  * It can terminate the search early by returning 0 in which case
74  * the search will return the number of hits found up to that point.
75  */
76 typedef int (*SearchHitCallback) (int id, void *arg);
77 
78 
79 extern int RTreeSearch(struct Node *, struct Rect *, SearchHitCallback,
80  void *);
81 extern int RTreeInsertRect(struct Rect *, int, struct Node **, int depth);
82 extern int RTreeInsertRect1(struct Rect *, struct Node *, struct Node **, int depth);
83 extern int RTreeDeleteRect(struct Rect *, int, struct Node **);
84 extern int RTreeDeleteRect1(struct Rect *, struct Node *, struct Node **);
85 extern struct Node *RTreeNewIndex(void);
86 extern struct Node *RTreeNewNode(void);
87 extern void RTreeInitNode(struct Node *);
88 extern void RTreeFreeNode(struct Node *);
89 extern void RTreeDestroyNode(struct Node *);
90 extern void RTreePrintNode(struct Node *, int);
91 extern void RTreeTabIn(int);
92 extern struct Rect RTreeNodeCover(struct Node *);
93 extern void RTreeInitRect(struct Rect *);
94 extern struct Rect RTreeNullRect(void);
95 extern RectReal RTreeRectArea(struct Rect *);
96 extern RectReal RTreeRectSphericalVolume(struct Rect *R);
97 extern RectReal RTreeRectVolume(struct Rect *R);
98 extern struct Rect RTreeCombineRect(struct Rect *, struct Rect *);
99 extern int RTreeOverlap(struct Rect *, struct Rect *);
100 extern void RTreePrintRect(struct Rect *, int);
101 extern int RTreeAddBranch(struct Branch *, struct Node *, struct Node **);
102 extern int RTreePickBranch(struct Rect *, struct Node *);
103 extern void RTreeDisconnectBranch(struct Node *, int);
104 extern void RTreeSplitNode(struct Node *, struct Branch *, struct Node **);
105 
106 extern int RTreeSetNodeMax(int);
107 extern int RTreeSetLeafMax(int);
108 extern int RTreeGetNodeMax(void);
109 extern int RTreeGetLeafMax(void);
110 
111 #endif /* _INDEX_ */