5 #ifndef QUADTREE_REMOVED
14 typedef int QuadTreeIndex;
15 static const QuadTreeIndex QUADTREE_EMPTY = -1;
18 enum QuadTreeNodeChildren
27 // Represents a single node in a quadtree.
30 // Indices of children nodes, QUADTREE_EMPTY if no such child.
31 QuadTreeIndex top_left;
32 QuadTreeIndex top_right;
33 QuadTreeIndex bottom_left;
34 QuadTreeIndex bottom_right;
35 // Parent node id. QUADTREE_EMPTY if root.
38 QuadTreeNodeChildren child_type;
39 // First object in the node.
40 unsigned object_begin;
41 // Last object in the node.
43 // Linked list of "extra" nodes
44 QuadTreeIndex next_overlay;
45 // First object which has not yet been propagated to extant children/parent.
46 unsigned object_dirty;
51 QuadTree() : root_id(QUADTREE_EMPTY) {}
52 QuadTreeIndex root_id;
53 std::vector<QuadTreeNode> nodes;
55 QuadTreeIndex GetNeighbour(QuadTreeIndex start, int xdir, int ydir, Document *doc) const;
59 Rect TransformToQuadChild(const Rect& src, QuadTreeNodeChildren child_type);
60 Rect TransformFromQuadChild(const Rect& src, QuadTreeNodeChildren child_type);
61 bool IntersectsQuadChild(const Rect& src, QuadTreeNodeChildren child_type);
62 bool ContainedInQuadChild(const Rect& src, QuadTreeNodeChildren child_type);
66 #define QUADTREE_DISABLED