## Using CKdTree

Help
2008-04-08
2013-05-09
• Nobody/Anonymous - 2008-04-08

Hallo,

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
Paul

#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);
#else
// conventional variant: always calculates the real nearest neighbor
tree.NearestNeighbour(point, quality, pResultData);
#endif

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 - 2008-04-08

Searching works very well and fast.

But deleting the tree I get a runtime error:

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

Regards
Paul

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?

Regards
Pedram

• Nobody/Anonymous - 2008-04-09

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
Paul

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?

Regards
Pedram