查找坐标中值以构建 kd 树（2D）-C++

Question

我有一个二维问题中的最近邻问题，我发现 kd 树是最好的解决方案。我找不到适合我正在使用的结构的现成实现，所以我决定创建自己的。

我使用的结构是：

struct Point{
  int id;
  double x;
  double y;
};

我有将近100000个点，我的问题是：每次要划分我的点时如何进行寻找中点，以及如何同时定义左右划分？

另一个问题是：是否有更有效的方法进行？（耗时越少越好）。

Answer 1

How to compute median? Is there a more efficient way to proceed?

这两个问题我都会给出一个答案：你可以使用std::nth_element，像这样：

std::vector<float> v;                                   // data vector (global)
bool myfunction (int i,int j) { return (v[i]<v[j]); } 

int find_median(std::vector<int> &v_i)
{
    size_t n = v_i.size() / 2;
    nth_element(v_i.begin(), v_i.begin()+n, v_i.end(), myfunction);
    return v_i[n];
}

您也可以查看我的question了解更多。

how to define the left and right partitions in the same time?

每个小于中位数的值都属于左分区，而每个大于中位数的值都属于右分区。

由您决定与中位数相等的值的去向。只需选择左或右并记住您的决定。

查找坐标中值以构建 kd 树（2D）-C++

Find median of coordinates to build kd tree (2D) - C++

c++

kdtree

nearest-neighbor

median