Space-efficient geometric algorithms and data structures By Ilya Katz and Hervé Brönnimann

kd_tree.hpp

Go to the documentation of this file.

/*
 * Copyright © Ilya Katz and Herve Bronnimann, 2005. 
 */

#ifndef D_KD_TREE
#define D_KD_TREE

#include <vector>
#include "dynamic_kd_tree.hpp"

namespace inplaceds
{


        template <class _Point,
                          class _AxisAlignedGeometry,
                          class _Sequence = std::vector<_Point> >
        class kd_tree
        {
                
                public:
                
                typedef typename _Sequence::value_type                  point_type;
                typedef typename _Sequence::iterator                    iterator;
                typedef typename _Sequence::const_iterator      const_iterator;
                typedef  _AxisAlignedGeometry                                   geometry;
                typedef  _Sequence                                                              sequence;
        
                protected:
                _Sequence _points;
                _AxisAlignedGeometry geom;
                
                public:
                
                
                kd_tree(){};
                
                template<class InputIterator>  
                kd_tree(InputIterator first, InputIterator last):_points(distance(first,last))
                {       
                        std::copy(first, last, this->_points.begin());
                        build_dynamic_kdtree(this->_points.begin(), this->_points.end(), geom);
                }
                
                kd_tree(const _Sequence& lhs):_points(lhs.size())
                {               
                        std::copy(lhs.begin(), lhs.end(), this->_points.begin());
                        build_dynamic_kdtree(this->_points.begin(), this->_points.end(), this->geom);
                }
                
                kd_tree(const kd_tree& lhs):_points(lhs.points.size())
                {
                        std::copy(lhs.points._begin(), lhs._points.end(), this->_points.begin());
                }
                
                void insert(point_type p)
                {
                        this->_points.insert(this->_points.end(), p);
                        insert_dynamic_kdtree(this->_points.begin(), this->_points.end(), this->geom);
                }
                
                void remove(iterator pos)
                {
                        remove_dynamic_kdtree(this->_points.begin(), pos, this->_points.end(), this->geom);
                        iterator it=this->_points.end();
                        this->_points.erase(--it);
                }
                
                const_iterator find(point_type p) const
                {
                        for(iterator it = this->_points.begin(); it!=this->_points.end(); ++it)
                        {
                                if(*it==p)
                                {
                                        return it;
                                }
                        }
                        
                        return this->_points.end();
                }
                
                        
                const_iterator npos() const
                {
                        return (this->_points).end();
                }
                
                template <class Box>
                iterator box_query( Box Q, sequence& result) const
                {
                        
                        window_query_dynamic_kdtree(this->_points.begin(), this->_points.end(), this->geom,
                                                                                Q, std::back_inserter(result));
                        return result.begin();
                }
                
                template <class Halfplane>
                iterator halfplane_query(Halfplane Q, sequence& result) const
                {
                        
                        halfplane_query_dynamic_kdtree(this->_points.begin(), this->_points.end(), this->geom,
                                                                                Q, std::back_inserter(result));
                        return result.begin();
                }
        
                template <class Comp>
                iterator query(Comp Q, sequence& result) const
                {
                        for(iterator it=this->_points.begin(); it!=this->_points.end(); ++it)
                        {
                                if(Q(*it))
                                {
                                        result.insert(result.end(), *it);       
                                }
                        }
                        return result.begin();
                }
                
                const_iterator points() const
                {
                        return (this->_points).begin();
                }
                
        };
        
}//namespaces



#endif

---

Code Documentation generated Using Doxygen

Copyright © Ilya Katz and Hervé Brönnimann, 2005, 2006.