GRASS Programmer's Manual  6.4.1(2011)
index.h
Go to the documentation of this file.
00001 
00002 /****************************************************************************
00003 * MODULE:       R-Tree library 
00004 *              
00005 * AUTHOR(S):    Antonin Guttman - original code
00006 *               Daniel Green (green@superliminal.com) - major clean-up
00007 *                               and implementation of bounding spheres
00008 *               
00009 * PURPOSE:      Multidimensional index
00010 *
00011 * COPYRIGHT:    (C) 2001 by the GRASS Development Team
00012 *
00013 *               This program is free software under the GNU General Public
00014 *               License (>=v2). Read the file COPYING that comes with GRASS
00015 *               for details.
00016 *****************************************************************************/
00017 #ifndef _INDEX_
00018 #define _INDEX_
00019 
00020 /* PGSIZE is normally the natural page size of the machine */
00021 #define PGSIZE  512
00022 #define NUMDIMS 3               /* number of dimensions */
00023 
00024 /* typedef float RectReal; */
00025 typedef double RectReal;
00026 
00027 /*-----------------------------------------------------------------------------
00028 | Global definitions.
00029 -----------------------------------------------------------------------------*/
00030 
00031 #ifndef TRUE
00032 #define TRUE 1
00033 #endif
00034 #ifndef FALSE
00035 #define FALSE 0
00036 #endif
00037 
00038 #define NUMSIDES 2*NUMDIMS
00039 
00040 struct Rect
00041 {
00042     RectReal boundary[NUMSIDES];        /* xmin,ymin,...,xmax,ymax,... */
00043 };
00044 
00045 struct Node;
00046 
00047 struct Branch
00048 {
00049     struct Rect rect;
00050     struct Node *child;
00051 };
00052 
00053 /* max branching factor of a node */
00054 #define MAXCARD (int)((PGSIZE-(2*sizeof(int))) / sizeof(struct Branch))
00055 
00056 struct Node
00057 {
00058     int count;
00059     int level;                  /* 0 is leaf, others positive */
00060     struct Branch branch[MAXCARD];
00061 };
00062 
00063 struct ListNode
00064 {
00065     struct ListNode *next;
00066     struct Node *node;
00067 };
00068 
00069 /*
00070  * If passed to a tree search, this callback function will be called
00071  * with the ID of each data rect that overlaps the search rect
00072  * plus whatever user specific pointer was passed to the search.
00073  * It can terminate the search early by returning 0 in which case
00074  * the search will return the number of hits found up to that point.
00075  */
00076 typedef int (*SearchHitCallback) (int id, void *arg);
00077 
00078 
00079 extern int RTreeSearch(struct Node *, struct Rect *, SearchHitCallback,
00080                        void *);
00081 extern int RTreeInsertRect(struct Rect *, int, struct Node **, int depth);
00082 extern int RTreeInsertRect1(struct Rect *, struct Node *, struct Node **, int depth);
00083 extern int RTreeDeleteRect(struct Rect *, int, struct Node **);
00084 extern int RTreeDeleteRect1(struct Rect *, struct Node *, struct Node **);
00085 extern struct Node *RTreeNewIndex(void);
00086 extern struct Node *RTreeNewNode(void);
00087 extern void RTreeInitNode(struct Node *);
00088 extern void RTreeFreeNode(struct Node *);
00089 extern void RTreeDestroyNode(struct Node *);
00090 extern void RTreePrintNode(struct Node *, int);
00091 extern void RTreeTabIn(int);
00092 extern struct Rect RTreeNodeCover(struct Node *);
00093 extern void RTreeInitRect(struct Rect *);
00094 extern struct Rect RTreeNullRect(void);
00095 extern RectReal RTreeRectArea(struct Rect *);
00096 extern RectReal RTreeRectSphericalVolume(struct Rect *R);
00097 extern RectReal RTreeRectVolume(struct Rect *R);
00098 extern struct Rect RTreeCombineRect(struct Rect *, struct Rect *);
00099 extern int RTreeOverlap(struct Rect *, struct Rect *);
00100 extern void RTreePrintRect(struct Rect *, int);
00101 extern int RTreeAddBranch(struct Branch *, struct Node *, struct Node **);
00102 extern int RTreePickBranch(struct Rect *, struct Node *);
00103 extern void RTreeDisconnectBranch(struct Node *, int);
00104 extern void RTreeSplitNode(struct Node *, struct Branch *, struct Node **);
00105 
00106 extern int RTreeSetNodeMax(int);
00107 extern int RTreeSetLeafMax(int);
00108 extern int RTreeGetNodeMax(void);
00109 extern int RTreeGetLeafMax(void);
00110 
00111 #endif /* _INDEX_ */
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Defines