kdtree.h

Go to the documentation of this file.

/******************************************************************************
 * Copyright 2014 Micah C Chambers (micahc.vt@gmail.com)
 *
 * NPL is free software: you can redistribute it and/or modify it under the
 * terms of the BSD 2-Clause License available in LICENSE or at
 * http://opensource.org/licenses/BSD-2-Clause
 *
 * @file kdtree.h
 *
 *****************************************************************************/

#ifndef KDTREE_H
#define KDTREE_H

#include <list>
#include <vector>

namespace npl {

template <size_t K, size_t E, typename T = double, typename D = double>
class KDTree;

template <size_t K, size_t E, typename T = double, typename D = double>
class KDTreeNode
{
    public:
        KDTreeNode(const std::vector<T>& pt, const std::vector<D>& data) :
            left(NULL), right(NULL)
        {
            size_t ii;
            for(ii=0; ii<K && ii<pt.size(); ii++)
                m_point[ii] = pt[ii];
            for(; ii<K; ii++)
                m_point[ii] = 0;

            for(ii=0; ii<E && ii<data.size(); ii++)
                m_data[ii] = data[ii];
            for(; ii<E; ii++)
                m_data[ii] = 0;
        };

        KDTreeNode(size_t plen, const T* pt, size_t dlen, const D* data) :
            left(NULL), right(NULL)
        {
            size_t ii;
            for(ii=0; ii<K && ii<plen; ii++)
                m_point[ii] = pt[ii];
            for(; ii<K; ii++)
                m_point[ii] = 0;

            for(ii=0; ii<E && ii<dlen; ii++)
                m_data[ii] = data[ii];
            for(; ii<E; ii++)
                m_data[ii] = 0;
        };

        T m_point[K];
        D m_data[E];
    private:
        KDTreeNode* left;
        KDTreeNode* right;

        friend KDTree<K,E,T,D>;

        KDTreeNode(const KDTreeNode& other)
        {
            (void)(other);
            throw -1;
        }

        KDTreeNode(KDTreeNode&& other)
        {
            (void)(other);
            throw -1;
        }
};

template <size_t K, size_t E, typename T, typename D>
class KDTree
{
public:

    KDTree() : m_built(false),m_treehead(NULL)  { };

    KDTree(KDTree&& other)  {
        m_allnodes = std::move(other.m_allnodes);
        m_built = other.m_built;
        m_treehead = other.m_treehead;
        other.m_allnodes.clear();
    };

    KDTree(const KDTree& other)  {
        (void)other;
        throw "Copy Constructor Not Yet Implemented";
    };

    ~KDTree()  {
        while(!m_allnodes.empty()) {
            delete m_allnodes.back() ;
            m_allnodes.pop_back();
        }
    };

    void insert(const std::vector<T>& pt, const std::vector<D>& data);

    void insert(size_t plen, const T* pt, size_t dlen, const D* data);

    void build();
    bool built() { return built; };

    void clear();

    const KDTreeNode<K,E,T,D>* nearest(const std::vector<T>& pt, double& dist) const;
    const KDTreeNode<K,E,T,D>* nearest(size_t len, const T* pt, double& dist) const;

    std::list<const KDTreeNode<K,E,T,D>*> withindist(const std::vector<T>& pt, double dist) const;
    std::list<const KDTreeNode<K,E,T,D>*> withindist(size_t len, const T* pt, double dist) const;

private:

    /**********
     * Data
     **********/
    // whether we have constructed the tree yet
    bool m_built;

    KDTreeNode<K,E,T,D>* m_treehead;
    std::vector<KDTreeNode<K,E,T,D>*> m_allnodes;

    /********************
     * Helper Functions
     ********************/
    const KDTreeNode<K,E,T,D>* nearest_help(size_t depth, KDTreeNode<K,E,T,D>* pos,
        const T* pt, double& distsq) const;

    std::list<const KDTreeNode<K,E,T,D>*> withindist_help(size_t depth,
        KDTreeNode<K,E,T,D>* pos, const T* pt, double distsq) const;

    KDTreeNode<K,E,T,D>* build_helper(
        typename std::vector<KDTreeNode<K,E,T,D>*>::iterator begin,
        typename std::vector<KDTreeNode<K,E,T,D>*>::iterator end,
        size_t depth);
};

}

#include "kdtree.txx"

#endif //KDTREE_H