c++ - Kdtree 距离最小的最近邻

Question

我正在使用 ANN kdtree 库来查找最近的邻居。我想找到距离最短的最近邻居。我在下面包含了常规代码（来自 ANN 库）。很明显，每次找到邻居时我都可以检查距离，但我正在寻找一种更有效的方法。

    void ANNkd_tree::annkSearch(
    ANNpoint            q,              // the query point
    int                 k,              // number of near neighbors to return
    ANNidxArray         nn_idx,         // nearest neighbor indices (returned)
    ANNdistArray        dd,             // the approximate nearest neighbor
    double              eps)            // the error bound
{

    ANNkdDim = dim;                     // copy arguments to static equivs
    ANNkdQ = q;
    ANNkdPts = pts;
    ANNptsVisited = 0;                  // initialize count of points visited

    if (k > n_pts) {                    // too many near neighbors?
        annError("Requesting more near neighbors than data points", ANNabort);
    }

    ANNkdMaxErr = ANN_POW(1.0 + eps);
    ANN_FLOP(2)                         // increment floating op count

    ANNkdPointMK = new ANNmin_k(k);     // create set for closest k points
                                        // search starting at the root
    root->ann_search(annBoxDistance(q, bnd_box_lo, bnd_box_hi, dim));

    for (int i = 0; i < k; i++) {       // extract the k-th closest points
        dd[i] = ANNkdPointMK->ith_smallest_key(i);
        nn_idx[i] = ANNkdPointMK->ith_smallest_info(i);
    }
    delete ANNkdPointMK;                // deallocate closest point set
}



    //----------------------------------------------------------------------
    //  kd_split::ann_search - search a splitting node
    //----------------------------------------------------------------------

    void ANNkd_split::ann_search(ANNdist box_dist)
    {
                                            // check dist calc term condition
        if (ANNmaxPtsVisited != 0 && ANNptsVisited > ANNmaxPtsVisited) return;

                                            // distance to cutting plane
        ANNcoord cut_diff = ANNkdQ[cut_dim] - cut_val;

        if (cut_diff < 0) {                 // left of cutting plane
            child[ANN_LO]->ann_search(box_dist);// visit closer child first

            ANNcoord box_diff = cd_bnds[ANN_LO] - ANNkdQ[cut_dim];
            if (box_diff < 0)               // within bounds - ignore
                box_diff = 0;
                                            // distance to further box
            box_dist = (ANNdist) ANN_SUM(box_dist,
                    ANN_DIFF(ANN_POW(box_diff), ANN_POW(cut_diff)));

                                            // visit further child if close enough
            if (box_dist * ANNkdMaxErr < ANNkdPointMK->max_key())
                child[ANN_HI]->ann_search(box_dist);

        }
        else {                              // right of cutting plane
            child[ANN_HI]->ann_search(box_dist);// visit closer child first

            ANNcoord box_diff = ANNkdQ[cut_dim] - cd_bnds[ANN_HI];
            if (box_diff < 0)               // within bounds - ignore
                box_diff = 0;
                                            // distance to further box
            box_dist = (ANNdist) ANN_SUM(box_dist,
                    ANN_DIFF(ANN_POW(box_diff), ANN_POW(cut_diff)));

                                            // visit further child if close enough
            if (box_dist * ANNkdMaxErr < ANNkdPointMK->max_key())
                child[ANN_LO]->ann_search(box_dist);

        }
        ANN_FLOP(10)                        // increment floating ops
        ANN_SPL(1)                          // one more splitting node visited
    }

    //----------------------------------------------------------------------
    //  kd_leaf::ann_search - search points in a leaf node
    //      Note: The unreadability of this code is the result of
    //      some fine tuning to replace indexing by pointer operations.
    //----------------------------------------------------------------------

    void ANNkd_leaf::ann_search(ANNdist box_dist)
    {
        register ANNdist dist;              // distance to data point
        register ANNcoord* pp;              // data coordinate pointer
        register ANNcoord* qq;              // query coordinate pointer
        register ANNdist min_dist;          // distance to k-th closest point
        register ANNcoord t;
        register int d;

        min_dist = ANNkdPointMK->max_key(); // k-th smallest distance so far

        for (int i = 0; i < n_pts; i++) {   // check points in bucket

            pp = ANNkdPts[bkt[i]];          // first coord of next data point
            qq = ANNkdQ;                    // first coord of query point
            dist = 0;

            for(d = 0; d < ANNkdDim; d++) {
                ANN_COORD(1)                // one more coordinate hit
                ANN_FLOP(4)                 // increment floating ops

                t = *(qq++) - *(pp++);      // compute length and adv coordinate
                                            // exceeds dist to k-th smallest?
                if( (dist = ANN_SUM(dist, ANN_POW(t))) > min_dist) {
                    break;
                }
            }

            if (d >= ANNkdDim &&                    // among the k best?
               (ANN_ALLOW_SELF_MATCH || dist!=0)) { // and no self-match problem
                                                    // add it to the list
                ANNkdPointMK->insert(dist, bkt[i]);
                min_dist = ANNkdPointMK->max_key();
            }
        }
        ANN_LEAF(1)                         // one more leaf node visited
        ANN_PTS(n_pts)                      // increment points visited
        ANNptsVisited += n_pts;             // increment number of points visited
    }