我正在从事一个个人项目,以在 C++ 中实现二维 kd-tree 构造算法。
我知道有些库已经这样做了,但我想获得 C++ 编程方面的经验
(如果你有个人项目要展示,这有助于简历)
输入:点数和点本身(可以从命令行读取输入)
我希望它在 O(n log n) 时间内运行,可以这样做吗,如果可以的话,有人可以提供一些伪代码来帮助我开始,在此先感谢。
我正在从事一个个人项目,以在 C++ 中实现二维 kd-tree 构造算法。
我知道有些库已经这样做了,但我想获得 C++ 编程方面的经验
(如果你有个人项目要展示,这有助于简历)
输入:点数和点本身(可以从命令行读取输入)
我希望它在 O(n log n) 时间内运行,可以这样做吗,如果可以的话,有人可以提供一些伪代码来帮助我开始,在此先感谢。
我最近一直在玩 kd-trees。这是一些未经测试的代码。kd-tree 构建分两个阶段完成;遍历点列表,O(n),并沿每个维度排序,O(nlogn)。所以,是的,您可以在 O(nlogn) 时间内构建 kd 树。
搜索树(假设您正在寻找最近的邻居),但变得更加棘手。我还没有找到任何易于理解的文档。
struct Node
{
int[2] point;
Node* left;
Node* right;
}
Node* createtreeRecursive (int** values /* int[2][len] */, int len, int dim = 2, int depth = 0)
{
// If empty, return
if (value <= 1) return null;
// Get axis to split along
int axis = depth % dim;
int** sorted = sortAlongDim (values, axis);
int mid = len / 2;
Node* curr = new Node ();
curr.point[0] = sorted [0][mid];
curr.point[1] = sorted [1][mid];
int** leftHalf = values;
int** rightHalf = &(values [mid]);
curr.left = createtreeRecursive (leftHalf, mid, dim, depth + 1);
curr.right = createtreeRecursive (rightHalf, len - mid, dim, depth + 1);
return curr;
}
int** sortAlongDim (int** values, int axis)