Quadtree.h

#pragma once
 
#include "Foundation/Geometry/Glm.hpp"
 
#include <array>
#include <vector>
#include <memory>
 
namespace Cogs {
  namespace Core {
 
    struct QuadBounds 
    { 
      glm::vec2 min;
      glm::vec2 max; 
    };
 
    struct QuadNode
    {
      // children quads
      std::array<std::unique_ptr<QuadNode>, 4> mChildren;
 
      // 2d points representing the arrows living in node. Policy to assign priority is nearness to node center 
      glm::vec2 mNearestArrow;
      //TODO: This can be improved (after the baseline works) by looking at a cell and immediate 
      //cell neighbours and choosing the most distant point instead of the point closest to the cell midpoint.
 
      // bounds of this quad
      QuadBounds mBounds;
    };
 
    class SeaCurrentQuadtree
    {
      std::unique_ptr<QuadNode> mRoot;    //Parent most node
      
 
      // get the dimensions of sub nodes
      QuadBounds computeSubQuad(const QuadBounds& bounds, int i) const;
      /* get and index representing to which subquadrant an arrow belongs*/
      int getSubQuad(const QuadBounds & bounds, const glm::vec2 & arrow) const;
      /* attempt to split a node, populating it's mChildren array*/
      void split(QuadNode* node);
      // clear tree
      void clear(QuadNode * node);
 
 
    public:
      SeaCurrentQuadtree(glm::vec2 min, glm::vec2 max)
      {
        mRoot = std::make_unique<QuadNode>();
        mRoot->mBounds = { min, max };
      };
 
      inline QuadNode* getRoot() const { return mRoot.get(); }
      inline bool isLeaf(const QuadNode* node) { return !static_cast<bool>(node->mChildren[0]); }
 
      // add a new node to the tree, split quads if conditions are met
      void insert(QuadNode * node, size_t depth, const glm::vec2 & arrow);
 
      // find a node in the tree. Returns priority value
      int search(QuadNode * node, const glm::vec2 & arrow, int priority) const;
      
    };
  }
}