Class naive_kd_tree

code/data-structures/kd_tree.test.cpp:2–59

template <int K>
struct naive_kd_tree {

  struct point {
    double coord[K];
    point() {}
    point(double c[K]) {
      for (int i = 0; i < K; i++)
        coord[i] = c[i];
    }

    double dist_to(const point &other) const {
      double sum = 0.0;
      for (int i = 0; i < K; i++)
        sum += pow(coord[i] - other.coord[i], 2.0);
      return sqrt(sum);
    }

    bool operator <(const point &other) const {
      for (int i = 0; i < K; i++)
        if (abs(coord[i] - other.coord[i]) > EPS)
          return coord[i] < other.coord[i];
      return false;
    }
  };

  set<point> pts;

  naive_kd_tree() { }
  naive_kd_tree(vector<point> _pts) {
    for (int i = 0; i < size(_pts); i++) {
      pts.insert(_pts[i]);
    }
  }

  bool contains(const point &p) {
    return pts.find(p) != pts.end();
  }

  void insert(const point &p) {
    pts.insert(p);
  }

  pair<point, bool> nearest_neighbour(const point &p, bool allow_same = true) {
    double mn = INFINITY;
    point res;
    bool found = false;
    for (typename set<point>::const_iterator it = pts.begin(); it != pts.end(); ++it) {
      double dist = p.dist_to(*it);
      if (abs(dist) < EPS && !allow_same) continue;
      if (dist < mn) {
        mn = dist;
        res = *it;
        found = true;
      }
    }
    return make_pair(res, found);
  }
};