1 /************************************************************************/
2 /*									*/
3 /*  Quad Tree implementation.						*/
4 /*									*/
5 /*  Some kind of balancing is achieved by dividing a rectangle in	*/
6 /*  quadrants. No attempt is made to balance the tree when the entries	*/
7 /*  are not evenly spaced.						*/
8 /*									*/
9 /************************************************************************/
10 
11 #   ifndef	GEO_QUAD_TREE_H
12 #   define	GEO_QUAD_TREE_H
13 
14 #   include	"geo2DInteger.h"
15 
16 typedef enum Quadrant
17     {
18     QTquadNE,
19     QTquadNW,
20     QTquadSW,
21     QTquadSE,
22 
23     QTquad_COUNT
24     } Quadrant;
25 
26 typedef enum Octant
27     {
28     QToctENE,
29     QToctNNE,
30     QToctNNW,
31     QToctWNW,
32     QToctWSW,
33     QToctSSW,
34     QToctSSE,
35     QToctESE,
36 
37     QToct_COUNT
38     } Octant;
39 
40 typedef struct QuadNode
41     {
42     int			qnX;
43     int			qnY;
44 
45     struct QuadNode *	qn_parent;
46     struct QuadNode *	qnChildren[QTquad_COUNT];
47 
48     short int		qnBusy;
49     int			qnValueCount;
50     void **		qnValues;
51     } QuadNode;
52 
53 typedef struct QuadTree
54     {
55     DocumentRectangle	qtRectangle;
56     int			qtDiameter;
57     QuadNode *		qtRootNode;
58     } QuadTree;
59 
60 typedef int (*QuadForAllFilter)( const DocumentRectangle *	dr,
61 				void *				through );
62 
63 typedef int (*QuadForAllCall)(	int *				pDelete,
64 				int				x,
65 				int				y,
66 				void *				data,
67 				void *				through );
68 
69 /************************************************************************/
70 /*									*/
71 /*  Routine declarations.						*/
72 /*									*/
73 /************************************************************************/
74 
75 extern QuadTree * qtMakeTree(	const DocumentRectangle *	dr );
76 
77 extern void qtFreeTree(		QuadTree *	qt,
78 				QuadForAllCall	freefun,
79 				void *		through );
80 
81 extern int qtFreeData(		int		x,
82 				int		y,
83 				void *		data,
84 				void *		through );
85 
86 extern int qtPut(		QuadTree *	qt,
87 				int		x,
88 				int		y,
89 				void *		data );
90 
91 extern int qtGetExact(		QuadTree *	qt,
92 				int		x,
93 				int		y,
94 				void *** const	pvals,
95 				int *		pnval );
96 
97 extern int qtGetNearest(	QuadTree *	qt,
98 				int		x,
99 				int		y,
100 				const void *	data,
101 				int *		pX,
102 				int *		pY,
103 				void * const **	pvals,
104 				int *		pnval );
105 
106 extern const char * qtQuadrantStr(	int q );
107 extern const char * qtOctantStr(	int q );
108 
109 extern int qtForAllInRectangle(	const QuadTree *		qt,
110 				const DocumentRectangle *	dr,
111 				QuadForAllCall			fun,
112 				void *				through );
113 
114 extern int qtForAll(		const QuadTree *		qt,
115 				QuadForAllFilter		filter,
116 				QuadForAllCall			fun,
117 				void *				through );
118 
119 #   endif		/* GEO_QUAD_TREE_H */
120