kd树迭代实现（C ++） [英] Kd Tree Iterative implementation ( C++ )
本文介绍了kd树迭代实现（C ++）的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
您好请问谁有迭代实现kd树在C ++中的。 我试过，但它失败时的节点数都是奇数。 这是我的code为止。我指 http://ldots.org/kdtree/#buildingAkDTree 网站了解详细信息。
的#include＆LT; stdio.h中＆GT;
＃包括＆LT;的iostream＆GT;
＃包括＆LT; fstream的＆GT;
＃包括＆LT;载体＆GT;
＃包括＆LT;算法＆GT;
＃包括＆LT;栈＆GT;
＃包括＆LT;排队＆GT;
＃包括＆LT;了iomanip＆GT;
结构点{
双角[2];
INT ID;
};
类型定义的std ::矢量＆lt;点和GT; TPointVector;
结构KdNode {
双点[2];
INT ID;
双递减;
布尔叶;
KdNode *左;
KdNode *权利;
KdNode *父母;
KdNode（KdNode *父_）：父（母_），叶（假）{}
KdNode（KdNode * PARENT_，TPointVector：迭代ITR，INT深度，TPointVector和放大器; PV）;
KdNode（KdNode * T，TPointVector和放大器; PV）;
};
KdNode :: KdNode（KdNode * PARENT_，TPointVector：迭代ITR，INT深度，TPointVector和放大器; PV）{
父= PARENT_;
左边= 0;
右= 0;
DESC = itr-＆GT; PT [深度％2]。
叶= FALSE;
}
KdNode :: KdNode（KdNode * T，TPointVector和放大器; PV）{
ID = PV [0] .ID;
点[0] = PV [0] .PT [0];
点[1] = PV [0] .PT [1];
左边= 0;
右= 0;
父= T;
叶= TRUE;
}
KdNode * PROOT = 0;
结构ComparePoints {
INT线;
ComparePoints（INT cord_）：电源线（cord_％2）{};
布尔运算符（）（常量点和放大器; LHS，常量点和放大器; RHS）const的{
返回lhs.pt [线] LT; rhs.pt [线]。
}
};
无效buildLeftTree（性病::栈＆LT; TPointVector＆GT;＆安培; stackL）{
KdNode * pCurrent = PROOT;
KdNode ** pNode =及（pCurrent-＆GT;左）;
INT深度= 0;
布尔changeDirection = FALSE;
而（！stackL.empty（））{
TPointVector PV = stackL.top（）;
stackL.pop（）;
如果（pv.size（）！= 1）{
性病::排序（pv.begin（），pv.end（），ComparePoints（++深度））;
* pNode =新KdNode（pCurrent，pv.begin（）+ pv.size（）/ 2，深度，PV）;
TPointVector LVP，RVP;
的std ::为size_t位数= pv.size（）/ 2;
性病::复制（pv.begin（），pv.begin（）+中位数的std :: back_inserter（LVP））;
性病::复制（pv.begin（）+中位数，pv.end（），性病:: back_inserter（RVP））;
stackL.push（RVP）;
stackL.push（LVP）;
如果（changeDirection）{
pCurrent = pCurrent-＆GT;权利;
changeDirection = FALSE;
} 其他 {
pCurrent = pCurrent-＆GT;左;
}
pNode =及（pCurrent-＆GT;左）;
} 其他 {
KdNode ** pNodeLeft =及（pCurrent-＆GT;左）;
* pNodeLeft =新KdNode（pCurrent，PV）;
PV = stackL.top（）;
stackL.pop（）;
KdNode ** pNodeRight =及（pCurrent-＆GT;右一）;
* pNodeRight =新KdNode（pCurrent，PV）;
pCurrent = pCurrent-＆GT;父母;
pNode =及（pCurrent-＆GT;右一）;
changeDirection = TRUE;
深度 - ;
}
}
}
无效buildRightTree（性病::栈＆LT; TPointVector＆GT;＆安培; stackR）{
KdNode * pCurrent = PROOT;
KdNode ** pNode =及（pCurrent-＆GT;右一）;
INT深度= 0;
布尔changeDirection = TRUE;
而（！stackR.empty（））{
TPointVector PV = stackR.top（）;
stackR.pop（）;
如果（pv.size（）！= 1）{
性病::排序（pv.begin（），pv.end（），ComparePoints（++深度））;
* pNode =新KdNode（pCurrent，pv.begin（）+ pv.size（）/ 2，深度，PV）;
TPointVector LVP，RVP;
的std ::为size_t位数= pv.size（）/ 2;
性病::复制（pv.begin（），pv.begin（）+中位数的std :: back_inserter（LVP））;
性病::复制（pv.begin（）+中位数，pv.end（），性病:: back_inserter（RVP））;
stackR.push（RVP）;
stackR.push（LVP）;
如果（changeDirection）{
pCurrent = pCurrent-＆GT;权利;
changeDirection = FALSE;
} 其他 {
pCurrent = pCurrent-＆GT;左;
}
pNode =及（pCurrent-＆GT;左）;
} 其他 {
KdNode ** pNodeLeft =及（pCurrent-＆GT;左）;
* pNodeLeft =新KdNode（pCurrent，PV）;
PV = stackR.top（）;
stackR.pop（）;
KdNode ** pNodeRight =及（pCurrent-＆GT;右一）;
* pNodeRight =新KdNode（pCurrent，PV）;
pCurrent = pCurrent-＆GT;父母;
pNode =及（pCurrent-＆GT;右一）;
深度 - ;
changeDirection = TRUE;
}
}
}
无效constructKD（TPointVector＆安培; PV）{
INT深度= 0;
性病::排序（pv.begin（），pv.end（），ComparePoints（深度））;
PROOT =新KdNode（0）;
pRoot-＆GT;递减=（pv.begin（）+ pv.size（）/ 2） - ＆的Pt [0];
pRoot-＆GT;左= 0;
pRoot-＆GT;右= 0;
TPointVector LVP，RVP;
性病::复制（pv.begin（），pv.begin（）+ pv.size（）/ 2，性病:: back_inserter（LVP））;
性病::复制（pv.begin（）+ pv.size（）/ 2，pv.end（），性病:: back_inserter（RVP））;
的std ::堆栈＆LT; TPointVector＆GT; stackL，stackR;
stackL.push（LVP）;
stackR.push（RVP）;
buildLeftTree（stackL）;
buildRightTree（stackR）;
}
无效readPoints（为const char *文件名，TPointVector和放大器;点）{
性病:: ifstream的输入（文件名）;
如果（input.peek（）！= EOF）{
而（！input.eof（））{
INT标识= 0;
双x_cord，y_cord;
输入＆GT;＆GT; ID＆GT;＆GT; x_cord＆GT;＆GT; y_cord;
点t;
t.pt [0] = x_cord;
t.pt [1] = y_cord;
t.id = ID;
points.push_back（T）;
}
input.close（）;
}
}
无效_printLevelWise（KdNode *节点的std ::队列＆LT; KdNode *＆GT; Q）{
INT深度= 0;
而（！Q.empty（））{
KdNode * qNode = Q.front（）; Q.pop（）;
如果（qNode-＆GT;叶）{
性病::法院＆LT;＆LT; [＆LT;＆LT; qNode-＆GT; ID＆LT;＆LT; ]＆LT;＆LT;性病::集precision（25）＆LT;＆LT; （＆其中;＆其中; qNode-＆GT;点[0]＆其中;＆所述;，＆其中;＆其中; qNode-＆GT;点[1];＆所述;）＆其中;＆其中;的std :: ENDL;
} 其他 {
性病::法院＆LT;＆LT;性病::集precision（25）＆LT;＆LT; qNode-＆GT;说明＆LT;＆LT;的std :: ENDL;
}
如果（qNode-＆GT;！左= 0）
Q.push（qNode-＆GT;左）;
如果（qNode-＆GT;！右= 0）
Q.push（qNode-＆GT;右一）;
}
}
无效PrintLevelWise（KdNode *节点）{
性病::队列＆LT; KdNode *＆GT; Q;
Q.push（节点）;
_printLevelWise（节点，Q）;
}
INT主（INT ARGC，字符** argv的）{
如果（的argc＆其中; = 1）{
返回0;
}
TPointVector点;
readPoints（的argv [1]，点）;
对于（TPointVector：迭代ITR = points.begin（！）; ITR = points.end（）; ++ ITR）{
性病::法院＆LT;＆LT; （＆其中;＆其中; itr-＆的Pt [0]＆其中;＆所述;，＆其中;＆其中; itr-＆的Pt [1];＆所述;）＆其中;＆其中;的std :: ENDL;
}
如果（points.size（）== 0）
返回0;
constructKD（分）;
PrintLevelWise（PROOT）;
性病::法院＆LT;＆LT; KD树的构建完成＆LT;＆LT;的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 不处理，其中有上右子树的节点为奇数的情况。在你的5点例如，其他情况 buildRightTree 结束了三个点 stackR ，第一，它使用了离开节点，后两个是默默分配给右键节点，就好像它是唯一的节点。
这是因为你的选择中位数，它采用了不同的标准比你引用该网站列出的。
的std ::为size_t位数= pv.size（）/ 2; //退化的情况下大小（）为奇数
您的选择条件应该是基于所述的中值的x或基于该标准（其不任何给定大小假设）y值和使用子列表。
Hello Does anybody has iterative implementation of Kd-Tree in C++. I tried but it is failing when the number of nodes are odd. Here is my code so far. I am referring http://ldots.org/kdtree/#buildingAkDTree site for details.
#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;
}
Sample Input for which this is failing :
1 6 1
2 5 5
3 9 6
4 3 6
5 4 9
Sample Input for which this is working :
1 6 1
2 5 5
3 9 6
4 3 6
5 4 9
6 4 0
7 7 9
8 2 9
解决方案
Your else in buildLeftTree and buildRightTree does not handle the case where there is an odd number of nodes on the right subtree. In your 5 point example, the else case in buildRightTree ends up with three points on stackR, the first it uses for the left node, the second two it silently assigns to the right node as if it were the only node.
This is due to your median selection, which uses a different criteria than the one listed on the site you reference.
std::size_t median = pv.size() / 2; // degenerates in cases where size() is odd
Your selection criteria is supposed to be based on the median x or y value and use sublists based on that criteria (which does not assume any given size).
这篇关于kd树迭代实现（C ++）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
