quadtree.h

Go to the documentation of this file.

// Copyright (c) 2018 Doyub Kim
//
// I am making my contributions/submissions to this project solely in my
// personal capacity and am not conveying any rights to any intellectual
// property of any third parties.
 
#ifndef INCLUDE_JET_QUADTREE_H_
#define INCLUDE_JET_QUADTREE_H_
 
#include <jet/intersection_query_engine2.h>
#include <jet/nearest_neighbor_query_engine2.h>
#include <vector>
 
namespace jet {
 
template <typename T>
class Quadtree final : public IntersectionQueryEngine2<T>,
                       public NearestNeighborQueryEngine2<T> {
 public:
    typedef std::vector<T> ContainerType;
    typedef typename ContainerType::iterator Iterator;
    typedef typename ContainerType::const_iterator ConstIterator;
 
    Quadtree();
 
    void build(const std::vector<T>& items, const BoundingBox2D& bound,
               const BoxIntersectionTestFunc2<T>& testFunc, size_t maxDepth);
 
    void clear();
 
    NearestNeighborQueryResult2<T> nearest(
        const Vector2D& pt,
        const NearestNeighborDistanceFunc2<T>& distanceFunc) const override;
 
    bool intersects(const BoundingBox2D& box,
                    const BoxIntersectionTestFunc2<T>& testFunc) const override;
 
    bool intersects(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> closestIntersection(
        const Ray2D& ray,
        const GetRayIntersectionFunc2<T>& testFunc) const override;
 
    Iterator begin();
 
    Iterator end();
 
    ConstIterator begin() const;
 
    ConstIterator end() const;
 
    size_t numberOfItems() const;
 
    const T& item(size_t i) const;
 
    size_t numberOfNodes() const;
 
    const std::vector<size_t>& itemsAtNode(size_t nodeIdx) const;
 
    size_t childIndex(size_t nodeIdx, size_t childIdx) const;
 
    const BoundingBox2D& boundingBox() const;
 
    size_t maxDepth() const;
 
 private:
    struct Node {
        size_t firstChild = kMaxSize;
        std::vector<size_t> items;
 
        bool isLeaf() const;
    };
 
    size_t _maxDepth = 1;
    BoundingBox2D _bbox;
    std::vector<T> _items;
    std::vector<Node> _nodes;
 
    void build(size_t nodeIdx, size_t currentDepth,
               const BoundingBox2D& currentBound,
               const BoxIntersectionTestFunc2<T>& overlapsFunc);
 
    bool intersects(const BoundingBox2D& box,
                    const BoxIntersectionTestFunc2<T>& testFunc, size_t nodeIdx,
                    const BoundingBox2D& currentBound) const;
 
    bool intersects(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> closestIntersection(
        const Ray2D& ray, const GetRayIntersectionFunc2<T>& testFunc,
        size_t nodeIdx, const BoundingBox2D& currentBound,
        ClosestIntersectionQueryResult2<T> best) const;
};
 
}  // namespace jet
 
#include "detail/quadtree-inl.h"
 
#endif  // INCLUDE_JET_QUADTREE_H_