kd_tree.h

Go to the documentation of this file.

/*
 * Copyright (c) 2013-2015:  G-CSC, Goethe University Frankfurt
 * Author: Sebastian Reiter
 * 
 * This file is part of UG4.
 * 
 * UG4 is free software: you can redistribute it and/or modify it under the
 * terms of the GNU Lesser General Public License version 3 (as published by the
 * Free Software Foundation) with the following additional attribution
 * requirements (according to LGPL/GPL v3 §7):
 * 
 * (1) The following notice must be displayed in the Appropriate Legal Notices
 * of covered and combined works: "Based on UG4 (www.ug4.org/license)".
 * 
 * (2) The following notice must be displayed at a prominent place in the
 * terminal output of covered works: "Based on UG4 (www.ug4.org/license)".
 * 
 * (3) The following bibliography is recommended for citation and must be
 * preserved in all covered files:
 * "Reiter, S., Vogel, A., Heppner, I., Rupp, M., and Wittum, G. A massively
 *   parallel geometric multigrid solver on hierarchically distributed grids.
 *   Computing and visualization in science 16, 4 (2013), 151-164"
 * "Vogel, A., Reiter, S., Rupp, M., Nägel, A., and Wittum, G. UG4 -- a novel
 *   flexible software system for simulating pde based models on high performance
 *   computers. Computing and visualization in science 16, 4 (2013), 165-179"
 * 
 * This program 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 Lesser General Public License for more details.
 */
 
 
#ifndef __H__UG__kd_tree__
#define __H__UG__kd_tree__
 
namespace ug{
 
enum KDTreeSplitStrategy
{
  KDTSS_CIRCULAR,
  KDTSS_LARGEST
};
 
struct KDTreeDesc{
  KDTreeDesc() : dim(3), splitThreshold(16), strategy(KDTSS_LARGEST)  {}
  KDTreeDesc(int nDim, int nSplitThreshold, KDTreeSplitStrategy nStrategy) :
    dim(nDim),
    splitThreshold(nSplitThreshold),
    strategy(nStrategy) {}
 
  int dim;
  int splitThreshold;
  KDTreeSplitStrategy strategy;
};
 
template <class point_t, class data_t, class real_t = float>
class KDTree
{
  public:
    class Element{
      friend class KDTree;
      public:
        point_t   point;
        data_t    data;
 
      private:
        int nextElemInd;
    };
 
 
    void set_desc(const KDTreeDesc& desc);
 
    bool empty() const;
 
    size_t size() const;
 
 
    size_t num_delayed_elements() const;
 
 
    void add_element(const point_t& point, const data_t& data, bool delayInsertion = false);
 
 
    Element closest_element(const point_t& point) const;
 
 
    void closest_elements(vector<Element>& elemsOut, const point_t& point,
                size_t n) const;
 
 
    real_t estimate_balance_quality();
 
    void rebalance();
 
  private:
    struct Node{
      int     childNodeInds[2]; 
      int     firstElemInd; 
      int     lastElemInd; 
      int     numElements; 
      float   splitValue;
      int     splitDim;
    };
 
 
    void split_leaf_node(Node& node);
 
    int find_leaf_node(const point_t& point);
 
 
    KDTreeDesc        m_desc;
    std::vector<Node>   m_nodes;
    std::vector<Element>  m_elements;
    size_t          m_numDelayedElements;
};
 
}// end of namespace
 
#endif