0
我正試圖建立一個基於遞歸的二維樹。我可以總結算法如下：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";
// }
}
聽起來像「請爲我調試」。我的建議是自己調試它。這是一項挑戰，如果您接受挑戰，您將從中獲得最大收益。另一點是：從小開始。學習單元測試。學習[TDD]（https://en.wikipedia.org/wiki/Test-driven_development）。 – TobiMcNamobi