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
  17         enum QuadTreeNodeChildren
  18         {
  19                 QTC_UNKNOWN,
  20                 QTC_TOP_LEFT,
  21                 QTC_TOP_RIGHT,
  22                 QTC_BOTTOM_LEFT,
  23                 QTC_BOTTOM_RIGHT
  24         };
  25
  26         // Represents a single node in a quadtree.
  27         struct QuadTreeNode
  28         {
  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.
  35                 QuadTreeIndex parent;
  36                 // Which child am I?
  37                 QuadTreeNodeChildren child_type;
  38                 // First object in the node.
  39                 unsigned object_begin;
  40                 // Last object in the node.
  41                 unsigned object_end;
  42                 // Linked list of "extra" nodes
  43                 QuadTreeIndex next_overlay;
  44         };
  45
  46         struct QuadTree
  47         {
  48                 QuadTree() : root_id(QUADTREE_EMPTY) {}
  49                 QuadTreeIndex root_id;
  50                 std::vector<QuadTreeNode> nodes;
  51
  52                 QuadTreeIndex GetNeighbour(QuadTreeIndex start, int xdir, int ydir) const;
  53
  54         };
  55
  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);
  60 }
  61
  62 #else
  63 #define QUADTREE_DISABLED
  64 #endif
  65
  66 #endif