CQuadTree::Split()

QuadTreeSplit.hpp

void CQuadTree::Split(QTNode* pNode)
{
  // Children already exist? This shouldn't happen.
  if(pNode->pChildren != nullptr)
  {
    // Delete the actual nodes.
    for(size_t i = 0; i < 4; ++i) delete pNode->pChildren[i];
    
    // Then delete the pointer array to the nodes.
    delete[] pNode->pChildren;
  }
  
  // Array of pointers (16 bytes).
  pNode->pChildren = new QTNode*[4];
  
  // Starting position of the node, so we can adjust as
  // necessary for the split.
  float x = pNode->Rect.x;
  float y = pNode->Rect.y;
  
  // Iterate over each child.
  for(size_t i = 0; i < 4; ++i)
  {
    pNode->pChildren[i] = new QTNode;         // Actually make the new node.
    pNode->pChildren[i]->pChildren = nullptr; // No children
    pNode->pChildren[i]->pParent = pNode;     // Assign parent node
    pNode->pChildren[i]->Rect = rect_t(pNode->Rect.x,
                                       pNode->Rect.y,
                                       pNode->Rect.w,
                                       pNode->Rect.h);  // Give it the parent
                                       
    pNode->pChildren[i]->depth  = pNode->depth + 1; // Depth is one lower level
  
    // Rect should be half size. The w++ and h++ parts are because
    // as the nodes get smaller, they may gain an odd value (like
    // 800/2/2/2/2/2 = 25) and the next split will be off-by-one due
    // to integer division. Then, a failure to insert an object may occur
    // because it doesn't fit in a node due to the spacing. Thus we compensate
    // by making the node 1x1 bigger than it needs to be.
    pNode->pChildren[i]->Rect.w /= 2; pNode->pChildren[i]->Rect.w++;
    pNode->pChildren[i]->Rect.h /= 2; pNode->pChildren[i]->Rect.h++;
    
    // Assign position of the node.
    pNode->pChildren[i]->Rect.x = x;
    pNode->pChildren[i]->Rect.y = y;
  
    // Add the objects from the parent node to the current child, if 
    // they belong there.
    for(auto j = pNode->nodeObjects.begin();
        j != pNode->nodeObjects.end(); )
    {
      if((*j)->DetectCollision(pNode->pChildren[i]->Rect))
      {
        pNode->pChildren[i]->nodeObjects.push_back(*j);
        j = pNode->nodeObjects.erase(j);
      }
      else
      {
        ++j;
      }
    }
  
    // Adjust the offset (goes from left to middle)
    x += pNode->pChildren[i]->Rect.w;
    
    // If we've reached the end, start on the next row.
    // (goes from top-middle to middle-left)
    if(x >= pNode->Rect.x + pNode->Rect.w)
    {
      x  = pNode->Rect.x;
      y += pNode->pChildren[i]->Rect.h;
    }
  }
  
  // The parent object list should already be empty, but 
  // this is just in case.
  pNode->nodeObjects.clear();
}