- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
你好,有人用 C++ 迭代实现了 Kd-Tree 吗?我试过了,但是当节点数为奇数时它失败了。到目前为止,这是我的代码。我指的是 http://ldots.org/kdtree/#buildingAkDTree网站了解详情。
#include <stdio.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <iomanip>
struct Point {
double pt[2];
int id;
};
typedef std::vector<Point> TPointVector;
struct KdNode {
double point[2];
int id;
double desc;
bool leaf;
KdNode *left;
KdNode *right;
KdNode *parent;
KdNode(KdNode *parent_):parent(parent_),leaf(false){}
KdNode(KdNode *parent_,TPointVector::iterator itr, int depth, TPointVector &pv);
KdNode(KdNode *t, TPointVector &pv);
};
KdNode::KdNode(KdNode *parent_,TPointVector::iterator itr, int depth, TPointVector &pv) {
parent = parent_ ;
left = 0;
right = 0;
desc = itr->pt[depth % 2 ];
leaf = false;
}
KdNode::KdNode(KdNode *t, TPointVector &pv) {
id = pv[0].id;
point[0] = pv[0].pt[0];
point[1] = pv[0].pt[1];
left = 0;
right = 0;
parent = t;
leaf = true;
}
KdNode *pRoot = 0;
struct ComparePoints {
int cord;
ComparePoints(int cord_) : cord(cord_ % 2) { };
bool operator()(const Point& lhs, const Point& rhs) const {
return lhs.pt[cord] < rhs.pt[cord];
}
};
void buildLeftTree(std::stack<TPointVector > &stackL) {
KdNode *pCurrent = pRoot;
KdNode **pNode = &(pCurrent->left);
int depth = 0;
bool changeDirection = false;
while (! stackL.empty()) {
TPointVector pv = stackL.top();
stackL.pop();
if ( pv.size() != 1 ) {
std::sort(pv.begin(), pv.end(), ComparePoints(++depth));
*pNode = new KdNode(pCurrent, pv.begin() + pv.size()/2, depth, pv);
TPointVector lvp,rvp;
std::size_t median = pv.size() / 2;
std::copy(pv.begin(), pv.begin() + median, std::back_inserter(lvp));
std::copy(pv.begin() + median, pv.end(), std::back_inserter(rvp));
stackL.push(rvp);
stackL.push(lvp);
if ( changeDirection ) {
pCurrent = pCurrent->right;
changeDirection = false;
} else {
pCurrent = pCurrent->left;
}
pNode = &(pCurrent->left);
} else {
KdNode **pNodeLeft = &(pCurrent->left);
*pNodeLeft = new KdNode(pCurrent, pv);
pv = stackL.top();
stackL.pop();
KdNode **pNodeRight = &(pCurrent->right);
*pNodeRight = new KdNode(pCurrent,pv);
pCurrent = pCurrent->parent;
pNode = &(pCurrent->right);
changeDirection = true;
depth--;
}
}
}
void buildRightTree(std::stack<TPointVector > &stackR) {
KdNode *pCurrent = pRoot;
KdNode **pNode = &(pCurrent->right);
int depth = 0;
bool changeDirection = true;
while (! stackR.empty()) {
TPointVector pv = stackR.top();
stackR.pop();
if ( pv.size() != 1 ) {
std::sort(pv.begin(), pv.end(), ComparePoints(++depth));
*pNode = new KdNode(pCurrent, pv.begin() + pv.size()/2, depth, pv);
TPointVector lvp,rvp;
std::size_t median = pv.size() / 2;
std::copy(pv.begin(), pv.begin() + median, std::back_inserter(lvp));
std::copy(pv.begin() + median, pv.end(), std::back_inserter(rvp));
stackR.push(rvp);
stackR.push(lvp);
if ( changeDirection ) {
pCurrent = pCurrent->right;
changeDirection = false;
} else {
pCurrent = pCurrent->left;
}
pNode = &(pCurrent->left);
} else {
KdNode **pNodeLeft = &(pCurrent->left);
*pNodeLeft = new KdNode(pCurrent, pv);
pv = stackR.top();
stackR.pop();
KdNode **pNodeRight = &(pCurrent->right);
*pNodeRight = new KdNode(pCurrent,pv);
pCurrent = pCurrent->parent;
pNode = &(pCurrent->right);
depth--;
changeDirection = true;
}
}
}
void constructKD(TPointVector &pv) {
int depth = 0;
std::sort(pv.begin(), pv.end(), ComparePoints(depth));
pRoot = new KdNode(0);
pRoot->desc = ( pv.begin() + pv.size()/2)->pt[0];
pRoot->left = 0;
pRoot->right = 0;
TPointVector lvp, rvp;
std::copy(pv.begin(), pv.begin() + pv.size()/2, std::back_inserter(lvp));
std::copy(pv.begin() + pv.size()/2, pv.end(), std::back_inserter(rvp));
std::stack<TPointVector > stackL, stackR;
stackL.push(lvp);
stackR.push(rvp);
buildLeftTree(stackL);
buildRightTree(stackR);
}
void readPoints(const char* fileName, TPointVector& points) {
std::ifstream input(fileName);
if ( input.peek() != EOF ) {
while(!input.eof()) {
int id = 0;
double x_cord, y_cord;
input >> id >> x_cord >> y_cord;
Point t ;
t.pt[0] = x_cord;
t.pt[1] = y_cord;
t.id = id;
points.push_back(t);
}
input.close();
}
}
void _printLevelWise(KdNode *node, std::queue<KdNode *> Q) {
int depth = 0;
while ( ! Q.empty()) {
KdNode *qNode = Q.front();Q.pop();
if ( qNode->leaf ) {
std::cout << "[" << qNode->id << "]" << std::setprecision (25) << "(" << qNode->point[0] << "," << qNode->point[1] << ")" << std::endl;
} else {
std::cout << std::setprecision (25) << qNode->desc << std::endl;
}
if (qNode->left != 0)
Q.push(qNode->left);
if (qNode->right != 0)
Q.push(qNode->right);
}
}
void PrintLevelWise(KdNode *node) {
std::queue<KdNode *> Q;
Q.push(node);
_printLevelWise(node, Q);
}
int main ( int argc, char **argv ) {
if ( argc <= 1 ) {
return 0;
}
TPointVector points;
readPoints(argv[1], points);
for ( TPointVector::iterator itr = points.begin(); itr != points.end(); ++itr) {
std::cout << "(" << itr->pt[0] << "," << itr->pt[1] << ")" << std::endl;
}
if ( points.size() == 0 )
return 0;
constructKD(points);
PrintLevelWise(pRoot);
std::cout << "Construction of KD Tree Done " << std::endl;
}
失败的示例输入:
1 6 1
2 5 5
3 9 6
4 3 6
5 4 9
适用于此的示例输入:
1 6 1
2 5 5
3 9 6
4 3 6
5 4 9
6 4 0
7 7 9
8 2 9
最佳答案
buildLeftTree
和 buildRightTree
中的 else
不处理右子树上节点数为奇数的情况。在您的 5 点示例中,buildRightTree
中的 else
案例以 stackR
上的三个点结束,第一个用于 left
节点,第二个它默默地分配给 right
节点,就好像它是唯一的节点一样。
这是由于您选择的中间值,它使用的标准与您引用的网站上列出的标准不同。
std::size_t median = pv.size() / 2; // degenerates in cases where size() is odd
您的选择标准应该基于中值 x 或 y 值,并根据该标准(不假定任何给定大小)使用子列表。
关于c++ - Kd 树迭代实现(C++),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6307356/
假设您有一个对象列表,每个对象都需要计算距离它最近的对象以进行拍摄。这个对象有一个 x 和一个 y 值。物体也在移动。 kd树还有用吗?我不确定,因为如果物体在移动,你必须继续创建这个 kd 树。 我
我正在查看 KD 树的维基百科页面。例如,我在 python 中实现了用于构建列出的 kd 树的算法。 但是,使用 KD 树进行 KNN 搜索的算法会切换语言并且并不完全清楚。英文解释开始有意义,但它
Kd 算法首先通过划分基元数组(三角形、球体等)来创建根 BSP 节点,以便创建两个新数组(左基元和右基元),用于创建其两个基元子树。 左基元和右基元是通过将给定基元数组划分为两个数组来计算的。通过取
我(尝试)在Processing/Java中实现KD树,并遵循我在数十篇文章和维基百科文章中看到的逻辑,但我一定做错了什么,因为输出如下所示: 而不是这个: 显然有些东西不对劲,因为节点是重复的,而且
我有以下路径数据: id1 p1 p2 0 1 7.935 5.103 1 1 7.93
我正在阅读 C 中的 kd 树实现。这是其中的一些部分。问题出在 findmedian 函数中。我不明白 的实现 *md = start +(end-start)/2; ...... -> 其他不相关
给定一组数据点,kdtree是在它们之上创建的,但是这个 kdtree 是唯一的吗? 最佳答案 这似乎取决于您构建树的方式。维基百科文章提到中点的选择如何影响生成的树是否平衡。如果选择不同的点,那么树
警告:相当长的问题,也许太长了。如果是这样,我深表歉意。 我正在开发一个涉及 kd 树的最近邻搜索的程序(在本例中,它是一棵具有 3961 个独立点的 11 维树)。我们才刚刚了解它们,虽然我很好地掌
我目前正在尝试构建二维(纬度和经度)的 KD 树以查询最近的坐标。我将坐标(ID、纬度、经度)推送到一个 vector 中,并将该 vector 传递到我的 KD-Tree 的构造函数中。 但是当我在
我正在尝试为我的 C++ (DirectX) 项目实现一个 kd-tree 以加速我的碰撞检测。我的实现是一个非常原始的递归函数。第 nth_element 似乎工作正常(如果我将其注释掉,则只有 1
我为两组点构建了 kd 树,以便找到两组点之间最接近的双色配对: kd 树存储为 python 字典,可以在下面的代码中找到,并传递给一个函数('closest'),该函数旨在同时递归地分析两棵树以找
我正在尝试基于递归构建一个二维树。我可以将算法总结如下: > ALGORITHM BuildKDTree(P,depth) > 1. if P contains only one po
我想从平衡的 KD 树中删除一个元素,并且树在不重建整棵树的情况下保持平衡。这有可能在不重建整棵树的情况下平衡树吗?如果是那么怎么办? 最佳答案 对于标准的 k-d 树,您可以删除项目但没有重新平衡,
所以我们有一个无限的 3d 世界,我们需要查询最近的点。然而我们的点有标识符并且一直在移动。支持数据点的 KDtree\Octree 之类的数据结构是什么。连续移动并且在搜索+更新方面不会比 3d 情
你好,有人用 C++ 迭代实现了 Kd-Tree 吗?我试过了,但是当节点数为奇数时它失败了。到目前为止,这是我的代码。我指的是 http://ldots.org/kdtree/#buildingAk
我想扩展一个 kd-tree (2D) 类,以便能够删除节点(点)。这种移除应该在不必重建树的大部分的情况下进行。这些slides中描述的算法,在幻灯片 13 上似乎是我所追求的。但是,我无法理解幻灯
普通的kd-tree是通过递归地将超平面分成两半来构建的。并且用一个查询点做范围搜索,它只会搜索一小串点(对数)而不是所有(线性)。 我想知道 kd 树可以用点积构建吗? 例如,b 是一个 3d 向量
按照目前的情况,这个问题不适合我们的问答形式。我们希望答案得到事实、引用或专业知识的支持,但这个问题可能会引发辩论、争论、投票或扩展讨论。如果您觉得这个问题可以改进并可能重新打开,visit the
我刚刚完成了一个 kd-tree 的实现用于进行快速最近邻搜索。除了 Euclidean distance 之外,我有兴趣使用不同的距离指标。 .我对 kd-tree 的理解是,如果度量是非欧几里德的
我使用了 kd-tree algoritham 和 make tree。 但是我发现树不平衡所以我的问题是如果我们使用 kd-tree algoritham 那棵树总是平衡的如果不是那么我们怎样才能使
我是一名优秀的程序员,十分优秀!