Using CKdTree

  • Nobody/Anonymous


    i'm trying to use the CKdTree class for searching the NN of 3d points. Can someone give me an example or description of the parameters and how the input data should be organized??

    Thank You

    • Pedram Azad

      Pedram Azad - 2008-04-08

      #include "DataStructures/KdTree/KdTree.h"

      #include <stdio.h>
      #include <stdlib.h>
      #include <math.h>
      #include <memory>

      #define USE_HEURISTIC

      int main()
          const int nBucketSize = 3; // just use 3; ask Kai Welke for more detailed information
          const int nDimensions = 3; // for 3D points
          const int nUserDataSize = 1; // space for extra data per entry, given in numbers of floats
          const int nLeavesForHeuristic = 5; // needed when using the heuristic variant:
          // the smaller the value the faster the search, but also less accurate
          int i;

          // example code
          const int nPoints = 10000;
          float **ppPoints = new float*[nPoints];
          for (i = 0; i < nPoints; i++)
              ppPoints[i] = new float[nDimensions + nUserDataSize];
              ppPoints[i][0] = rand() % 500;
              ppPoints[i][1] = rand() % 500;
              ppPoints[i][2] = rand() % 500;

              // store the pointer to the point (32 bit systems)
              memcpy(&ppPoints[i][3], &ppPoints[i], sizeof(float));
          // build kd-tree
          CKdTree tree;
          // note: this call will mix up the order of the points in ppPoints, so copy if this is a problem.
          //       for example, storing the index of each point would not work with the shuffled data.
          tree.Build(ppPoints, 0, nPoints - 1, nBucketSize, nDimensions, nUserDataSize);

          // determine nearest neighbor for a given point
          float point[3] = { 100, 200, 300 };
          float quality, *pResultData;   
          #ifdef USE_HEURISTIC
          // with BBF (best bin first) and heuristic
          tree.NearestNeighbour_HL_BBF(point, nLeavesForHeuristic, quality, pResultData);
          // conventional variant: always calculates the real nearest neighbor
          tree.NearestNeighbour(point, quality, pResultData);
          printf("the nearest neighbor according to the kd-tree is:\n");
          printf("euclidian distance = %.2f\n", sqrtf(quality));

          // variant 1 to access the result (via the result pointer):
          printf("access variant 1: %.2f %.2f %.2f\n", pResultData[0], pResultData[1], pResultData[2]);
          // variant 2 to access the result (via the stored pointer):
          const float *pPoint = (float *) ((unsigned int *) pResultData)[nDimensions];
          printf("access variant 2: %.2f %.2f %.2f\n", pPoint[0], pPoint[1], pPoint[2]);
          // note: in this case, the use of user data is superfluous. it's just for
          //       showing how to handle user data.

          // free memory
          for (i = 0; i < nPoints; i++)
              delete [] ppPoints[i];
          delete [] ppPoints;

          return 0;

    • Nobody/Anonymous

      Thank You for your response.
      Searching works very well and fast.

      But deleting the tree I get a runtime error:
      corrupted double-linked list.

      This error also occurs only calling the Dispose method. So maybe there is an malloc (or something) error?
      Do you have any suggestions?


    • Pedram Azad

      Pedram Azad - 2008-04-09

      Under which operating system and with which compiler are you having this problem? I tested the file from my previous posting under Mac OS X with gcc4 and under Linux with gcc3, and I am not getting any runtime errors.

      Does the exact same code I posted produce a runtime error?


    • Nobody/Anonymous

      Got the point:
      I deleted the result pointer, which is obviously forbidden. (Could be important to mention it in a future doc )

      Now it works fine.

      By the way, it is a very good library I was searchin for a long time. I'm working with PMD 3D-cameras, so I am especially interested in 3d-vision.
      I'm looking forward for a documentation :), maybe for adding some functionality ( cameras, etc. ).

      Best regards

    • Pedram Azad

      Pedram Azad - 2008-04-10

      Thanks for the compliment! :-)

      Documentation is definitely a good point, and it is on my TODO-list. I just don't have the time at the moment, but I hope this will change soon.

      The IVT is not a 3D library in first place, even though there are various functions for 3D calculations in  Math/Math3d.h and quite a lot of functionality for stereo vision (Calibration/StereoCalibration.h). But there is not that much for 3D point clouds in particular - except the core optimization method commonly used within the ICP algorithm (Tracking/ICP.h). What would be functionality you would find useful for 3D point clouds?



Get latest updates about Open Source Projects, Conferences and News.

Sign up for the SourceForge newsletter:

No, thanks