k-d tree implementation [closed]
- by user466441
when i run my code and debugged,i got this error
- this 0x00093584 {_Myproxy=0x00000000 _Mynextiter=0x00000000 } std::_Iterator_base12 * const
- _Myproxy 0x00000000 {_Mycont=??? _Myfirstiter=??? } std::_Container_proxy *
_Mycont CXX0017: Error: symbol "" not found
_Myfirstiter CXX0030: Error: expression cannot be evaluated
+ _Mynextiter 0x00000000 {_Myproxy=??? _Mynextiter=??? } std::_Iterator_base12 *
but i dont know what does it means,code is this
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct point
{
float x,y;
};
vector<point>pointleft(4);
vector<point>pointright(4);
//we are going to implement two comparison function for x and y coordinates,we need it in calculation of median (we should sort vector
//by x or y according to depth informaton,is depth even or odd.
bool sortby_X(point &a,point &b)
{
return a.x<b.x;
}
bool sortby_Y(point &a,point &b)
{
return a.y<b.y;
}
//so i am going to implement to median finding algorithm,one for finding median by x and another find median by y
point medianx(vector<point>points)
{
point temp;
sort(points.begin(),points.end(),sortby_X);
temp=points[(points.size()/2)];
return temp;
}
point mediany(vector<point>points)
{
point temp;
sort(points.begin(),points.end(),sortby_Y);
temp=points[(points.size()/2)];
return temp;
}
//now construct basic tree structure
struct Tree
{
float x,y;
Tree(point a)
{
x=a.x;
y=a.y;
}
Tree *left;
Tree *right;
};
Tree * build_kd( Tree *root,vector<point>points,int depth)
{
point temp;
if(points.size()==1)// that point is as a leaf
{
if(root==NULL)
root=new Tree(points[0]);
return root;
}
if(depth%2==0)
{
temp=medianx(points);
root=new Tree(temp);
for(int i=0;i<points.size();i++)
{
if (points[i].x<temp.x)
pointleft[i]=points[i];
else
pointright[i]=points[i];
}
}
else
{
temp=mediany(points);
root=new Tree(temp);
for(int i=0;i<points.size();i++)
{
if(points[i].y<temp.y)
pointleft[i]=points[i];
else
pointright[i]=points[i];
}
}
return build_kd(root->left,pointleft,depth+1);
return build_kd(root->right,pointright,depth+1);
}
void print(Tree *root)
{
while(root!=NULL)
{
cout<<root->x<<" " <<root->y;
print(root->left);
print(root->right);
}
}
int main()
{
int depth=0;
Tree *root=NULL;
vector<point>points(4);
float x,y;
int n=4;
for(int i=0;i<n;i++)
{
cin>>x>>y;
points[i].x=x;
points[i].y=y;
}
root=build_kd(root,points,depth);
print(root);
return 0;
}
i am trying ti implement in c++ this pseudo code
tuple function build_kd_tree(int depth, set points):
if points contains only one point:
return that point as a leaf.
if depth is even:
Calculate the median x-value.
Create a set of points (pointsLeft) that have x-values less than
the median.
Create a set of points (pointsRight) that have x-values greater
than or equal to the median.
else:
Calculate the median y-value.
Create a set of points (pointsLeft) that have y-values less than
the median.
Create a set of points (pointsRight) that have y-values greater
than or equal to the median.
treeLeft = build_kd_tree(depth + 1, pointsLeft)
treeRight = build_kd_tree(depth + 1, pointsRight)
return(median, treeLeft, treeRight)
please help me what this error means?
