kdtree.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_KDTREE_H
#define INCLUDE_JET_KDTREE_H
 
#include <jet/bounding_box2.h>
#include <jet/bounding_box3.h>
#include <jet/vector2.h>
#include <jet/vector3.h>
#include <jet/vector4.h>
 
#include <vector>
 
namespace jet {
 
template <typename T, size_t K>
class KdTree final {
 public:
    typedef Vector<T, K> Point;
    typedef BoundingBox<T, K> BBox;
 
    struct Node {
        size_t flags = 0;
 
        size_t child = kMaxSize;
 
        size_t item = kMaxSize;
 
        Point point;
 
        Node();
 
        void initLeaf(size_t it, const Point& pt);
 
        void initInternal(size_t axis, size_t it, size_t c, const Point& pt);
 
        bool isLeaf() const;
    };
 
    typedef std::vector<Point> ContainerType;
    typedef typename ContainerType::iterator Iterator;
    typedef typename ContainerType::const_iterator ConstIterator;
 
    typedef std::vector<Node> NodeContainerType;
    typedef typename NodeContainerType::iterator NodeIterator;
    typedef typename NodeContainerType::const_iterator ConstNodeIterator;
 
    KdTree();
 
    void build(const ConstArrayAccessor1<Point>& points);
 
    void forEachNearbyPoint(
        const Point& origin, T radius,
        const std::function<void(size_t, const Point&)>& callback) const;
 
    bool hasNearbyPoint(const Point& origin, T radius) const;
 
    size_t nearestPoint(const Point& origin) const;
 
    Iterator begin();
 
    Iterator end();
 
    ConstIterator begin() const;
 
    ConstIterator end() const;
 
    NodeIterator beginNode();
 
    NodeIterator endNode();
 
    ConstNodeIterator beginNode() const;
 
    ConstNodeIterator endNode() const;
 
    void reserve(size_t numPoints, size_t numNodes);
 
 private:
    std::vector<Point> _points;
    std::vector<Node> _nodes;
 
    size_t build(size_t nodeIndex, size_t* itemIndices, size_t nItems,
                 size_t currentDepth);
};
 
}  // namespace jet
 
#include "detail/kdtree-inl.h"
 
#endif  // INCLUDE_JET_KDTREE_H