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