quad_tree.h

#pragma once
#include "triangle.h"
#include <memory>
#include <vector>
#include "box.h"
#include <set>

const int POINT_NOT_IN_QUADTREE = -1;
const int QUADTREE_MAX_DEPTH = 5;

#define QUADTREE_NODE_MAX_SHAPE 4

class QuadTree
{
    Box b;
    int level;
    std::vector<Triangle> triangles;

    std::vector<QuadTree> children;
    QuadTree(Box b, int level);
    void collectUniqueTriangleFragments(const Triangle &t, std::set<int> &seen, std::vector<Triangle> &result) const;
    void split();
    void addNonIntersectingTriangle(const Triangle &t);

    std::vector<Triangle> visibleSurface(std::set<int> &seen) const;
public:
    QuadTree(Box b);
    void addTriangle(const Triangle &triangle);
    std::vector<Triangle> visibleSurface() const;
    // returns triangle id
    int pointIntersection(const Point &p) const;
};