src/quadtree.cpp

   1 #ifndef QUADTREE_REMOVED
   2 #include "quadtree.h"
   3 #include "document.h"
   4
   5 namespace IPDF {
   6
   7 Rect TransformToQuadChild(const Rect& src, QuadTreeNodeChildren child_type)
   8 {
   9         Rect dst = src;
  10         dst.x *= 2;
  11         dst.y *= 2;
  12         dst.w *= 2;
  13         dst.h *= 2;
  14         if (child_type == QTC_BOTTOM_LEFT || child_type == QTC_BOTTOM_RIGHT)
  15         {
  16                 dst.y -= 1;
  17         }
  18         if (child_type == QTC_TOP_RIGHT || child_type == QTC_BOTTOM_RIGHT)
  19         {
  20                 dst.x -= 1;
  21         }
  22         return dst;
  23 }
  24
  25 Rect TransformFromQuadChild(const Rect& src, QuadTreeNodeChildren child_type)
  26 {
  27         Rect dst = src;
  28         if (child_type == QTC_BOTTOM_LEFT || child_type == QTC_BOTTOM_RIGHT)
  29         {
  30                 dst.y += 1;
  31         }
  32         if (child_type == QTC_TOP_RIGHT || child_type == QTC_BOTTOM_RIGHT)
  33         {
  34                 dst.x += 1;
  35         }
  36         dst.x *= 0.5;
  37         dst.y *= 0.5;
  38         dst.w *= 0.5;
  39         dst.h *= 0.5;
  40         return dst;
  41 }
  42
  43 bool IntersectsQuadChild(const Rect& src, QuadTreeNodeChildren child_type)
  44 {
  45         Rect std = {0,0,1,1};
  46         Rect dst = TransformFromQuadChild(std, child_type);
  47         if (src.x + src.w < dst.x) return false;
  48         if (src.y + src.h < dst.y) return false;
  49         if (src.x > dst.x + dst.w) return false;
  50         if (src.y > dst.y + dst.h) return false;
  51         //Debug("%s is contained in %s\n", src.Str().c_str(), dst.Str().c_str());
  52         return true;
  53 }
  54
  55 bool ContainedInQuadChild(const Rect& src, QuadTreeNodeChildren child_type)
  56 {
  57         Rect std = {0,0,1,1};
  58         Rect dst = TransformFromQuadChild(std, child_type);
  59         if (src.x < dst.x) return false;
  60         if (src.y < dst.y) return false;
  61         if (src.x + src.w > dst.x + dst.w) return false;
  62         if (src.y + src.h > dst.y + dst.h) return false;
  63         //Debug("%s is contained in %s... \n", src.Str().c_str(), dst.Str().c_str());
  64         return true;
  65 }
  66
  67
  68
  69 QuadTreeIndex QuadTree::GetNeighbour(QuadTreeIndex start, int xdir, int ydir, Document *addTo) const
  70 {
  71         if (!xdir && !ydir) return start;
  72
  73         QuadTreeIndex newNode;
  74         // Try moving to the right if that's easy.
  75         if (xdir > 0)
  76         {
  77                 switch (nodes[start].child_type)
  78                 {
  79                 case QTC_TOP_LEFT:
  80                 case QTC_BOTTOM_LEFT:
  81                 {
  82                         if (nodes[start].child_type == QTC_TOP_LEFT)
  83                         {
  84                                 newNode = nodes[nodes[start].parent].top_right;
  85                                 if (addTo && newNode == -1)
  86                                 {
  87                                         newNode = addTo->GenQuadChild(nodes[start].parent, QTC_TOP_RIGHT);
  88                                 }
  89                         }
  90                         else
  91                         {
  92                                 newNode = nodes[nodes[start].parent].bottom_right;
  93                                 if (addTo && newNode == -1)
  94                                 {
  95                                         newNode = addTo->GenQuadChild(nodes[start].parent, QTC_BOTTOM_RIGHT);
  96                                 }
  97                         }
  98                         return GetNeighbour(newNode, xdir - 1, ydir, addTo);
  99                 }
 100                 case QTC_TOP_RIGHT:
 101                 case QTC_BOTTOM_RIGHT:
 102                 {
 103                         QuadTreeIndex right_parent = GetNeighbour(nodes[start].parent, 1, 0, addTo);
 104                         if (right_parent == -1) return -1;
 105                         if (nodes[start].child_type == QTC_TOP_RIGHT)
 106                         {
 107                                 newNode = nodes[right_parent].top_left;
 108                                 if (addTo && newNode == -1)
 109                                 {
 110                                         newNode = addTo->GenQuadChild(right_parent, QTC_TOP_LEFT);
 111                                 }
 112                         }
 113                         else
 114                         {
 115                                 newNode = nodes[right_parent].bottom_left;
 116                                 if (addTo && newNode == -1)
 117                                 {
 118                                         newNode = addTo->GenQuadChild(right_parent, QTC_BOTTOM_LEFT);
 119                                 }
 120                         }
 121                         return GetNeighbour(newNode, xdir - 1, ydir, addTo);
 122                 }
 123                 default:
 124                         return -1;
 125
 126                 }
 127         }
 128
 129         // Try moving to the left.
 130         if (xdir < 0)
 131         {
 132                 switch (nodes[start].child_type)
 133                 {
 134                 case QTC_TOP_RIGHT:
 135                 case QTC_BOTTOM_RIGHT:
 136                 {
 137                         if (nodes[start].child_type == QTC_TOP_RIGHT)
 138                         {
 139                                 newNode = nodes[nodes[start].parent].top_left;
 140                                 if (addTo && newNode == -1)
 141                                 {
 142                                         newNode = addTo->GenQuadChild(nodes[start].parent, QTC_TOP_LEFT);
 143                                 }
 144                         }
 145                         else
 146                         {
 147                                 newNode = nodes[nodes[start].parent].bottom_left;
 148                                 if (addTo && newNode == -1)
 149                                 {
 150                                         newNode = addTo->GenQuadChild(nodes[start].parent, QTC_BOTTOM_LEFT);
 151                                 }
 152                         }
 153
 154                         return GetNeighbour(newNode, xdir + 1, ydir, addTo);
 155                 }
 156                 case QTC_TOP_LEFT:
 157                 case QTC_BOTTOM_LEFT:
 158                 {
 159                         QuadTreeIndex left_parent = GetNeighbour(nodes[start].parent, -1, 0, addTo);
 160                         if (left_parent == -1) return -1;
 161                         if (nodes[start].child_type == QTC_TOP_LEFT)
 162                         {
 163                                 newNode = nodes[left_parent].top_right;
 164                                 if (addTo && newNode == -1)
 165                                 {
 166                                         newNode = addTo->GenQuadChild(left_parent, QTC_TOP_RIGHT);
 167                                 }
 168                         }
 169                         else
 170                         {
 171                                 newNode = nodes[left_parent].bottom_right;
 172                                 if (addTo && newNode == -1)
 173                                 {
 174                                         newNode = addTo->GenQuadChild(left_parent, QTC_BOTTOM_RIGHT);
 175                                 }
 176                         }
 177                         return GetNeighbour(newNode, xdir + 1, ydir, addTo);
 178                 }
 179                 default:
 180                         return -1;
 181                 }
 182         }
 183
 184         // Try moving to the bottom.
 185         if (ydir > 0)
 186         {
 187                 switch (nodes[start].child_type)
 188                 {
 189                 case QTC_TOP_LEFT:
 190                 case QTC_TOP_RIGHT:
 191                 {
 192                         if (nodes[start].child_type == QTC_TOP_LEFT)
 193                         {
 194                                 newNode = nodes[nodes[start].parent].bottom_left;
 195                                 if (addTo && newNode == -1)
 196                                 {
 197                                         newNode = addTo->GenQuadChild(nodes[start].parent, QTC_BOTTOM_LEFT);
 198                                 }
 199                         }
 200                         else
 201                         {
 202                                 newNode = nodes[nodes[start].parent].bottom_right;
 203                                 if (addTo && newNode == -1)
 204                                 {
 205                                         newNode = addTo->GenQuadChild(nodes[start].parent, QTC_BOTTOM_RIGHT);
 206                                 }
 207                         }
 208                         return GetNeighbour(newNode, xdir, ydir - 1, addTo);
 209                 }
 210                 case QTC_BOTTOM_LEFT:
 211                 case QTC_BOTTOM_RIGHT:
 212                 {
 213                         QuadTreeIndex bottom_parent = GetNeighbour(nodes[start].parent, 0, 1, addTo);
 214                         if (bottom_parent == -1) return -1;
 215                         if (nodes[start].child_type == QTC_BOTTOM_LEFT)
 216                         {
 217                                 newNode = nodes[bottom_parent].top_left;
 218                                 if (addTo && newNode == -1)
 219                                 {
 220                                         newNode = addTo->GenQuadChild(bottom_parent, QTC_TOP_LEFT);
 221                                 }
 222                         }
 223                         else
 224                         {
 225                                 newNode = nodes[bottom_parent].top_right;
 226                                 if (addTo && newNode == -1)
 227                                 {
 228                                         newNode = addTo->GenQuadChild(bottom_parent, QTC_TOP_RIGHT);
 229                                 }
 230                         }
 231                         return GetNeighbour(newNode, xdir, ydir - 1, addTo);
 232                 }
 233                 default:
 234                         return -1;
 235                 }
 236         }
 237
 238         // Try moving up, towards the sky.
 239         if (ydir < 0)
 240         {
 241                 switch (nodes[start].child_type)
 242                 {
 243                 case QTC_BOTTOM_LEFT:
 244                 case QTC_BOTTOM_RIGHT:
 245                 {
 246                         if (nodes[start].child_type == QTC_BOTTOM_LEFT)
 247                         {
 248                                 newNode = nodes[nodes[start].parent].top_left;
 249                                 if (addTo && newNode == -1)
 250                                 {
 251                                         newNode = addTo->GenQuadChild(nodes[start].parent, QTC_TOP_LEFT);
 252                                 }
 253                         }
 254                         else
 255                         {
 256                                 newNode = nodes[nodes[start].parent].top_right;
 257                                 if (addTo && newNode == -1)
 258                                 {
 259                                         newNode = addTo->GenQuadChild(nodes[start].parent, QTC_TOP_RIGHT);
 260                                 }
 261                         }
 262                         return GetNeighbour(newNode, xdir, ydir + 1, addTo);
 263                 }
 264                 case QTC_TOP_LEFT:
 265                 case QTC_TOP_RIGHT:
 266                 {
 267                         QuadTreeIndex top_parent = GetNeighbour(nodes[start].parent, 0, -1, addTo);
 268                         if (top_parent == -1) return -1;
 269                         if (nodes[start].child_type == QTC_TOP_LEFT)
 270                         {
 271                                 newNode = nodes[top_parent].bottom_left;
 272                                 if (addTo && newNode == -1)
 273                                 {
 274                                         newNode = addTo->GenQuadChild(top_parent, QTC_BOTTOM_LEFT);
 275                                 }
 276                         }
 277                         else
 278                         {
 279                                 newNode = nodes[top_parent].bottom_right;
 280                                 if (addTo && newNode == -1)
 281                                 {
 282                                         newNode = addTo->GenQuadChild(top_parent, QTC_BOTTOM_RIGHT);
 283                                 }
 284                         }
 285                         return GetNeighbour(newNode, xdir, ydir + 1, addTo);
 286                 }
 287                 default:
 288                         return -1;
 289                 }
 290         }
 291         return -1;
 292 }
 293
 294 }
 295
 296 #endif