00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016 #ifndef _INDEX_
00017 #define _INDEX_
00018
00019
00020 #define PGSIZE 512
00021 #define NUMDIMS 3
00022 #define NDEBUG
00023
00024
00025 typedef double RectReal;
00026
00027
00028
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];
00043 };
00044
00045 struct Node;
00046
00047 struct Branch
00048 {
00049 struct Rect rect;
00050 struct Node *child;
00051 };
00052
00053
00054 #define MAXCARD (int)((PGSIZE-(2*sizeof(int))) / sizeof(struct Branch))
00055
00056 struct Node
00057 {
00058 int count;
00059 int level;
00060 struct Branch branch[MAXCARD];
00061 };
00062
00063 struct ListNode
00064 {
00065 struct ListNode *next;
00066 struct Node *node;
00067 };
00068
00069
00070
00071
00072
00073
00074
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