quadtree.hpp

#ifndef QUADTREE_HPP
#define QUADTREE_HPP
 
#include "triangulation.hpp"
#include <memory>
#include <optional>
#include <vector>
 
struct BoundingBox {
  double minX, minY, maxX, maxY;
 
  bool contains(double x, double y) const;
 
  bool intersects(const BoundingBox &other) const;
};
 
class QuadTree {
public:
  QuadTree(const BoundingBox &bounds, int depth = 0);
 
  void insert(const Triangle &triangle, const std::vector<Point> &points);
 
  std::optional<Triangle> find(double x, double y,
                               const std::vector<Point> &points) const;
 
private:
  BoundingBox bounds;
  int depth;
  static const int MAX_DEPTH = 10;
  static const int MAX_TRIANGLES = 1500; // Leaf capacity
 
  std::vector<Triangle> triangles;
  std::unique_ptr<QuadTree> children[4]; // NW, NE, SW, SE
 
  bool isLeaf() const;
  void subdivide();
};
 
#endif // QUADTREE_HPP