daily pastebin goal
23%
SHARE
TWEET

constructor working

a guest Mar 24th, 2019 71 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /**
  2.  * @file kdtree.cpp
  3.  * Implementation of KDTree class.
  4.  */
  5.  
  6. #include <utility>
  7. #include <algorithm>
  8. #include <iostream>
  9.  
  10. using namespace std;
  11.  
  12. template <int Dim>
  13. bool KDTree<Dim>::smallerDimVal(const Point<Dim>& first,                    //probably working
  14.                                 const Point<Dim>& second, int curDim) const
  15. {
  16.     /**
  17.      * @todo Implement this function!
  18.      */
  19.     if (first[curDim] < second[curDim]) {
  20.       return true;
  21.     }
  22.     else if (first[curDim] > second[curDim]) {
  23.       return false;
  24.     }
  25.     return (first < second);
  26. }
  27.  
  28. template <int Dim>
  29. bool KDTree<Dim>::shouldReplace(const Point<Dim>& target,               //probably working
  30.                                 const Point<Dim>& currentBest,
  31.                                 const Point<Dim>& potential) const
  32. {
  33.     /**
  34.      * @todo Implement this function!
  35.      */
  36.     double curr_dist = 0;
  37.     double pot_dist = 0;
  38.     for (int i = 0; i < Dim; i++) {
  39.       curr_dist += pow(target[i] - currentBest[i], 2);
  40.       pot_dist += pow(target[i] - potential[i], 2);
  41.     }
  42.     if (pot_dist < curr_dist) {
  43.       return true;
  44.     }
  45.     else if (curr_dist < pot_dist) {
  46.       return false;
  47.     }
  48.     return (potential < currentBest);
  49. }
  50.  
  51. template <int Dim>
  52. KDTree<Dim>::KDTree(const vector<Point<Dim>>& newPoints)          //probably working
  53. {
  54.     /**
  55.      * @todo Implement this function!
  56.      */
  57.     vector<Point<Dim>> sorted(newPoints);
  58.     root = constructTree(0, sorted.size()-1, 0, sorted);
  59. }
  60.  
  61. template <int Dim>
  62. typename KDTree<Dim>::KDTreeNode * KDTree<Dim>::constructTree(int l, int r, int dim, vector<Point<Dim>>& sorted_points) { //probably working
  63.     KDTreeNode * newNode = NULL;
  64.    
  65.     if (l > r) {
  66.       return newNode;
  67.     }
  68.     int median = (l+r)/2;
  69.     Point<Dim> point_holder = quickSelect(l, r, median, dim%Dim, sorted_points);
  70.    
  71.     newNode = new KDTreeNode(point_holder);
  72.     newNode->left = constructTree(l, median-1, (dim+1)%Dim, sorted_points);
  73.     newNode->right = constructTree(median+1, r, (dim+1)%Dim, sorted_points);
  74.    
  75.     //returns head of current subtree.
  76.     return newNode;
  77. }
  78.  
  79. template <int Dim>
  80. Point<Dim> KDTree<Dim>::quickSelect(int l, int r, int k, int dim, vector<Point<Dim>>& sorted_points) {  
  81.     if (l == r) {
  82.       return sorted_points[l];
  83.     }
  84.  
  85.     int piv_idx = (l+r)/2;
  86.     piv_idx = partition(sorted_points, l, r, piv_idx, dim);
  87.  
  88.     if (k < piv_idx) {
  89.       return quickSelect(l, piv_idx-1, k, dim, sorted_points);
  90.     }
  91.     else if (k == piv_idx) {
  92.       return sorted_points[k];
  93.     }
  94.     else {
  95.       return quickSelect(piv_idx+1, r, k, dim, sorted_points);
  96.     }
  97. }
  98.  
  99. template <int Dim>
  100. int KDTree<Dim>::partition(vector<Point<Dim>>& sorted_points, int l, int r, int piv_idx, int dim) {
  101.  
  102.   Point<Dim> pivValue = sorted_points[piv_idx];
  103.   iter_swap(sorted_points.begin() + piv_idx, sorted_points.begin() + r);
  104.  
  105.   int str_idx = l;
  106.   for (int i = l; i < r; i++) {
  107.     if (smallerDimVal(sorted_points[i], pivValue, dim)) {
  108.       iter_swap(sorted_points.begin() + str_idx, sorted_points.begin() + i);
  109.       str_idx++;
  110.     }
  111.   }
  112.  
  113.   iter_swap(sorted_points.begin() + r, sorted_points.begin() + str_idx);
  114.   return str_idx;
  115. }
  116.  
  117. template <int Dim>
  118. KDTree<Dim>::KDTree(const KDTree<Dim>& other) { //maybe working??
  119.     /**
  120.      * @todo Implement this function!
  121.      */
  122.     root = _copy(other);
  123. }
  124.  
  125. template <int Dim>
  126. const KDTree<Dim>& KDTree<Dim>::operator=(const KDTree<Dim>& rhs) { //maybe working??
  127.     /**
  128.      * @todo Implement this function!
  129.      */
  130.     if (&rhs != this) {
  131.         _destroy(root);
  132.         root = _copy(rhs);
  133.     }
  134.     return *this;
  135. }
  136.  
  137. template <int Dim>
  138. KDTree<Dim>::~KDTree() {
  139.     /**
  140.      * @todo Implement this function!
  141.      */
  142.  
  143.     _destroy(root);
  144. }
  145.  
  146. template <int Dim>
  147. Point<Dim> KDTree<Dim>::findNearestNeighbor(const Point<Dim>& query) const
  148. {
  149.     /**
  150.      * @todo Implement this function!
  151.      */
  152.     Point<Dim> currentBest;
  153.     double distance = 0;
  154.     //bool firstSide = true; not sure about this one, i'll uncomment if needed.
  155.     //findNearestNeighborHelper(root, query, currentBest, 0, distance);
  156.     return currentBest;
  157. }
  158.  
  159. template <int Dim>
  160. typename KDTree<Dim>::KDTreeNode * KDTree<Dim>::_copy(const KDTree & other) { //maybe working??
  161.     if (other.root == NULL ) {
  162.       return NULL;
  163.     }
  164.  
  165.     root = new KDTreeNode(other.root.point);
  166.     root->left = _copy(other.root.left);
  167.     root->right = _copy(other.root.right);
  168.     return root;
  169. }
  170.  
  171. template <int Dim>
  172. void KDTree<Dim>::_destroy(KDTreeNode * root) { //definitely not working :(
  173.     if (root == NULL)  {
  174.       return;  
  175.     }
  176.     _destroy(root->left);  
  177.     _destroy(root->right);  
  178.     delete root;
  179.     root = NULL;
  180. }
  181.  
  182. template <int Dim>
  183. double KDTree<Dim>::get_distance(const Point<Dim>& first, const Point<Dim>& second) const {
  184.   double distance = 0;
  185.  
  186.   for (int i=0; i<Dim; i++) {
  187.     distance += pow((first[i] - second[i]), 2);
  188.   }
  189.  
  190.   return distance;
  191. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top