kdtree.H

/*
 * This file is part of the "Archon" framework.
 * (http://files3d.sourceforge.net)
 *
 * Copyright © 2002 by Kristian Spangsege and Brian Kristiansen.
 *
 * Permission to use, copy, modify, and distribute this software and
 * its documentation under the terms of the GNU General Public License is
 * hereby granted. No representations are made about the suitability of
 * this software for any purpose. It is provided "as is" without express
 * or implied warranty. See the GNU General Public License
 * (http://www.gnu.org/copyleft/gpl.html) for more details.
 *
 * The characters in this file are ISO8859-1 encoded.
 *
 * The documentation in this file is in "Doxygen" style
 * (http://www.doxygen.org).
 */

#ifndef ARCHON_UTILITIES_KDTREE_H
#define ARCHON_UTILITIES_KDTREE_H

#include <vector>
#include <algorithm>
#include <queue>

#include <archon/math/geometry.H>

namespace Archon
{
  namespace Utilities
  {
    struct KDTree
    {
      struct Element
      {
        virtual Math::Vector3 getPosition() const = 0;

      protected:
        virtual ~Element() {}
      };

      void clear() { elements.clear(); }
      void insert(Element *element) { elements.push_back(element); }
      void balanceTree() { buildSubKDTree(0, elements.size()-1, 0); }

      void findNearest(const Math::Vector3 &position,
                       unsigned count, double max_radius, double &radius,
                       std::vector<const Element *> &_elements);

    private:
      class QElement
      {
      public:
        const Element *element;
        double dist; // distance to point
      };

      double radius;

      void buildSubKDTree(int start, int end, int axis);
      void findSubNearest(const Math::Vector3 &position, unsigned count, int start, int end, int axis);
      void findSubNearestNew(const Math::Vector3 &position, unsigned count, int start, int end, int axis);

      struct sort_func: public std::binary_function<Element, Element, bool>
      {
        int sort_axis;
        sort_func(int axis) : sort_axis(axis) {}
        bool operator()(const Element *a, const Element *b)
        {
          return a->getPosition()[sort_axis] < b->getPosition()[sort_axis];
        }
      };

      struct priority_func: public std::binary_function<QElement, QElement, bool>
      {
        bool operator()(QElement *a, QElement *b) { return a->dist < b->dist; }
      };

      std::priority_queue<QElement *, std::vector<QElement *>, priority_func> nearest_queue;

      std::vector<const Element *> elements;
    };
  }
}

#endif // ARCHON_UTILITIES_KDTREE_H

---