KdTree.h

Go to the documentation of this file.

/*
 *  This is free software: you can redistribute it and/or modify it
 *  under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  any later version.
 *  The software is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *  You should have received a copy of the GNU General Public License
 *  along with the software. If not, see <http://www.gnu.org/licenses/>.
 *
 *  Copyright 2018, 2019, Jan Broeckhove and Bistromatics group.
 */

#pragma once

#include "AABBox.h"
#include "KdNode.h"

#include <cstddef>
#include <functional>
#include <memory>
#include <utility>
#include <vector>

namespace geopop {

template <typename P>
class KdTree
{
public:
        static_assert(P::dim > 0, "Cannot have points in 0 dimensions");

        KdTree();

        static KdTree Build(const std::vector<P>& points);

        void Apply(std::function<bool(const P&)> f) const;

        void Apply(std::function<bool(const P&)> f, const AABBox<P>& box) const;

        bool Contains(const P& point) const;

        bool Empty() const;

        std::size_t GetHeight() const;

        void Insert(P point);

        std::vector<P> Query(const AABBox<P>& box) const;

        std::size_t Size() const;

private:
        template <std::size_t D>
        static std::unique_ptr<kd::Node<P, D>> Construct(const std::vector<P>& points);

private:
        std::size_t                     m_size; 
        std::unique_ptr<kd::Node<P, 0>> m_root; 
};

} // namespace geopop