OctTree.h

Go to the documentation of this file.

// SPDX-FileCopyrightText: Copyright (c) OpenGeoSys Community (opengeosys.org)
// SPDX-License-Identifier: BSD-3-Clause
 
#pragma once
 
#include <Eigen/Core>
#include <cstdint>
#include <limits>
#include <vector>
 
namespace GeoLib
{
template <typename POINT, std::size_t MAX_POINTS>
class OctTree
{
public:
    static OctTree<POINT, MAX_POINTS>* createOctTree(
        Eigen::Vector3d ll, Eigen::Vector3d ur,
        double eps = std::numeric_limits<double>::epsilon());

    virtual ~OctTree();

    bool addPoint(POINT* pnt, POINT*& ret_pnt);

    template <typename T>
    void getPointsInRange(T const& min, T const& max,
                          std::vector<POINT*>& pnts) const;
 
#ifndef NDEBUG
    Eigen::Vector3d const& getLowerLeftCornerPoint() const { return _ll; }
    Eigen::Vector3d const& getUpperRightCornerPoint() const { return _ur; }
    OctTree<POINT, MAX_POINTS> const* getChild(std::size_t i) const
    {
        return _children[i];
    }
    std::vector<POINT*> const& getPointVector() const { return _pnts; }
#endif
 
private:
    OctTree(Eigen::Vector3d const& ll, Eigen::Vector3d const& ur, double eps);
 
    enum class Quadrant : std::int8_t
    {
        NEL = 0,  
        NWL,      
        SWL,      
        SEL,      
        NEU,      
        NWU,      
        SWU,      
        SEU       
    };

    bool addPoint_(POINT* pnt, POINT*& ret_pnt);

    bool addPointToChild(POINT* pnt);

    void splitNode(POINT* pnt);

    bool isOutside(POINT* pnt) const;

    template <typename T>
    void getPointsInRange_(T const& min, T const& max,
                           std::vector<POINT*>& pnts) const;

    std::array<OctTree<POINT, MAX_POINTS>*, 8> _children;
    Eigen::Vector3d const _ll;
    Eigen::Vector3d const _ur;
    std::vector<POINT*> _pnts;
    bool _is_leaf;
    double const _eps;
};
 
}  // end namespace GeoLib
 
#include "OctTree-impl.h"