index.h

Go to the documentation of this file.
00001 /****************************************************************************
00002 * MODULE:       R-Tree library 
00003 *              
00004 * AUTHOR(S):    Antonin Guttman - original code
00005 *               Daniel Green (green@superliminal.com) - major clean-up
00006 *                               and implementation of bounding spheres
00007 *               
00008 * PURPOSE:      Multidimensional index
00009 *
00010 * COPYRIGHT:    (C) 2001 by the GRASS Development Team
00011 *
00012 *               This program is free software under the GNU General Public
00013 *               License (>=v2). Read the file COPYING that comes with GRASS
00014 *               for details.
00015 *****************************************************************************/
00016 #ifndef _INDEX_
00017 #define _INDEX_
00018 
00019 /* PGSIZE is normally the natural page size of the machine */
00020 #define PGSIZE  512
00021 #define NUMDIMS 3       /* number of dimensions */
00022 #define NDEBUG
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, void*);
00080 extern int RTreeInsertRect(struct Rect*, int, struct Node**, int depth);
00081 extern int RTreeDeleteRect(struct Rect*, int, struct Node**);
00082 extern struct Node * RTreeNewIndex(void);
00083 extern struct Node * RTreeNewNode(void);
00084 extern void RTreeInitNode(struct Node*);
00085 extern void RTreeFreeNode(struct Node *);
00086 extern void RTreeDestroyNode(struct Node *);
00087 extern void RTreePrintNode(struct Node *, int);
00088 extern void RTreeTabIn(int);
00089 extern struct Rect RTreeNodeCover(struct Node *);
00090 extern void RTreeInitRect(struct Rect*);
00091 extern struct Rect RTreeNullRect(void);
00092 extern RectReal RTreeRectArea(struct Rect*);
00093 extern RectReal RTreeRectSphericalVolume(struct Rect *R);
00094 extern RectReal RTreeRectVolume(struct Rect *R);
00095 extern struct Rect RTreeCombineRect(struct Rect*, struct Rect*);
00096 extern int RTreeOverlap(struct Rect*, struct Rect*);
00097 extern void RTreePrintRect(struct Rect*, int);
00098 extern int RTreeAddBranch(struct Branch *, struct Node *, struct Node **);
00099 extern int RTreePickBranch(struct Rect *, struct Node *);
00100 extern void RTreeDisconnectBranch(struct Node *, int);
00101 extern void RTreeSplitNode(struct Node*, struct Branch*, struct Node**);
00102 
00103 extern int RTreeSetNodeMax(int);
00104 extern int RTreeSetLeafMax(int);
00105 extern int RTreeGetNodeMax(void);
00106 extern int RTreeGetLeafMax(void);
00107 
00108 #endif /* _INDEX_ */

Generated on Sun Apr 6 17:32:44 2008 for GRASS by  doxygen 1.5.5