kd-tree 中的无限递归
Infinite Recursion in kd-tree
我正在尝试基于递归构建一个二维树。我可以将算法总结如下：
> ALGORITHM BuildKDTree(P,depth)
> 1. if P contains only one point
> 2. then return a leaf storing this point
> 3. else if depth is even
> 4. then split P with a vertical line through median x into P1 and P2 (left and right of the line, respectively)
> 5. else split P with a horizontal line through median y into P1 and P2 like before
> 6. RECURSION STEP -> v_left = BuildKDTree(P1,depth+1)
> 7. RECURSION STEP -> v_right = BuildKDTree(P2,depth+1)
> 8. Create a node v storing the line, make v_left the left child and v_right the right child
> 9. return the node v
由于我是第一次实现递归，因此遇到了很多与之相关的问题。到目前为止，我编写的代码似乎处于无限循环中，直到抛出分段错误。到目前为止，我无法在代码中找到错误，我将不胜感激。
// Point
struct Point{
int idx;
double xpos;
double ypos;
};
// Node in the k-d tree
struct Node{
char type;
Point coord;
Node* leftChild;
Node* rightChild;
double split;
};
// Function to find the median point
int findMedian( const vector<Point>& P, char line ){
vector<double> positions;
map<double,int> indices;
// Store the corresponding positions (vertical or horizontal splitting)
switch ( line ){
case 'x':
for( auto p: P ){
positions.push_back( p.xpos );
indices.insert( pair<double,int>(p.xpos,p.idx) );
}
break;
case 'y':
for( auto p: P ){
positions.push_back( p.ypos );
indices.insert( pair<double,int>(p.ypos,p.idx) );
}
break;
}
sort( positions.begin(), positions.end() );
cout << positions.size() << endl;
int middle_pt = (int)floor(positions.size()/2);
cout << indices[positions[middle_pt]] << "\t" << middle_pt << "\t" << positions[middle_pt] << endl;
return ( indices[positions[middle_pt]] );
}
// Function to build a k-d tree
Node buildKDTree( vector<Point> P, int depth ){
Node v;
// if P contains only one point, return a leaf storing this point;
// else if depth is even, split P with a vertical line through the median x ..
// .. into P1 (left of l) and P2 (right of l);
// when the depth is odd, do the vice versa.
if( P.size() == 1 ){
cout << "I am at the leaf!" << endl;
v.coord = P[0];
v.type = 'l';
return v;
}
else if( P.size() < 1 ){
cout << "Points size smaller than 1 " << P.size() << endl;
v.type = 'n';
return v;
}
else{
vector<Point> P1; // left of median
vector<Point> P2; // right of median
if( depth % 2 == 0 ) {
// Verical line through median x
char line = 'x';
v.type = line;
int mid_idx = findMedian( P, line );
v.split = P[mid_idx].xpos;
v.coord = P[mid_idx];
for( auto p: P ){
if( p.xpos < v.split ){
//cout << "Through x, left " << "\t" << p.xpos << "\t" << mid_coord << endl;
P1.push_back( p );
}
else{
//cout << "Through x, right " << "\t" << p.xpos << "\t" << mid_coord << endl;
P2.push_back( p );
}
}
}
else{
// Horizontal line through median y
char line = 'y';
v.type = line;
int mid_idx = findMedian( P, line );
v.split = P[mid_idx].ypos;
v.coord = P[mid_idx];
for( auto p: P ){
if( p.ypos < v.split ){
//cout << "Through y, left " << "\t" << p.ypos << "\t" << mid_coord << endl;
P1.push_back( p );
}
else{
//cout << "Through y, right " << "\t" << p.ypos << "\t" << mid_coord << endl;
P2.push_back( p );
}
}
}
cout << "depth is before at " << depth << endl;
Node temp1 = buildKDTree( P1, depth+1 );
depth = 2;
cout << "depth is after at " << depth << endl;
Node temp2 = buildKDTree( P2, depth+1 );
v.leftChild = &temp1;
v.rightChild = &temp2;
return v;
}
}
// +++++++
int main( int argc, char *argv[] ){
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
//++ Get the data
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// Choose the data to be used
const int nsamp = samplePostData; // Sampling interval
const double dtSamp = nsamp*dt; // Time units between two data points
// Instantiate the data structure
vector<Cell> cells( M );
// Set filenames
char * x_input_file = argv[1]; // Filename for the x data
char * y_input_file = argv[2]; // Filename for the y data
// Read the data to the cells
int sample_cnt = -1;
int sample_data = 1;
char getX = 'x';
readData( cells, x_input_file, getX, sample_cnt, sample_data );
sample_cnt = -1;
char getY = 'y';
readData( cells, y_input_file, getY, sample_cnt, sample_data );
// Set general simulation variables
Data simData;
simData.setNumStep( cells[0].xpos.size() );
simData.setNumDelay( sqrt( cells[0].xpos.size() ) );
simData.setNumTotalDelay();
const double T = simData.getNumStep(); // Total time
const double D = simData.getNumDelay(); // Last delay time
const double TD = simData.getNumTotalDelay(); // Total time - last delay time
// Set the box
Box box;
box.setWidth( boxSize_x );
box.setHeight( boxSize_y );
const double Lx = box.getWidth();
const double Ly = box.getHeight();
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
//++ Do the analysis
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
vector<Point> points;
int i = 1000;
for( int m = 0; m < M; m++ ){
Point point_temp;
point_temp.xpos = (cells[m].xpos[i] - Lx*ifloor(cells[m].xpos[i]/Lx));
point_temp.ypos = (cells[m].ypos[i] - Ly*ifloor(cells[m].ypos[i]/Ly));
point_temp.idx = m;
points.push_back( point_temp );
}
vector<Node> tree;
int depth = 2;
tree.push_back( buildKDTree( points, depth ) );
cout << tree.size() << endl;
// for( auto j: tree ){
// cout << j.type << " " << j.coord.idx << " " << j.coord.xpos << " " << j.coord.ypos << " " << j.leftChild->coord.idx << " " << j.rightChild->coord.idx << " " << j.leftChild->coord.xpos << " " << j.rightChild->coord.ypos << "\n";
// }
}
问题是您没有检查是否将同一点标记为中位数两次。很容易出现这种情况（尤其是在密集系统中）中线上有多个点。如果您没有明确标记之前用作中位数的点，那么您将再次使用它们，这将在树中创建无限递归。
我的建议是为每个点创建一个布尔数组，当你使用这些点作为中值时，只需标记它们，这样你以后就不会再使用它们了。
我正在尝试基于递归构建一个二维树。我可以将算法总结如下：
> ALGORITHM BuildKDTree(P,depth)
> 1. if P contains only one point
> 2. then return a leaf storing this point
> 3. else if depth is even
> 4. then split P with a vertical line through median x into P1 and P2 (left and right of the line, respectively)
> 5. else split P with a horizontal line through median y into P1 and P2 like before
> 6. RECURSION STEP -> v_left = BuildKDTree(P1,depth+1)
> 7. RECURSION STEP -> v_right = BuildKDTree(P2,depth+1)
> 8. Create a node v storing the line, make v_left the left child and v_right the right child
> 9. return the node v
由于我是第一次实现递归，因此遇到了很多与之相关的问题。到目前为止，我编写的代码似乎处于无限循环中，直到抛出分段错误。到目前为止，我无法在代码中找到错误，我将不胜感激。
// Point
struct Point{
int idx;
double xpos;
double ypos;
};
// Node in the k-d tree
struct Node{
char type;
Point coord;
Node* leftChild;
Node* rightChild;
double split;
};
// Function to find the median point
int findMedian( const vector<Point>& P, char line ){
vector<double> positions;
map<double,int> indices;
// Store the corresponding positions (vertical or horizontal splitting)
switch ( line ){
case 'x':
for( auto p: P ){
positions.push_back( p.xpos );
indices.insert( pair<double,int>(p.xpos,p.idx) );
}
break;
case 'y':
for( auto p: P ){
positions.push_back( p.ypos );
indices.insert( pair<double,int>(p.ypos,p.idx) );
}
break;
}
sort( positions.begin(), positions.end() );
cout << positions.size() << endl;
int middle_pt = (int)floor(positions.size()/2);
cout << indices[positions[middle_pt]] << "\t" << middle_pt << "\t" << positions[middle_pt] << endl;
return ( indices[positions[middle_pt]] );
}
// Function to build a k-d tree
Node buildKDTree( vector<Point> P, int depth ){
Node v;
// if P contains only one point, return a leaf storing this point;
// else if depth is even, split P with a vertical line through the median x ..
// .. into P1 (left of l) and P2 (right of l);
// when the depth is odd, do the vice versa.
if( P.size() == 1 ){
cout << "I am at the leaf!" << endl;
v.coord = P[0];
v.type = 'l';
return v;
}
else if( P.size() < 1 ){
cout << "Points size smaller than 1 " << P.size() << endl;
v.type = 'n';
return v;
}
else{
vector<Point> P1; // left of median
vector<Point> P2; // right of median
if( depth % 2 == 0 ) {
// Verical line through median x
char line = 'x';
v.type = line;
int mid_idx = findMedian( P, line );
v.split = P[mid_idx].xpos;
v.coord = P[mid_idx];
for( auto p: P ){
if( p.xpos < v.split ){
//cout << "Through x, left " << "\t" << p.xpos << "\t" << mid_coord << endl;
P1.push_back( p );
}
else{
//cout << "Through x, right " << "\t" << p.xpos << "\t" << mid_coord << endl;
P2.push_back( p );
}
}
}
else{
// Horizontal line through median y
char line = 'y';
v.type = line;
int mid_idx = findMedian( P, line );
v.split = P[mid_idx].ypos;
v.coord = P[mid_idx];
for( auto p: P ){
if( p.ypos < v.split ){
//cout << "Through y, left " << "\t" << p.ypos << "\t" << mid_coord << endl;
P1.push_back( p );
}
else{
//cout << "Through y, right " << "\t" << p.ypos << "\t" << mid_coord << endl;
P2.push_back( p );
}
}
}
cout << "depth is before at " << depth << endl;
Node temp1 = buildKDTree( P1, depth+1 );
depth = 2;
cout << "depth is after at " << depth << endl;
Node temp2 = buildKDTree( P2, depth+1 );
v.leftChild = &temp1;
v.rightChild = &temp2;
return v;
}
}
// +++++++
int main( int argc, char *argv[] ){
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
//++ Get the data
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// Choose the data to be used
const int nsamp = samplePostData; // Sampling interval
const double dtSamp = nsamp*dt; // Time units between two data points
// Instantiate the data structure
vector<Cell> cells( M );
// Set filenames
char * x_input_file = argv[1]; // Filename for the x data
char * y_input_file = argv[2]; // Filename for the y data
// Read the data to the cells
int sample_cnt = -1;
int sample_data = 1;
char getX = 'x';
readData( cells, x_input_file, getX, sample_cnt, sample_data );
sample_cnt = -1;
char getY = 'y';
readData( cells, y_input_file, getY, sample_cnt, sample_data );
// Set general simulation variables
Data simData;
simData.setNumStep( cells[0].xpos.size() );
simData.setNumDelay( sqrt( cells[0].xpos.size() ) );
simData.setNumTotalDelay();
const double T = simData.getNumStep(); // Total time
const double D = simData.getNumDelay(); // Last delay time
const double TD = simData.getNumTotalDelay(); // Total time - last delay time
// Set the box
Box box;
box.setWidth( boxSize_x );
box.setHeight( boxSize_y );
const double Lx = box.getWidth();
const double Ly = box.getHeight();
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
//++ Do the analysis
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
vector<Point> points;
int i = 1000;
for( int m = 0; m < M; m++ ){
Point point_temp;
point_temp.xpos = (cells[m].xpos[i] - Lx*ifloor(cells[m].xpos[i]/Lx));
point_temp.ypos = (cells[m].ypos[i] - Ly*ifloor(cells[m].ypos[i]/Ly));
point_temp.idx = m;
points.push_back( point_temp );
}
vector<Node> tree;
int depth = 2;
tree.push_back( buildKDTree( points, depth ) );
cout << tree.size() << endl;
// for( auto j: tree ){
// cout << j.type << " " << j.coord.idx << " " << j.coord.xpos << " " << j.coord.ypos << " " << j.leftChild->coord.idx << " " << j.rightChild->coord.idx << " " << j.leftChild->coord.xpos << " " << j.rightChild->coord.ypos << "\n";
// }
}
问题是您没有检查是否将同一点标记为中位数两次。很容易出现这种情况（尤其是在密集系统中）中线上有多个点。如果您没有明确标记之前用作中位数的点，那么您将再次使用它们，这将在树中创建无限递归。
我的建议是为每个点创建一个布尔数组，当你使用这些点作为中值时，只需标记它们，这样你以后就不会再使用它们了。