c++ - kd-tree 中的无限递归

Question

我正在尝试基于递归构建一个二维树。我可以将算法总结如下:

>     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";
//    }


}

Answer 1

问题是您不检查是否将同一点标记为中位数两次。很容易出现这种情况(尤其是在密集系统中)中线上有多个点。如果您没有明确标记之前用作中位数的点，那么您将再次使用它们，这将在树中创建无限递归。

我的建议是为每个点创建一个 bool 数组，当你使用这些点作为中值时，只需标记它们，这样你以后就不会再使用它们了。