代码之家 › 专栏 › 技术社区 › berserker

找到坐标中值以构建kd树(2D)-C++

kdtree nearest-neighbor median c++

2

berserker · 技术社区 · 10 年前

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

我使用的结构是:

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

我有将近10万个点,我的问题是:每次我想划分点时,如何继续找到中间点,以及如何同时定义左分区和右分区?

另一个问题是:是否有更有效的方法来进行?(可能花费的时间越少)。

1 回复 | 直到 10 年前

1

0

Community Mohan Dere 8 年前

如何计算中值?有没有更有效的方法?

我将对这两个问题给出一个答案:您可以使用 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 了解更多信息。

如何同时定义左右分区?

小于中间值的每个值都属于左侧分区,而大于中间值的所有值都属于右侧分区。

这取决于你来决定中值的平均值会去哪里。只需向左或向右选择并记住您的决定。