13 * Each node divide the sub-tree in following quadtrants:
15 * up left (0) | up right (1)
16 * -----------------------------
17 * down left (2) | down right (3)
19 struct quadtree *child[4];
20 struct quadtree *parent;
23 long int children; /* The total number of children */
24 long int depth; /* The deepest subtree branch */
27 * Corner points that indicate the space that is covered by
28 * the tree. Upper left and lower right points are stored.
30 struct vector corner[2];
35 * Calculates required statistical information for a node
37 void (*recalculate_stats)(struct quadtree *node);
40 static inline void init_quadtree(struct quadtree *t)
42 memset(t, 0, sizeof(*t));
45 #define QUADTREE_UPLEFT 0x1
46 #define QUADTREE_UPRIGHT 0x2
47 #define QUADTREE_DOWNLEFT 0x4
48 #define QUADTREE_DOWNRIGHT 0x8
49 #define QUADTREE_SELF 0x10
51 struct quadtree_iterator {
52 struct quadtree *head;
55 int (*direction)(struct quadtree *head, struct quadtree_iterator *it);
56 void (*callback)(struct quadtree *head, struct quadtree_iterator *it);
59 struct quadtree *quadtree_add(struct quadtree *parent, struct quadtree *new,
60 struct quadtree_ops *ops);
62 struct quadtree *quadtree_del(struct quadtree *node, struct quadtree_ops *ops);
63 struct quadtree *quadtree_move(struct quadtree *node, struct vector new_pos,
64 struct quadtree_ops *ops);
66 int walk_quadtree(const struct quadtree_iterator *iterator);
69 /* quadtree_find_parent - return the highest parent of the node */
70 static inline struct quadtree *quadtree_find_parent(const struct quadtree *node)
72 struct quadtree *t = (struct quadtree *)node;