Quadtree.h

Go to the documentation of this file.

/*************************************************************************
> File Name: Quadtree.h
> Project Name: CubbyFlow
> Author: Chan-Ho Chris Ohk
> Purpose: Generic quadtree data structure.
> Created Time: 2017/10/15
> Copyright (c) 2018, Chan-Ho Chris Ohk
*************************************************************************/
#ifndef CUBBYFLOW_QUADTREE_H
#define CUBBYFLOW_QUADTREE_H

#include <Core/QueryEngine/IntersectionQueryEngine2.h>
#include <Core/QueryEngine/NearestNeighborQueryEngine2.h>

namespace CubbyFlow
{
    template <typename T>
    class Quadtree final : public IntersectionQueryEngine2<T>, public NearestNeighborQueryEngine2<T>
    {
    public:
        using ContainerType = std::vector<T>;
        using Iterator = typename ContainerType::iterator;
        using ConstIterator = typename ContainerType::const_iterator;

        Quadtree();

        void Build(const std::vector<T>& items, const BoundingBox2D& bound,
            const BoxIntersectionTestFunc2<T>& testFunc, size_t maxDepth);

        void Clear();

        NearestNeighborQueryResult2<T> GetNearestNeighbor(
            const Vector2D& pt,
            const NearestNeighborDistanceFunc2<T>& distanceFunc) const override;

        bool IsIntersects(const BoundingBox2D& box,
            const BoxIntersectionTestFunc2<T>& testFunc) const override;

        bool IsIntersects(const Ray2D& ray,
            const RayIntersectionTestFunc2<T>& testFunc) const override;

        void ForEachIntersectingItem(
            const BoundingBox2D& box, const BoxIntersectionTestFunc2<T>& testFunc,
            const IntersectionVisitorFunc2<T>& visitorFunc) const override;

        void ForEachIntersectingItem(
            const Ray2D& ray, const RayIntersectionTestFunc2<T>& testFunc,
            const IntersectionVisitorFunc2<T>& visitorFunc) const override;

        ClosestIntersectionQueryResult2<T> GetClosestIntersection(
            const Ray2D& ray,
            const GetRayIntersectionFunc2<T>& testFunc) const override;

        Iterator begin();

        Iterator end();

        ConstIterator begin() const;

        ConstIterator end() const;

        size_t GetNumberOfItems() const;

        const T& GetItem(size_t i) const;

        size_t GetNumberOfNodes() const;

        const std::vector<size_t>& GetItemsAtNode(size_t nodeIdx) const;

        size_t GetChildIndex(size_t nodeIdx, size_t childIdx) const;

        const BoundingBox2D& GetBoundingBox() const;

        size_t GetMaxDepth() const;

    private:
        struct Node
        {
            size_t firstChild = std::numeric_limits<size_t>::max();
            std::vector<size_t> items;

            bool IsLeaf() const;
        };

        size_t m_maxDepth = 1;
        BoundingBox2D m_bbox;
        std::vector<T> m_items;
        std::vector<Node> m_nodes;

        void Build(size_t nodeIdx, size_t currentDepth,
            const BoundingBox2D& currentBound,
            const BoxIntersectionTestFunc2<T>& overlapsFunc);

        bool IsIntersects(const BoundingBox2D& box,
            const BoxIntersectionTestFunc2<T>& testFunc, size_t nodeIdx,
            const BoundingBox2D& currentBound) const;

        bool IsIntersects(const Ray2D& ray,
            const RayIntersectionTestFunc2<T>& testFunc, size_t nodeIdx,
            const BoundingBox2D& currentBound) const;

        void ForEachIntersectingItem(const BoundingBox2D& box,
            const BoxIntersectionTestFunc2<T>& testFunc,
            const IntersectionVisitorFunc2<T>& visitorFunc,
            size_t nodeIdx,
            const BoundingBox2D& currentBound) const;

        void ForEachIntersectingItem(const Ray2D& ray,
            const RayIntersectionTestFunc2<T>& testFunc,
            const IntersectionVisitorFunc2<T>& visitorFunc,
            size_t nodeIdx,
            const BoundingBox2D& currentBound) const;

        ClosestIntersectionQueryResult2<T> GetClosestIntersection(
            const Ray2D& ray, const GetRayIntersectionFunc2<T>& testFunc,
            size_t nodeIdx, const BoundingBox2D& currentBound,
            ClosestIntersectionQueryResult2<T> best) const;
    };
}

#include <Core/Geometry/Quadtree-Impl.h>

#endif