src/quadtree.h

   1 #ifndef _QUADTREE_H
   2 #define _QUADTREE_H
   3
   4
   5 #ifndef QUADTREE_REMOVED
   6
   7
   8 #include "common.h"
   9 #include "ipdf.h"
  10
  11 namespace IPDF
  12 {
  13
  14         typedef int QuadTreeIndex;
  15         static const QuadTreeIndex QUADTREE_EMPTY = -1;
  16         class Document;
  17
  18         enum QuadTreeNodeChildren
  19         {
  20                 QTC_UNKNOWN,
  21                 QTC_TOP_LEFT,
  22                 QTC_TOP_RIGHT,
  23                 QTC_BOTTOM_LEFT,
  24                 QTC_BOTTOM_RIGHT
  25         };
  26
  27         // Represents a single node in a quadtree.
  28         struct QuadTreeNode
  29         {
  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.
  36                 QuadTreeIndex parent;
  37                 // Which child am I?
  38                 QuadTreeNodeChildren child_type;
  39                 // First object in the node.
  40                 unsigned object_begin;
  41                 // Last object in the node.
  42                 unsigned object_end;
  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;
  47                 bool render_dirty;
  48         };
  49
  50         struct QuadTree
  51         {
  52                 QuadTree() : root_id(QUADTREE_EMPTY) {}
  53                 QuadTreeIndex root_id;
  54                 std::vector<QuadTreeNode> nodes;
  55
  56                 QuadTreeIndex GetNeighbour(QuadTreeIndex start, int xdir, int ydir, Document *doc) const;
  57                 void GetCanonicalCoords(QuadTreeIndex& start, Real& x, Real& y, Document *doc);
  58
  59         };
  60
  61         Rect TransformToQuadChild(const Rect& src, QuadTreeNodeChildren child_type);
  62         Rect TransformFromQuadChild(const Rect& src, QuadTreeNodeChildren child_type);
  63         bool IntersectsQuadChild(const Rect& src, QuadTreeNodeChildren child_type);
  64         bool ContainedInQuadChild(const Rect& src, QuadTreeNodeChildren child_type);
  65 }
  66
  67 #else
  68 #define QUADTREE_DISABLED
  69 #endif
  70
  71 #endif