src/quadtree.cpp

   1 #ifndef QUADTREE_REMOVED
   2 #include "quadtree.h"
   3
   4 namespace IPDF {
   5
   6 Rect TransformToQuadChild(const Rect& src, QuadTreeNodeChildren child_type)
   7 {
   8         Rect dst = src;
   9         dst.x *= 2;
  10         dst.y *= 2;
  11         dst.w *= 2;
  12         dst.h *= 2;
  13         if (child_type == QTC_BOTTOM_LEFT || child_type == QTC_BOTTOM_RIGHT)
  14         {
  15                 dst.y -= 1;
  16         }
  17         if (child_type == QTC_TOP_RIGHT || child_type == QTC_BOTTOM_RIGHT)
  18         {
  19                 dst.x -= 1;
  20         }
  21         return dst;
  22 }
  23
  24 Rect TransformFromQuadChild(const Rect& src, QuadTreeNodeChildren child_type)
  25 {
  26         Rect dst = src;
  27         if (child_type == QTC_BOTTOM_LEFT || child_type == QTC_BOTTOM_RIGHT)
  28         {
  29                 dst.y += 1;
  30         }
  31         if (child_type == QTC_TOP_RIGHT || child_type == QTC_BOTTOM_RIGHT)
  32         {
  33                 dst.x += 1;
  34         }
  35         dst.x *= 0.5;
  36         dst.y *= 0.5;
  37         dst.w *= 0.5;
  38         dst.h *= 0.5;
  39         return dst;
  40 }
  41
  42 bool IntersectsQuadChild(const Rect& src, QuadTreeNodeChildren child_type)
  43 {
  44         Rect std = {0,0,1,1};
  45         Rect dst = TransformFromQuadChild(std, child_type);
  46         if (src.x + src.w < dst.x) return false;
  47         if (src.y + src.h < dst.y) return false;
  48         if (src.x > dst.x + dst.w) return false;
  49         if (src.y > dst.y + dst.h) return false;
  50         Debug("%s is contained in %s\n", src.Str().c_str(), dst.Str().c_str());
  51         return true;
  52 }
  53
  54 bool ContainedInQuadChild(const Rect& src, QuadTreeNodeChildren child_type)
  55 {
  56         Rect std = {0,0,1,1};
  57         Rect dst = TransformFromQuadChild(std, child_type);
  58         if (src.x < dst.x) return false;
  59         if (src.y < dst.y) return false;
  60         if (src.x + src.w > dst.x + dst.w) return false;
  61         if (src.y + src.h > dst.y + dst.h) return false;
  62         Debug("%s is contained in %s... \n", src.Str().c_str(), dst.Str().c_str());
  63         return true;
  64 }
  65
  66
  67
  68 QuadTreeIndex QuadTree::GetNeighbour(QuadTreeIndex start, int xdir, int ydir)
  69 {
  70         if (!xdir && !ydir) return start;
  71
  72         // Try moving to the right if that's easy.
  73         if (xdir > 0)
  74         {
  75                 switch (nodes[start].child_type)
  76                 {
  77                 case QTC_TOP_LEFT:
  78                 case QTC_BOTTOM_LEFT:
  79                         QuadTreeIndex newNode;
  80                         if (nodes[start].child_type == QTC_TOP_LEFT)
  81                                 newNode = node[nodes[start].parent].top_right;
  82                         else
  83                                 newNode = node[nodes[start].parent].bottom_right;
  84
  85                         return GetNeighbour(newNode, xdir - 1, ydir);
  86                 case QTC_TOP_RIGHT:
  87                 case QTC_BOTTOM_RIGHT:
  88                         QuadTreeIndex right_parent = GetNeighbour(nodes[start].parent, 1, 0);
  89                         if (right_parent == -1) return -1;
  90                         QuadTreeIndex newNode;
  91                         if (nodes[start].child_type == QTC_TOP_RIGHT)
  92                                 newNode = node[right_parent].top_left;
  93                         else
  94                                 newNode = node[right_parent].bottom_left;
  95                         return GetNeighbour(newNode, xdir - 1, ydir);
  96
  97                 }
  98         }
  99
 100         // Try moving to the left.
 101         if (xdir < 0)
 102         {
 103                 switch (nodes[start].child_type)
 104                 {
 105                 case QTC_TOP_RIGHT:
 106                 case QTC_BOTTOM_RIGHT:
 107                         QuadTreeIndex newNode;
 108                         if (nodes[start].child_type == QTC_TOP_RIGHT)
 109                                 newNode = node[nodes[start].parent].top_left;
 110                         else
 111                                 newNode = node[nodes[start].parent].bottom_left;
 112
 113                         return GetNeighbour(newNode, xdir + 1, ydir);
 114                 case QTC_TOP_LEFT:
 115                 case QTC_BOTTOM_LEFT:
 116                         QuadTreeIndex left_parent = GetNeighbour(nodes[start].parent, -1, 0);
 117                         if (left_parent == -1) return -1;
 118                         QuadTreeIndex newNode;
 119                         if (nodes[start].child_type == QTC_TOP_LEFT)
 120                                 newNode = node[left_parent].top_right;
 121                         else
 122                                 newNode = node[left_parent].bottom_right;
 123                         return GetNeighbour(newNode, xdir + 1, ydir);
 124
 125                 }
 126         }
 127
 128         // Try moving to the bottom.
 129         if (ydir > 0)
 130         {
 131                 switch (nodes[start].child_type)
 132                 {
 133                 case QTC_TOP_LEFT:
 134                 case QTC_TOP_RIGHT:
 135                         QuadTreeIndex newNode;
 136                         if (nodes[start].child_type == QTC_TOP_LEFT)
 137                                 newNode = node[nodes[start].parent].bottom_left;
 138                         else
 139                                 newNode = node[nodes[start].parent].bottom_right;
 140
 141                         return GetNeighbour(newNode, xdir, ydir - 1);
 142                 case QTC_BOTTOM_LEFT:
 143                 case QTC_BOTTOM_RIGHT:
 144                         QuadTreeIndex bottom_parent = GetNeighbour(nodes[start].parent, 0, 1);
 145                         if (bottom_parent == -1) return -1;
 146                         QuadTreeIndex newNode;
 147                         if (nodes[start].child_type == QTC_BOTTOM_LEFT)
 148                                 newNode = node[bottom__parent].top_left;
 149                         else
 150                                 newNode = node[bottom_parent].top_right;
 151                         return GetNeighbour(newNode, xdir, ydir - 1);
 152
 153                 }
 154         }
 155
 156         // Try moving up, towards the sky.
 157         if (ydir < 0)
 158         {
 159                 switch (nodes[start].child_type)
 160                 {
 161                 case QTC_BOTTOM_LEFT:
 162                 case QTC_BOTTOM_RIGHT:
 163                         QuadTreeIndex newNode;
 164                         if (nodes[start].child_type == QTC_BOTTOM_LEFT)
 165                                 newNode = node[nodes[start].parent].top_left;
 166                         else
 167                                 newNode = node[nodes[start].parent].top_right;
 168
 169                         return GetNeighbour(newNode, xdir, ydir + 1);
 170                 case QTC_TOP_LEFT:
 171                 case QTC_BOTTOM_LEFT:
 172                         QuadTreeIndex top_parent = GetNeighbour(nodes[start].parent, 0, -1);
 173                         if (top_parent == -1) return -1;
 174                         QuadTreeIndex newNode;
 175                         if (nodes[start].child_type == QTC_TOP_LEFT)
 176                                 newNode = node[top_parent].bottom_left;
 177                         else
 178                                 newNode = node[top_parent].bottom_right;
 179                         return GetNeighbour(newNode, xdir, ydir + 1);
 180
 181                 }
 182         }
 183         return -1;
 184 }
 185
 186 }
 187
 188 #endif