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

dkd.hpp

Go to the documentation of this file.

#ifndef KD_TREE_HPP
#define KD_TREE_HPP

#include <iostream>
#include <algorithm>

#include <boost/array.hpp>
#include "cgl.hpp"


namespace inplaceds
{
        
        #define STATIC_KD_TREE_CUTOFF  16
        
        template <class RandomAccessIterator, class AxisAlignedGeometry>
        void
        build_kdtree(RandomAccessIterator first, RandomAccessIterator last,
                                 AxisAlignedGeometry geom,
                                 size_t dimensions)
        {
          build_kdtree(first, last, geom, dimensions, 1);
        }
        
        template <class RandomAccessIterator, class AxisAlignedGeometry>
        void
        build_kdtree(RandomAccessIterator first, RandomAccessIterator last,
                                 AxisAlignedGeometry geom,
                                 size_t dimensions,
                                 size_t pointDimension)
        {

          //stop recursing if minimum size is reached
          if(last - first < STATIC_KD_TREE_CUTOFF)
          {
            return;
          }
                
          RandomAccessIterator mid = (first + (last-first+1)/2);
          RandomAccessIterator Lmid = (first + (mid-first+1)/2);
          RandomAccessIterator Rmid = (mid + (last-mid+1)/2);
        
          if(dimensions == 1)
          {     
            std::partial_sort (first, mid, last, geom.less_nth_object(pointDimension)) ;
          }
          else
          {
            std::partial_sort(first, mid, last, geom.less_nth_object(pointDimension) );
            build_kdtree(first, mid, geom, dimensions-1, pointDimension+1);
            build_kdtree(mid+1, last, geom, dimensions-1, pointDimension+1);    
          }
                
          //----recursive calls----
        
          //recursively partition Lbot
          build_kdtree(first, Lmid, geom, dimensions, pointDimension);
        
          //recursively partition Ltop
          build_kdtree(Lmid+1, mid, geom, dimensions, pointDimension);
        
          //recursively partition Rbot
          build_kdtree(mid+1, Rmid, geom, dimensions, pointDimension);
        
          //recursively partition Rtop
          build_kdtree(Rmid+1, last, geom, dimensions, pointDimension);
        
        }
        
        #undef STATIC_KD_TREE_CUTOFF
        
}       
#endif

---

Code Documentation generated Using Doxygen

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