Changeset 20:8f9a14fd63eb in rrlib_geometry


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

Readded support for different metrics using C++11 constucts

Files:
3 edited

Legend:

Unmodified
Added
Removed
  • space_partitioning/tKDTree.h

    r19 r20  
    147147  typedef geometry::tPoint<Tdimension, TElement> tPoint; 
    148148  typedef geometry::tBoundingBox<Tdimension, TElement> tBoundingBox; 
    149  
    150 //  /*! 
    151 //   * \brief An instantiation of std::binary_function for easier implementation of an own appropriate metric 
    152 //   */ 
    153 //  typedef std::binary_function<tCoordinates, tCoordinates, typename tCoordinates::tElement> tMetric; 
     149  typedef std::function < TElement(const tPoint &, const tPoint &) > tMetric; 
    154150 
    155151  /*! 
     
    185181     */ 
    186182    template <typename TIterator> 
    187     tNode(TIterator begin, TIterator end); 
     183    tNode(TIterator begin, TIterator end, tMetric metric); 
    188184 
    189185    /*! 
     
    263259    tPoint center_of_mass; 
    264260 
    265     size_t SelectSplitAxis() const; 
     261    size_t SelectSplitAxis(tMetric metric) const; 
    266262  }; 
    267263 
     
    288284  tKDTree(TIterator begin, TIterator end); 
    289285 
     286  template <typename TIterator> 
     287  tKDTree(TIterator begin, TIterator end, tMetric metric); 
     288 
    290289  /*! 
    291290   * \brief The dtor of tKDTree 
     
    300299  inline const tNode &Root() const; 
    301300 
    302 //  /*! 
    303 //   * \brief The default metric (Euklidian norm) used in this algorithm 
    304 //   */ 
    305 //  struct tDefaultMetric : public tMetric 
    306 //  { 
    307 //    inline const typename tMetric::result_type operator()(const typename tMetric::first_argument_type &x, const typename tMetric::second_argument_type &y) const 
    308 //    { 
    309 //      return (x - y).Length(); 
    310 //    } 
    311 //  }; 
    312  
    313301//---------------------------------------------------------------------- 
    314302// Private fields and methods 
  • space_partitioning/tKDTree.hpp

    r19 r20  
    6969template <typename TIterator> 
    7070tKDTree<Tdimension, TElement>::tKDTree(TIterator begin, TIterator end) 
    71     : root(new tNode(begin, end)) 
     71    : root(new tNode(begin, end, [](const tPoint &a, const tPoint &b) 
     72{ 
     73  return (a - b).Length(); 
     74})) 
     75{} 
     76 
     77template <size_t Tdimension, typename TElement> 
     78template <typename TIterator> 
     79tKDTree<Tdimension, TElement>::tKDTree(TIterator begin, TIterator end, tMetric metric) 
     80    : root(new tNode(begin, end, metric)) 
    7281{} 
    7382 
     
    96105template <size_t Tdimension, typename TElement> 
    97106template <typename TIterator> 
    98 tKDTree<Tdimension, TElement>::tNode::tNode(TIterator begin, TIterator end) 
     107tKDTree<Tdimension, TElement>::tNode::tNode(TIterator begin, TIterator end, tMetric metric) 
    99108    : bounding_box(begin, end), 
    100     split_axis(SelectSplitAxis()), 
     109    split_axis(SelectSplitAxis(metric)), 
    101110    split_value(0.5 *(this->bounding_box.Min()[this->split_axis] + this->bounding_box.Max()[this->split_axis])), 
    102111    left_child(0), 
     
    118127    if (split != begin && split != end) 
    119128    { 
    120       this->left_child = new tNode(begin, split); 
    121       this->right_child = new tNode(split, end); 
     129      this->left_child = new tNode(begin, split, metric); 
     130      this->right_child = new tNode(split, end, metric); 
    122131      assert(this->left_child && this->right_child); 
    123132    } 
     
    233242//---------------------------------------------------------------------- 
    234243template <size_t Tdimension, typename TElement> 
    235 size_t tKDTree<Tdimension, TElement>::tNode::SelectSplitAxis() const 
     244size_t tKDTree<Tdimension, TElement>::tNode::SelectSplitAxis(tMetric metric) const 
    236245{ 
    237246  tPoint sample_point; 
     
    241250  { 
    242251    sample_point[i] = this->bounding_box.Max()[i] - this->bounding_box.Min()[i]; 
    243     TElement width = (sample_point - tPoint::Zero()).Length(); 
     252    TElement width = metric(sample_point, tPoint::Zero()); 
    244253    sample_point[i] = 0; 
    245254    if (width > max_width) 
  • test/test_kd_tree.cpp

    r19 r20  
    7575// Implementation 
    7676//---------------------------------------------------------------------- 
     77 
     78struct tManhattanNorm 
     79{ 
     80  inline tElement operator()(const tPoint &a, const tPoint &b) const 
     81  { 
     82    return std::fabs(a.X() - b.X()) + std::fabs(a.Y() - b.Y()); 
     83  } 
     84}; 
     85 
     86int ManhattanNorm(const tPoint &a, const tPoint &b) 
     87{ 
     88  return std::fabs(a.X() - b.X()) + std::fabs(a.Y() - b.Y()); 
     89} 
     90 
     91auto manhattan_norm = [](const tPoint & a, const tPoint & b) 
     92{ 
     93  return std::fabs(a.X() - b.X()) + std::fabs(a.Y() - b.Y()); 
     94}; 
     95 
     96 
    7797 
    7898void DrawPoint(tWindow &window, const tPoint &point) 
     
    199219 
    200220  tKDTree kd_tree(points.begin(), points.end()); 
     221//  tKDTree kd_tree(points.begin(), points.end(), [](const tPoint &a, const tPoint &b){return (a - b).Length();}); 
     222//  tKDTree kd_tree(points.begin(), points.end(), tManhattanNorm()); 
     223//  tKDTree kd_tree(points.begin(), points.end(), ManhattanNorm); 
     224//  tKDTree kd_tree(points.begin(), points.end(), manhattan_norm); 
    201225 
    202226  for (unsigned int i = 0; i < 10; i++) 
Note: See TracChangeset for help on using the changeset viewer.