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         if (addTo && (nodes[start].parent == -1) && nodes[start].child_type != QTC_UNKNOWN)
  74         {
  75                 Debug("Adding parent of node %d...", start);
  76                 addTo->GenQuadParent(start, nodes[start].child_type);
  77         }
  78
  79         QuadTreeIndex newNode;
  80         // Try moving to the right if that's easy.
  81         if (xdir > 0)
  82         {
  83                 switch (nodes[start].child_type)
  84                 {
  85                 case QTC_TOP_LEFT:
  86                 case QTC_BOTTOM_LEFT:
  87                 {
  88                         if (nodes[start].child_type == QTC_TOP_LEFT)
  89                         {
  90                                 newNode = nodes[nodes[start].parent].top_right;
  91                                 if (addTo && newNode == -1)
  92                                 {
  93                                         newNode = addTo->GenQuadChild(nodes[start].parent, QTC_TOP_RIGHT);
  94                                 }
  95                         }
  96                         else
  97                         {
  98                                 newNode = nodes[nodes[start].parent].bottom_right;
  99                                 if (addTo && newNode == -1)
 100                                 {
 101                                         newNode = addTo->GenQuadChild(nodes[start].parent, QTC_BOTTOM_RIGHT);
 102                                 }
 103                         }
 104                         return GetNeighbour(newNode, xdir - 1, ydir, addTo);
 105                 }
 106                 case QTC_TOP_RIGHT:
 107                 case QTC_BOTTOM_RIGHT:
 108                 {
 109                         QuadTreeIndex right_parent = GetNeighbour(nodes[start].parent, 1, 0, addTo);
 110                         if (right_parent == -1) return -1;
 111                         if (nodes[start].child_type == QTC_TOP_RIGHT)
 112                         {
 113                                 newNode = nodes[right_parent].top_left;
 114                                 if (addTo && newNode == -1)
 115                                 {
 116                                         newNode = addTo->GenQuadChild(right_parent, QTC_TOP_LEFT);
 117                                 }
 118                         }
 119                         else
 120                         {
 121                                 newNode = nodes[right_parent].bottom_left;
 122                                 if (addTo && newNode == -1)
 123                                 {
 124                                         newNode = addTo->GenQuadChild(right_parent, QTC_BOTTOM_LEFT);
 125                                 }
 126                         }
 127                         return GetNeighbour(newNode, xdir - 1, ydir, addTo);
 128                 }
 129                 default:
 130                         return -1;
 131
 132                 }
 133         }
 134
 135         // Try moving to the left.
 136         if (xdir < 0)
 137         {
 138                 switch (nodes[start].child_type)
 139                 {
 140                 case QTC_TOP_RIGHT:
 141                 case QTC_BOTTOM_RIGHT:
 142                 {
 143                         if (nodes[start].child_type == QTC_TOP_RIGHT)
 144                         {
 145                                 newNode = nodes[nodes[start].parent].top_left;
 146                                 if (addTo && newNode == -1)
 147                                 {
 148                                         newNode = addTo->GenQuadChild(nodes[start].parent, QTC_TOP_LEFT);
 149                                 }
 150                         }
 151                         else
 152                         {
 153                                 newNode = nodes[nodes[start].parent].bottom_left;
 154                                 if (addTo && newNode == -1)
 155                                 {
 156                                         newNode = addTo->GenQuadChild(nodes[start].parent, QTC_BOTTOM_LEFT);
 157                                 }
 158                         }
 159
 160                         return GetNeighbour(newNode, xdir + 1, ydir, addTo);
 161                 }
 162                 case QTC_TOP_LEFT:
 163                 case QTC_BOTTOM_LEFT:
 164                 {
 165                         QuadTreeIndex left_parent = GetNeighbour(nodes[start].parent, -1, 0, addTo);
 166                         if (left_parent == -1) return -1;
 167                         if (nodes[start].child_type == QTC_TOP_LEFT)
 168                         {
 169                                 newNode = nodes[left_parent].top_right;
 170                                 if (addTo && newNode == -1)
 171                                 {
 172                                         newNode = addTo->GenQuadChild(left_parent, QTC_TOP_RIGHT);
 173                                 }
 174                         }
 175                         else
 176                         {
 177                                 newNode = nodes[left_parent].bottom_right;
 178                                 if (addTo && newNode == -1)
 179                                 {
 180                                         newNode = addTo->GenQuadChild(left_parent, QTC_BOTTOM_RIGHT);
 181                                 }
 182                         }
 183                         return GetNeighbour(newNode, xdir + 1, ydir, addTo);
 184                 }
 185                 default:
 186                         return -1;
 187                 }
 188         }
 189
 190         // Try moving to the bottom.
 191         if (ydir > 0)
 192         {
 193                 switch (nodes[start].child_type)
 194                 {
 195                 case QTC_TOP_LEFT:
 196                 case QTC_TOP_RIGHT:
 197                 {
 198                         if (nodes[start].child_type == QTC_TOP_LEFT)
 199                         {
 200                                 newNode = nodes[nodes[start].parent].bottom_left;
 201                                 if (addTo && newNode == -1)
 202                                 {
 203                                         newNode = addTo->GenQuadChild(nodes[start].parent, QTC_BOTTOM_LEFT);
 204                                 }
 205                         }
 206                         else
 207                         {
 208                                 newNode = nodes[nodes[start].parent].bottom_right;
 209                                 if (addTo && newNode == -1)
 210                                 {
 211                                         newNode = addTo->GenQuadChild(nodes[start].parent, QTC_BOTTOM_RIGHT);
 212                                 }
 213                         }
 214                         return GetNeighbour(newNode, xdir, ydir - 1, addTo);
 215                 }
 216                 case QTC_BOTTOM_LEFT:
 217                 case QTC_BOTTOM_RIGHT:
 218                 {
 219                         QuadTreeIndex bottom_parent = GetNeighbour(nodes[start].parent, 0, 1, addTo);
 220                         if (bottom_parent == -1) return -1;
 221                         if (nodes[start].child_type == QTC_BOTTOM_LEFT)
 222                         {
 223                                 newNode = nodes[bottom_parent].top_left;
 224                                 if (addTo && newNode == -1)
 225                                 {
 226                                         newNode = addTo->GenQuadChild(bottom_parent, QTC_TOP_LEFT);
 227                                 }
 228                         }
 229                         else
 230                         {
 231                                 newNode = nodes[bottom_parent].top_right;
 232                                 if (addTo && newNode == -1)
 233                                 {
 234                                         newNode = addTo->GenQuadChild(bottom_parent, QTC_TOP_RIGHT);
 235                                 }
 236                         }
 237                         return GetNeighbour(newNode, xdir, ydir - 1, addTo);
 238                 }
 239                 default:
 240                         return -1;
 241                 }
 242         }
 243
 244         // Try moving up, towards the sky.
 245         if (ydir < 0)
 246         {
 247                 switch (nodes[start].child_type)
 248                 {
 249                 case QTC_BOTTOM_LEFT:
 250                 case QTC_BOTTOM_RIGHT:
 251                 {
 252                         if (nodes[start].child_type == QTC_BOTTOM_LEFT)
 253                         {
 254                                 newNode = nodes[nodes[start].parent].top_left;
 255                                 if (addTo && newNode == -1)
 256                                 {
 257                                         newNode = addTo->GenQuadChild(nodes[start].parent, QTC_TOP_LEFT);
 258                                 }
 259                         }
 260                         else
 261                         {
 262                                 newNode = nodes[nodes[start].parent].top_right;
 263                                 if (addTo && newNode == -1)
 264                                 {
 265                                         newNode = addTo->GenQuadChild(nodes[start].parent, QTC_TOP_RIGHT);
 266                                 }
 267                         }
 268                         return GetNeighbour(newNode, xdir, ydir + 1, addTo);
 269                 }
 270                 case QTC_TOP_LEFT:
 271                 case QTC_TOP_RIGHT:
 272                 {
 273                         QuadTreeIndex top_parent = GetNeighbour(nodes[start].parent, 0, -1, addTo);
 274                         if (top_parent == -1) return -1;
 275                         if (nodes[start].child_type == QTC_TOP_LEFT)
 276                         {
 277                                 newNode = nodes[top_parent].bottom_left;
 278                                 if (addTo && newNode == -1)
 279                                 {
 280                                         newNode = addTo->GenQuadChild(top_parent, QTC_BOTTOM_LEFT);
 281                                 }
 282                         }
 283                         else
 284                         {
 285                                 newNode = nodes[top_parent].bottom_right;
 286                                 if (addTo && newNode == -1)
 287                                 {
 288                                         newNode = addTo->GenQuadChild(top_parent, QTC_BOTTOM_RIGHT);
 289                                 }
 290                         }
 291                         return GetNeighbour(newNode, xdir, ydir + 1, addTo);
 292                 }
 293                 default:
 294                         return -1;
 295                 }
 296         }
 297         return -1;
 298 }
 299
 300 }
 301
 302 #endif