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) const
  69 {
  70         if (!xdir && !ydir) return start;
  71
  72         QuadTreeIndex newNode;
  73         // Try moving to the right if that's easy.
  74         if (xdir > 0)
  75         {
  76                 switch (nodes[start].child_type)
  77                 {
  78                 case QTC_TOP_LEFT:
  79                 case QTC_BOTTOM_LEFT:
  80                 {
  81                         if (nodes[start].child_type == QTC_TOP_LEFT)
  82                                 newNode = nodes[nodes[start].parent].top_right;
  83                         else
  84                                 newNode = nodes[nodes[start].parent].bottom_right;
  85
  86                         return GetNeighbour(newNode, xdir - 1, ydir);
  87                 }
  88                 case QTC_TOP_RIGHT:
  89                 case QTC_BOTTOM_RIGHT:
  90                 {
  91                         QuadTreeIndex right_parent = GetNeighbour(nodes[start].parent, 1, 0);
  92                         if (right_parent == -1) return -1;
  93                         if (nodes[start].child_type == QTC_TOP_RIGHT)
  94                                 newNode = nodes[right_parent].top_left;
  95                         else
  96                                 newNode = nodes[right_parent].bottom_left;
  97                         return GetNeighbour(newNode, xdir - 1, ydir);
  98                 }
  99                 default:
 100                         return -1;
 101
 102                 }
 103         }
 104
 105         // Try moving to the left.
 106         if (xdir < 0)
 107         {
 108                 switch (nodes[start].child_type)
 109                 {
 110                 case QTC_TOP_RIGHT:
 111                 case QTC_BOTTOM_RIGHT:
 112                 {
 113                         if (nodes[start].child_type == QTC_TOP_RIGHT)
 114                                 newNode = nodes[nodes[start].parent].top_left;
 115                         else
 116                                 newNode = nodes[nodes[start].parent].bottom_left;
 117
 118                         return GetNeighbour(newNode, xdir + 1, ydir);
 119                 }
 120                 case QTC_TOP_LEFT:
 121                 case QTC_BOTTOM_LEFT:
 122                 {
 123                         QuadTreeIndex left_parent = GetNeighbour(nodes[start].parent, -1, 0);
 124                         if (left_parent == -1) return -1;
 125                         if (nodes[start].child_type == QTC_TOP_LEFT)
 126                                 newNode = nodes[left_parent].top_right;
 127                         else
 128                                 newNode = nodes[left_parent].bottom_right;
 129                         return GetNeighbour(newNode, xdir + 1, ydir);
 130                 }
 131                 default:
 132                         return -1;
 133                 }
 134         }
 135
 136         // Try moving to the bottom.
 137         if (ydir > 0)
 138         {
 139                 switch (nodes[start].child_type)
 140                 {
 141                 case QTC_TOP_LEFT:
 142                 case QTC_TOP_RIGHT:
 143                 {
 144                         if (nodes[start].child_type == QTC_TOP_LEFT)
 145                                 newNode = nodes[nodes[start].parent].bottom_left;
 146                         else
 147                                 newNode = nodes[nodes[start].parent].bottom_right;
 148
 149                         return GetNeighbour(newNode, xdir, ydir - 1);
 150                 }
 151                 case QTC_BOTTOM_LEFT:
 152                 case QTC_BOTTOM_RIGHT:
 153                 {
 154                         QuadTreeIndex bottom_parent = GetNeighbour(nodes[start].parent, 0, 1);
 155                         if (bottom_parent == -1) return -1;
 156                         if (nodes[start].child_type == QTC_BOTTOM_LEFT)
 157                                 newNode = nodes[bottom_parent].top_left;
 158                         else
 159                                 newNode = nodes[bottom_parent].top_right;
 160                         return GetNeighbour(newNode, xdir, ydir - 1);
 161                 }
 162                 default:
 163                         return -1;
 164                 }
 165         }
 166
 167         // Try moving up, towards the sky.
 168         if (ydir < 0)
 169         {
 170                 switch (nodes[start].child_type)
 171                 {
 172                 case QTC_BOTTOM_LEFT:
 173                 case QTC_BOTTOM_RIGHT:
 174                 {
 175                         if (nodes[start].child_type == QTC_BOTTOM_LEFT)
 176                                 newNode = nodes[nodes[start].parent].top_left;
 177                         else
 178                                 newNode = nodes[nodes[start].parent].top_right;
 179
 180                         return GetNeighbour(newNode, xdir, ydir + 1);
 181                 }
 182                 case QTC_TOP_LEFT:
 183                 case QTC_TOP_RIGHT:
 184                 {
 185                         QuadTreeIndex top_parent = GetNeighbour(nodes[start].parent, 0, -1);
 186                         if (top_parent == -1) return -1;
 187                         if (nodes[start].child_type == QTC_TOP_LEFT)
 188                                 newNode = nodes[top_parent].bottom_left;
 189                         else
 190                                 newNode = nodes[top_parent].bottom_right;
 191                         return GetNeighbour(newNode, xdir, ydir + 1);
 192                 }
 193                 default:
 194                         return -1;
 195                 }
 196         }
 197         return -1;
 198 }
 199
 200 }
 201
 202 #endif