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 */
29 * Calculates required statistical information for a node
31 void (*recalculate_stats)(struct quadtree *node);
34 static inline void init_quadtree(struct quadtree *t)
36 memset(t, 0, sizeof(*t));
39 #define QUADTREE_UPLEFT 0x1
40 #define QUADTREE_UPRIGHT 0x2
41 #define QUADTREE_DOWNLEFT 0x4
42 #define QUADTREE_DOWNRIGHT 0x8
43 #define QUADTREE_SELF 0x10
45 struct quadtree_iterator {
46 struct quadtree *head;
49 int (*direction)(struct quadtree *head, struct quadtree_iterator *it);
50 void (*callback)(struct quadtree *head, struct quadtree_iterator *it);
53 struct quadtree *quadtree_add(struct quadtree *parent, struct quadtree *new,
54 struct quadtree_ops *ops);
56 struct quadtree *quadtree_del(struct quadtree *node, struct quadtree_ops *ops);
57 struct quadtree *quadtree_move(struct quadtree *node, struct vector new_pos,
58 struct quadtree_ops *ops);
60 int walk_quadtree(const struct quadtree_iterator *iterator);
63 /* quadtree_find_parent - return the highest parent of the node */
64 static inline struct quadtree *quadtree_find_parent(const struct quadtree *node)
66 struct quadtree *t = (struct quadtree *)node;