GRASS Programmer's Manual
6.4.2(2012)
|
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_ */