src/quadtree.h

   1 #ifndef _QUADTREE_H
   2 #define _QUADTREE_H
   3
   4
   5 #ifndef QUADTREE_REMOVED
   6
   7
   8 #include "common.h"
   9
  10 namespace IPDF
  11 {
  12
  13         typedef int QuadTreeIndex;
  14         static const QuadTreeIndex QUADTREE_EMPTY = -1;
  15
  16         enum QuadTreeNodeChildren
  17         {
  18                 QTC_UNKNOWN,
  19                 QTC_TOP_LEFT,
  20                 QTC_TOP_RIGHT,
  21                 QTC_BOTTOM_LEFT,
  22                 QTC_BOTTOM_RIGHT
  23         };
  24
  25         // Represents a single node in a quadtree.
  26         struct QuadTreeNode
  27         {
  28                 // Indices of children nodes, QUADTREE_EMPTY if no such child.
  29                 QuadTreeIndex top_left;
  30                 QuadTreeIndex top_right;
  31                 QuadTreeIndex bottom_left;
  32                 QuadTreeIndex bottom_right;
  33                 // Parent node id. QUADTREE_EMPTY if root.
  34                 QuadTreeIndex parent;
  35                 // Which child am I?
  36                 QuadTreeNodeChildren child_type;
  37                 // First object in the node.
  38                 unsigned object_begin;
  39                 // Last object in the node.
  40                 unsigned object_end;
  41         };
  42
  43         struct QuadTree
  44         {
  45                 QuadTree() : root_id(QUADTREE_EMPTY) {}
  46                 QuadTreeIndex root_id;
  47                 std::vector<QuadTreeNode> nodes;
  48         };
  49 }
  50
  51 #else
  52 #define QUADTREE_DISABLED
  53 #endif
  54
  55 #endif