Où puis-je trouver une implémentation de kdtree ?

Question

Des recommandations pour un kd-tree C/C++ ?

Je suis à la recherche d'une mise en œuvre existante avec laquelle le posteur a, je l'espère, travaillé ou dont il a entendu parler en bien. De plus, j'ai besoin d'utiliser ce kd-tree pour effectuer une recherche 1/2-NN.

Answer 1

http://people.cs.ubc.ca/~mariusm/index.php/FLANN/FLANN

Ou OpenCV 1.2 qui a FLANN.

Answer 2

http://code.google.com/p/kdtree/

Answer 3

Ce code est optimisé pour TAILLE .

Vous verrez donc beaucoup de "mauvais hacks".

Notez que nous avons utilisé 'struct', mais il peut être facilement changé en classe si vous ajoutez public: . Paste manque également le type 'Point2D' mais vous pouvez deviner à quoi cela ressemble. Includes et Include guards ont également été supprimés.

/* ------------------------------ kdtree.h ------------------------------ */

typedef struct kdNode2D
{
    kdNode2D(pPoint2D pointList, int pointLength, int depth = 0);

    ~kdNode2D()
    {
        for(int i=0; i<2; ++i)
            delete sons[i];
    }

    /* Leave depth alone for outside code! */
    unsigned nearest(const Point2D &point, int depth = 0);

    union {
        struct {
            kdNode2D* left;
            kdNode2D* right;
        };

        kdNode2D* sons[2];
    };

    Point2D p;

} kdNode2D;

/* ----------------------------- kdtree.cpp ----------------------------- */

static int cmpX(const void* a, const void* b)
{
    return (*(pPoint2D)a).x - (*(pPoint2D)b).x;
}

static int cmpY(const void* a, const void* b)
{
    return (*(pPoint2D)a).y - (*(pPoint2D)b).y;
}

kdNode2D::kdNode2D(pPoint2D pointList, int pointLength, int depth)
{
    if(pointLength == 1) {
        left    = NULL;
        right   = NULL;
        p       = *pointList;
        return;
    }

        // Odd depth = Y, even depth = X
    if(depth & 1)
        qsort(pointList, pointLength, sizeof(Point2D), cmpY);
    else
        qsort(pointList, pointLength, sizeof(Point2D), cmpX);

    const int halfLength = pointLength >> 1;
    p = pointList[halfLength];
    for(int i=0; i<2; ++i)
        sons[i] = new kdNode2D(pointList + (i*halfLength), halfLength, depth + 1);
}

unsigned kdNode2D::nearest(const Point2D &point, int depth)
{
    /* End of tree. */
    if(!left || !right)   // We assume if left != NULL, then right != NULL (see ctor)
    {
        Point2D r = p;
        for(int i=0; i<2; ++i)
            r[i] -= point[i];

        return r.dot(r);
    }

    const int tmp = p[depth] - point[depth];
    const int side = tmp < 0; /* Prefer the left. */

    /* Switch depth. */
    depth ^= 1;

    /* Search the near side of the tree. */
    int leftDist = sons[side]->nearest(point, depth);

    /* Radius intersects a kd tree boundary? */
    if(leftDist < (tmp * tmp))
    {
        /* No; this is the nearest point on this side. */
        return leftDist;
    }

    /* Yes; look at the points on the other side. */
    return min(leftDist, sons[side ^ 1]->nearest(point, depth));
}

Answer 4

Juste pour que la liste soit complète. Il existe une bonne implémentation d'un kdtree en c++ appelée libkdtree++ . La bibliothèque est modélisée, et vous pouvez utiliser vos propres structures de données comme nœuds. J'ai utilisé cette bibliothèque à quelques reprises, et je l'ai particulièrement appréciée pour son interface. Je n'ai pas encore fait de benchmarking.

Answer 5

Recommandez 2 approches à envisager :

1) approche classique du ptr :

class KdTreeNode
{
   private :
    vector<T> data;
    KdTreeNode * Left;
    KdTreeNode * Right; 
};

2) std::map approche :

où un nœud d'arbre est constitué de :

class KdTreeNode
{
  private :
    map<K, V> values;
    map<K, KdTreeNode> subnodes;
};

ad 1. Je l'ai utilisé il y a quelques années dans un projet graphique dont ma société avait besoin, il est simple et fait le travail.

ad 2. Je l'ai utilisé dernièrement, mais pas comme un KdTree. Grâce à l'utilisation de cartes, il est très polyvalent.

Je ne dis pas que mes solutions sont les meilleures, mais j'ai essayé les deux, à différentes occasions, et elles ont fonctionné.

J'espère que cela vous aidera.