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         };
  46
  47         struct QuadTree
  48         {
  49                 QuadTree() : root_id(QUADTREE_EMPTY) {}
  50                 QuadTreeIndex root_id;
  51                 std::vector<QuadTreeNode> nodes;
  52
  53                 QuadTreeIndex GetNeighbour(QuadTreeIndex start, int xdir, int ydir, Document *doc) const;
  54
  55         };
  56
  57         Rect TransformToQuadChild(const Rect& src, QuadTreeNodeChildren child_type);
  58         Rect TransformFromQuadChild(const Rect& src, QuadTreeNodeChildren child_type);
  59         bool IntersectsQuadChild(const Rect& src, QuadTreeNodeChildren child_type);
  60         bool ContainedInQuadChild(const Rect& src, QuadTreeNodeChildren child_type);
  61 }
  62
  63 #else
  64 #define QUADTREE_DISABLED
  65 #endif
  66
  67 #endif