Changeset 21:c6c1dda3d2e0 in rrlib_geometry


Ignore:
Timestamp:
09.01.2012 16:12:12 (8 years ago)
Author:
Tobias Föhst <foehst@…>
Branch:
default
Phase:
public
Message:

Some renaming and the default metric is now accessible via cDEFAULT_METRIC

Location:
space_partitioning
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • space_partitioning/tKDTree.h

    r20 r21  
    146146 
    147147  typedef geometry::tPoint<Tdimension, TElement> tPoint; 
    148   typedef geometry::tBoundingBox<Tdimension, TElement> tBoundingBox; 
    149148  typedef std::function < TElement(const tPoint &, const tPoint &) > tMetric; 
     149 
     150  static const tMetric cDEFAULT_METRIC; 
    150151 
    151152  /*! 
     
    168169  public: 
    169170 
     171    typedef geometry::tBoundingBox<Tdimension, TElement> tBoundingBox; 
     172 
    170173    /*! 
    171174     * \brief The ctor of tNode 
     
    176179     * as its own children until only single points are left. 
    177180     * 
    178      * \param begin    An indirect iterator to the begin of the data to manage 
    179      * \param end      An indirect iterator to the end of the data to manage 
    180      * \param metric   A functor that computes an appropriate metric 
     181     * \param points_begin   An indirect iterator to the begin of the data to manage 
     182     * \param points_end     An indirect iterator to the end of the data to manage 
     183     * \param metric         A functor that computes an appropriate metric 
    181184     */ 
    182185    template <typename TIterator> 
    183     tNode(TIterator begin, TIterator end, tMetric metric); 
     186    tNode(TIterator points_begin, TIterator points_end, tMetric metric); 
    184187 
    185188    /*! 
     
    217220 
    218221    /*! 
    219      * \brief Get the axis-aligned boungind box of the points underneath this node 
     222     * \brief Get the axis-aligned bounging box of the points underneath this node 
    220223     * 
    221224     * \return The maximum coordinates of this node 
     
    282285   */ 
    283286  template <typename TIterator> 
    284   tKDTree(TIterator begin, TIterator end); 
    285  
    286   template <typename TIterator> 
    287   tKDTree(TIterator begin, TIterator end, tMetric metric); 
     287  tKDTree(TIterator points_begin, TIterator points_end, tMetric metric = cDEFAULT_METRIC); 
     288// 
     289//  template <typename TIterator> 
     290//  tKDTree(TIterator begin, TIterator end, tMetric metric); 
    288291 
    289292  /*! 
  • space_partitioning/tKDTree.hpp

    r20 r21  
    5959//---------------------------------------------------------------------- 
    6060 
     61template <size_t Tdimension, typename TElement> 
     62const typename tKDTree<Tdimension, TElement>::tMetric tKDTree<Tdimension, TElement>::cDEFAULT_METRIC = [](const tPoint &a, const tPoint &b) 
     63{ 
     64  return (a - b).Length(); 
     65}; 
     66 
    6167//---------------------------------------------------------------------- 
    6268// Implementation 
     
    6874template <size_t Tdimension, typename TElement> 
    6975template <typename TIterator> 
    70 tKDTree<Tdimension, TElement>::tKDTree(TIterator begin, TIterator end) 
    71     : root(new tNode(begin, end, [](const tPoint &a, const tPoint &b) 
    72 { 
    73   return (a - b).Length(); 
    74 })) 
    75 {} 
    76  
    77 template <size_t Tdimension, typename TElement> 
    78 template <typename TIterator> 
    79 tKDTree<Tdimension, TElement>::tKDTree(TIterator begin, TIterator end, tMetric metric) 
    80     : root(new tNode(begin, end, metric)) 
     76tKDTree<Tdimension, TElement>::tKDTree(TIterator begin_points, TIterator end_points, tMetric metric) 
     77    : root(new tNode(begin_points, end_points, metric)) 
    8178{} 
    8279 
     
    105102template <size_t Tdimension, typename TElement> 
    106103template <typename TIterator> 
    107 tKDTree<Tdimension, TElement>::tNode::tNode(TIterator begin, TIterator end, tMetric metric) 
    108     : bounding_box(begin, end), 
     104tKDTree<Tdimension, TElement>::tNode::tNode(TIterator points_begin, TIterator points_end, tMetric metric) 
     105    : bounding_box(points_begin, points_end), 
    109106    split_axis(SelectSplitAxis(metric)), 
    110107    split_value(0.5 *(this->bounding_box.Min()[this->split_axis] + this->bounding_box.Max()[this->split_axis])), 
    111108    left_child(0), 
    112109    right_child(0), 
    113     number_of_points(std::distance(begin, end)) 
     110    number_of_points(std::distance(points_begin, points_end)) 
    114111{ 
    115112  if (this->number_of_points > 1) 
    116113  { 
    117     std::sort(begin, end, 
    118               [this](const tPoint &a, const tPoint &b) 
     114    std::sort(points_begin, points_end, [this](const tPoint &a, const tPoint &b) 
    119115    { 
    120116      return a[this->split_axis] < b[this->split_axis]; 
    121117    }); 
    122     TIterator split = begin; 
    123     while (split != end && (*split)[this->split_axis] <= this->split_value) 
     118    TIterator split = points_begin; 
     119    while (split != points_end && (*split)[this->split_axis] <= this->split_value) 
    124120    { 
    125121      ++split; 
    126122    } 
    127     if (split != begin && split != end) 
    128     { 
    129       this->left_child = new tNode(begin, split, metric); 
    130       this->right_child = new tNode(split, end, metric); 
     123    if (split != points_begin && split != points_end) 
     124    { 
     125      this->left_child = new tNode(points_begin, split, metric); 
     126      this->right_child = new tNode(split, points_end, metric); 
    131127      assert(this->left_child && this->right_child); 
    132128    } 
     
    137133  { 
    138134    // there may be more than one point in a leave 
    139     for (auto it = begin; it != end; it++) 
     135    for (auto it = points_begin; it != points_end; it++) 
    140136    { 
    141137      for (size_t i = 0; i < Tdimension; i++) 
     
    204200//---------------------------------------------------------------------- 
    205201template <size_t Tdimension, typename TElement> 
    206 const typename tKDTree<Tdimension, TElement>::tBoundingBox &tKDTree<Tdimension, TElement>::tNode::BoundingBox() const 
     202const typename tKDTree<Tdimension, TElement>::tNode::tBoundingBox &tKDTree<Tdimension, TElement>::tNode::BoundingBox() const 
    207203{ 
    208204  return this->bounding_box; 
Note: See TracChangeset for help on using the changeset viewer.