5 #ifndef QUADTREE_REMOVED
14 typedef int QuadTreeIndex;
15 static const QuadTreeIndex QUADTREE_EMPTY = -1;
17 enum QuadTreeNodeChildren
26 // Represents a single node in a quadtree.
29 // Indices of children nodes, QUADTREE_EMPTY if no such child.
30 QuadTreeIndex top_left;
31 QuadTreeIndex top_right;
32 QuadTreeIndex bottom_left;
33 QuadTreeIndex bottom_right;
34 // Parent node id. QUADTREE_EMPTY if root.
37 QuadTreeNodeChildren child_type;
38 // First object in the node.
39 unsigned object_begin;
40 // Last object in the node.
42 // Linked list of "extra" nodes
43 QuadTreeIndex next_overlay;
48 QuadTree() : root_id(QUADTREE_EMPTY) {}
49 QuadTreeIndex root_id;
50 std::vector<QuadTreeNode> nodes;
52 QuadTreeIndex GetNeighbour(QuadTreeIndex start, int xdir, int ydir) const;
56 Rect TransformToQuadChild(const Rect& src, QuadTreeNodeChildren child_type);
57 Rect TransformFromQuadChild(const Rect& src, QuadTreeNodeChildren child_type);
58 bool IntersectsQuadChild(const Rect& src, QuadTreeNodeChildren child_type);
59 bool ContainedInQuadChild(const Rect& src, QuadTreeNodeChildren child_type);
63 #define QUADTREE_DISABLED