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         };
  43
  44         struct QuadTree
  45         {
  46                 QuadTree() : root_id(QUADTREE_EMPTY) {}
  47                 QuadTreeIndex root_id;
  48                 std::vector<QuadTreeNode> nodes;
  49         };
  50
  51         Rect TransformToQuadChild(const Rect& src, QuadTreeNodeChildren child_type);
  52         Rect TransformFromQuadChild(const Rect& src, QuadTreeNodeChildren child_type);
  53         bool IntersectsQuadChild(const Rect& src, QuadTreeNodeChildren child_type);
  54         bool ContainedInQuadChild(const Rect& src, QuadTreeNodeChildren child_type);
  55 }
  56
  57 #else
  58 #define QUADTREE_DISABLED
  59 #endif
  60
  61 #endif