kbriggs:~/tests> g++ -Wall -I ~/Downloads/nanoflann-master/include/ -I ~/Downloads/nanoflann-master/examples pointcloud_kdd_radius.cpp -o pointcloud_kdd_radius
In file included from pointcloud_kdd_radius.cpp:31:0:
/home/kbriggs/Downloads/nanoflann-master/include/nanoflann.hpp: In constructor ‘nanoflann::KDTreeSingleIndexDynamicAdaptor<Distance, DatasetAdaptor, DIM, IndexType>::KDTreeSingleIndexDynamicAdaptor(int, DatasetAdaptor&, const nanoflann::KDTreeSingleIndexAdaptorParams&, size_t)’:
/home/kbriggs/Downloads/nanoflann-master/include/nanoflann.hpp:1825:16: error: ‘log2’ is not a member of ‘std’
treeCount = std::log2(maximumPointCount);
^
/home/kbriggs/Downloads/nanoflann-master/include/nanoflann.hpp:1825:16: note: suggested alternative:
In file included from /usr/include/features.h:367:0,
from /usr/include/x86_64-linux-gnu/c++/5/bits/os_defines.h:39,
from /usr/include/x86_64-linux-gnu/c++/5/bits/c++config.h:482,
from /usr/include/c++/5/bits/stl_algobase.h:59,
from /usr/include/c++/5/vector:60,
from /home/kbriggs/Downloads/nanoflann-master/include/nanoflann.hpp:49,
from pointcloud_kdd_radius.cpp:31:
/usr/include/x86_64-linux-gnu/bits/mathcalls.h:144:1: note: ‘log2’
__MATHCALL (log2,, (Mdouble __x));
^

This is definitely a low-priority edge case. I caught while doing some unit-tests of my own.
The repro rate is about 20%. i.e. the code fails about once every five tries.

#include <iostream>
#include <Eigen/Dense>
#include "NanoFlann.h"


using Eigen::Array3f;


struct VectorDataAdaptor
{
    std::vector<Array3f> points;

    VectorDataAdaptor(const std::vector<Array3f> &points)
        : points(points)
    {}

    inline size_t kdtree_get_point_count() const
        { return points.size(); }

    inline float kdtree_get_pt(const size_t idx, int dim) const
        { return points[idx][dim]; }

	float kdtree_distance(const float *p, const size_t idx_q, size_t size) const
        {
            assert( size == 3 );
            return (Eigen::Array3d(p[0], p[1], p[2]) - points[idx_q].cast<double>()).matrix().squaredNorm();
        }

    template <class BBOX> bool kdtree_get_bbox(BBOX &bb) const
        { return false; }
};


template<class T>
static inline std::vector<size_t> getNeighborIndices(
    const T& kdtree, const Array3f &p, const size_t &num_neighbors)
{
    std::vector<size_t> out_indices(num_neighbors);
    std::vector<float> out_sqdists(num_neighbors);

    const auto num_found = kdtree.knnSearch(&p[0], num_neighbors, &out_indices[0], &out_sqdists[0]);
    assert( num_found == num_neighbors );

    return std::move(out_indices);
}


int main(int argc, char *argv[])
{
    std::vector<Array3f> points;
    for (int i=0; i<10; ++i)
        points.push_back(Array3f::Random()*50);

    typedef nanoflann::L2_Simple_Adaptor<float, VectorDataAdaptor> DistanceFunction_t;
    typedef nanoflann::KDTreeSingleIndexAdaptor<DistanceFunction_t, VectorDataAdaptor, 3, size_t> KDTree_t;
    
    KDTree_t search_index(3, VectorDataAdaptor(points));
    search_index.buildIndex();

    for (const auto &p : points) {
        getNeighborIndices(search_index, p, 10);
    }

    return 0;
}

TODO: Take a look at the patch:

"there is a couple of warning when compiling in 64 bits"
->

Index: nanoflann.hpp

--- nanoflann.hpp (revision 39165)
+++ nanoflann.hpp (working copy)
@@ -396,12 +396,12 @@
*/
struct KDTreeSingleIndexAdaptorParams
{

•   KDTreeSingleIndexAdaptorParams(size_t _leaf_max_size = 10, int dim_ = -1) :
  

•   KDTreeSingleIndexAdaptorParams(const int _leaf_max_size = 10, size_t dim_ = -1) :
      leaf_max_size(_leaf_max_size), dim(dim_)
  {}
  

•   size_t leaf_max_size;
  

•   int dim;
  

•   const int leaf_max_size;
  

•   size_t dim;
  

  };

  /** Search options for KDTreeSingleIndexAdaptor::findNeighbors() */
  @@ -753,7 +753,7 @@
  const KDTreeSingleIndexAdaptorParams index_params;

  size_t m_size;
  

•   int dim;  //!< Dimensionality of each data point
  

•   size_t dim;  //!< Dimensionality of each data point
  
  
  /*--------------------- Internal Data Structures --------------------------*/
  

  @@ -846,7 +846,7 @@
  * inputData = dataset with the input features
  * params = parameters passed to the kdtree algorithm (see http://code.google.com/p/nanoflann/ for help choosing the parameters)
  */

•   KDTreeSingleIndexAdaptor(const int dimensionality, const DatasetAdaptor& inputData, const KDTreeSingleIndexAdaptorParams& params = KDTreeSingleIndexAdaptorParams() ) :
  

•   KDTreeSingleIndexAdaptor(const size_t dimensionality, const DatasetAdaptor& inputData, const KDTreeSingleIndexAdaptorParams& params = KDTreeSingleIndexAdaptorParams() ) :
      dataset(inputData), index_params(params), root_node(NULL), distance(inputData)
  {
      m_size = dataset.kdtree_get_point_count();
  

  @@ -1371,7 +1371,7 @@
  index_t* index; //! The kd-tree index for the user to call its methods as usual with any other FLANN index.

  /// Constructor: takes a const ref to the matrix object with the data points
  

•   KDTreeEigenMatrixAdaptor(const int dimensionality, const MatrixType &mat, const int leaf_max_size = 10) : m_data_matrix(mat)
  

•   KDTreeEigenMatrixAdaptor(const size_t dimensionality, const MatrixType &mat, const int leaf_max_size = 10) : m_data_matrix(mat)
  {
      const size_t dims = mat.cols();
      if (DIM>0 && static_cast<int>(dims)!=DIM)
  

  @@ -1425,7 +1425,7 @@
  }

  // Returns the dim'th component of the idx'th point in the class:
  

•   inline num_t kdtree_get_pt(const size_t idx, int dim) const {
  

•   inline num_t kdtree_get_pt(const size_t idx, size_t dim) const {
      return m_data_matrix.coeff(idx,dim);
  }
  

Hi I'm getting the errors with vs110 on following lines -

• template
  struct has_resize <T, decltype((void)std::declval().resize(1), 0)> : std::true_type {};
• template
  struct has_assign <T, decltype((void)std::declval().assign(1, 0), 0)> : std::true_type {};

The error are -

• Failed to specialize function template 'add_rvalue_reference<_Ty>::type std::declval(int) throw()'
• left of '.resize' must have class/struct/union

The code is littered with problematic conversions from unsigned to signed integers and truncations, because size_t has 64 bit length and int hasn't.

Some of them are issues due to the fact that the Template parameter IndexType is not used where it ought to be, this is relative easy to fix (await pull request).

But a big problem here is that the Dimension is of type int instead of type IndexType, so if you set IndexType to size_t and have a int dimension you will get buried in hundreds of warnings.
Solutiuon would be to change the Template argument order and make the dim paramter of type IndexSize, but this is a serious Interface change and needs disuccion.

Any ideas how to fix this?

Hi!

It seems like recently, flann was added as a submodule to this repo. It's not used in the nanoflann.hpp header, but I found some uses of flann headers in the benchmark folders.
Now as a user of just the nanoflann header, included via submodule in my own repo, it's quite annoying that now with every clone, the flann submodule is fetched through nanoflann. Even more so since it's completely unnecessary for the nanoflann library. I know that repositories can be cloned without --recursive and then transitive submodules will not be fetched but unfortunately this is very often not an option as other repos actually do need the submodules that they include.

I would like to propose to move the benchmark (or whichever part uses flann) to a different repo (it can be linked in the README.md here), so that users including the nanoflann repo into their repos via submodule, aren't fetching the flann code too. After all, the main reason to use nanoflann, is not to have to use flann.
For me, this is currently a reason not to upgrade nanoflann.

My ultimate goal here is to use this KD tree for iterative closest point on a per-frame basis. I'm still playing around with things and have made one step toward enabling this, but before a PR I wanted to ask if there was more that can be done. Before sharing the code, I was looking for high level advice on what I can try out.

1. The first optimization that can be done is a very simple modification to the eigen matrix adapter class. The class (call it KDTreeStaticEigenMatrixAdaptor) is virtually identical except for one method:

   // Must return the number of data points
   inline size_t kdtree_get_point_count() const {
       return MatrixType::RowsAtCompileTime;
   }

   and in the constructor:

   // const IndexType dims = mat.cols();
   const IndexType dims = MatrixType::ColsAtCompileTime;

   Some preliminary results:

   Generating 1000000 random points...done
   Generic matrix adapter class:
     Building the index took: 549 ms
     Initializing the result set took: 0 us
     Finding the neighbors took: 15 us
     knnSearch(nn=3):
       ret_index[0]=821326 out_dist_sqr=0.2484
       ret_index[1]=764833 out_dist_sqr=0.2628
       ret_index[2]=639822 out_dist_sqr=0.381601
   Static matrix adapter class:
     Building the index took: 455 ms
     Initializing the result set took: 0 us
     Finding the neighbors took: 13 us
     knnSearch(nn=3):
       ret_index[0]=821326 out_dist_sqr=0.2484
       ret_index[1]=764833 out_dist_sqr=0.2628
       ret_index[2]=639822 out_dist_sqr=0.381601
   

   Savings of ~100ms. Adding another 0, we get the generic matrix adapter index build is 9764 ms, and the static version is 9126 ms. So cool, this is a good step so far. But I feel like there is a lot more that could be done here. Note I'm using the default 10 here, I haven't delved into finding the ideal parameters for my problem size yet, just optimizing the "worst" case index build right now ;)

2. Example usage must change, since unless you have a generally small problem size, you cannot use the Eigen::Matrix<type, N, Cols> directly (static asserts about allocating on the stack for a matrix that is too big). It looks something like this:

   static constexpr unsigned N = 10000000u;
   using Matrix = Eigen::Matrix<float, N, 4, Eigen::DontAlign>;
   
   // r_positions contains the raw data
   Eigen::Map<Matrix> mat = Eigen::Map<Matrix>(r_positions, N, 4);
   
   // create the index
   using my_kd_tree_t = nanoflann::KDTreeStaticEigenMatrixAdaptor<Eigen::Map<Matrix>>;
   my_kd_tree_t mat_index(mat, 10 /* max leaf */ );

   I don't actually really understand how this even works, the Eigen::Map class is kind of confusing. You can still use things like map.row(0) etc, but as far as I could tell it doesn't actually inherit from Eigen::MatrixBase. But in the end it works, and the results are consistent.

3. What else can be changed for this adapter if we know everything at compile time? The point cloud example has this

   // Returns the dim'th component of the idx'th point in the class:
   // Since this is inlined and the "dim" argument is typically an immediate value, the
   //  "if/else's" are actually solved at compile time.
   inline coord_t kdtree_get_pt(const size_t idx, int dim) const
   {
       if (dim == 0) return derived().pts[idx].x;
       else if (dim == 1) return derived().pts[idx].y;
       else return derived().pts[idx].z;
   }

   I got a little turned around on how this would go down in the matrix case (the loop can be unrolled since we know both rows and columns), but I didn't see how it would help since coeff already allows both.

   Another thought that comes to mind (for both the generic and static eigen adapter) is the bounding box method. You should be able to compute it with something like mat.col(0).minCoeff() for each column or something, I think.

4. Quasi-related to all of this, possibly better for a separate discussion, I suspect that if I want to re-use the KDTree each frame, there should be a better way of just allocating the memory for the indices once at the beginning and reusing that. Is that possible with how things are setup?

When looking at your description I was wondering whether this library uses kd-trees to determine exact results in the knn and radius search or if there are approximations? For me it looks that you do not perform approximations; which would make sense for low-dimensional point-clouds.

https://github.com/jlblancoc/nanoflann/blob/master/include/nanoflann.hpp#L778

There are some problems with this code:
Unnamed structs in unions are not allowed in C++98. gcc doesn't know that, clang does.
There is also a very bad aliasing issue, because IndexType might not have the same size as the other struct, in my case 4 bytes off.

I'm confused by this function. Nothing ever seems to call it.

Seems like it wasn't fully cleared out during this commit.
b83c291#diff-6972321bb8a18bf106257beeecb4a09eL371

There was some memory leakage problem in my own move assignment operator. No issue.

nanoflann starts to make use of modern CMake which I highly appreciate (https://github.com/jlblancoc/nanoflann/blob/master/CMakeLists.txt#L64). However, this breaks support for CMake 2.8.12 since header-only libraries/targets are a feature of CMake 3.0+ (see https://cmake.org/cmake/help/v3.0/release/3.0.0.html#commands). Unfortunately, this issue has not been caught by Travis since it uses CMake 3.9.
Furthermore, this target is also used to build nanoflann's benchmarks, but sadly not exported/installed such that users with more recent version of CMake can actually profit from this.

I would like to contribute a patch to fix this, but first wanted to get some feedback which strategy would be best to tackle the problem. Essentially, there are two possibilities:

• Bump minimum required CMake version to 3.0 (or 3.1 to get set(CMAKE_CXX_STANDARD 11)) and export targets such that user can also use them (see e.g. https://pabloariasal.github.io/2018/02/19/its-time-to-do-cmake-right/).

• Export targets but guard all CMake 3.0+ stuff (if (NOT CMAKE_VERSION VERSION_LESS 3.0)) to also provide support for old CMake 2.8.12.

The former results in a much cleaner CMake file at the cost of dropping support for Ubuntu 14.04 LTS and folks. The latter approach has the opposite effect, i.e. more clutter but proper support. Suggestions?

Best regards,
Patrick Stotko

First, I would like to thank you for sharing this very useful kNN library.

When using KDTreeSingleIndexAdaptor, I would like to send the DIM value at runtime. However, it is a constant expression right now. Is there a way to go around this rule?
I am interested on generating different datasets with different dimensions, then for each dataset, I want to do kNN and radius search after building the kd-tree. The value of DIM should be sent at runtime.

Thank you,

KDTreeEigenMatrixAdaptor works with data in which "Each row in the matrix represents a point in the state space", i.e. for three-dimensional points, the data should be stored in the Eigen::MatrixX3d.

In some cases, the points are conveniently stored in columns - in the Eigen::Matrix3Xd.
For example, here implemented an adapter for this case:

...
struct KDTreeAdaptor {
    ...
    KDTreeAdaptor(const MatrixType &mat, const int leaf_max_size = 10) : m_data_matrix(mat) {
        const size_t dims = mat.rows();
        ...

Can you add this option to the library?

Is it possible to apply transformations (rotation/translation/scaling) to the entire tree without rebuilding the index? If yes, this might be a nice feature for increasing speed.

http://jlblancoc.github.io/nanoflann/modules.html says "C++ header-only ANN library", and the term ANN appears in other places in the docs. I thought ANN meant 'approximate nearest neighbours', but https://github.com/jlblancoc/nanoflann says "No support for approximate NN is provided". What's going on here?

VS2015 warns of possible loss of data when assigning a zero value as the value is always int and converted to float or double.

An easy fix would be to make the following changes to findNeighbors function

auto zero = static_cast<decltype(result.worstDist())>(0);
assign(dists, (DIM > 0 ? DIM : BaseClassRef::dim), zero); // Fill it with zeros.

Here's the existing constructor.

		KDTreeSingleIndexDynamicAdaptor(const int dimensionality, DatasetAdaptor& inputData, const KDTreeSingleIndexAdaptorParams& params = KDTreeSingleIndexAdaptorParams() , const size_t maximumPointCount = 1000000000U) :
			dataset(inputData), index_params(params), distance(inputData)
		{
			if (dataset.kdtree_get_point_count()) throw std::runtime_error("[nanoflann] cannot handle non empty point cloud.");
			treeCount = std::log2(maximumPointCount);
			pointCount = 0U;
			dim = dimensionality;
			treeIndex.clear();
			if (DIM > 0) dim = DIM;
			m_leaf_max_size = params.leaf_max_size;
			init();
		}

Would there be anything wrong with removing the assertion and then adding a line:
addPoints(0, dataset.kdtree_get_point_count() - 1);
right after init?
This seems more intuitive.

If some or all points changed coordinates, is it somehow possible to reinsert them in same tree structure (without rebuilding)?

E.g. I have transient simulation of point cloud (with known bounds) and would like to rebuild whole tree on every N-th step, else just reinsert moving points into already built hierarchy.

Is nanoflann thread-safe under (apparently) read-only operations?

As per title, the link to docs gives a 403.

I try to figure out what is the normal behaviour when
I build index on a matrix (x,y) with a query based on another matrix (x,y)
How many results nannoflann will return ?

Will nannoflann return each ANN for each point of my query (here x rows <=> x points)?

How should nanoflann be cited in a research article?

In file: nanoflann/examples/KDTreeVectorOfVectorsAdaptor.h

Here are some things that might need changing:

1. Line 54: typedef KDTreeSingleIndexAdaptor< metric_t,self_t,DIM,IndexType> index_t;
   Solution: Need to reference the namespace, so perhaps change it to: typedef nanoflann::KDTreeSingleIndexAdaptor

2. Line 82: nanoflann::KNNResultSet<typename VectorOfVectorsType::Scalar,IndexType> resultSet(num_closest); in inline void query:
   If VectorOfVectorsType is std::vector<std::vector<double> >, then it will complain that no member ::Scalar exists. I think you intended that for Eigen::VectorXd.
   Solution: I got this to work by changing it to num_t

Hi,

Would it be possible to add a method to get all indices of points that are traversed by a ray?

Something like:

size_t raySearch(const ElementType *ray_origin, const ElementType *ray_direction, const DistanceType ray_length, std::vector<IndexType> &indices) const;

Or do you have some tips about how to implement this kind of query?
I think it would be very useful (e.g for raytracing, etc...).

Thanks!

Have you given any thought to porting this to CUDA? Perhaps not the tree construction, but being able to find the kNN of a set of points in parallel, rather than one at a time would be great!

When performing a search for a maximum of k nearest points using the function knnSearch, we get invalid results if the number of elements on the tree is less than the requested number of results (num_results).

Hi,

this link gives me a 404 and hence is not reachable. Here is the full error report:

Forbidden
You don't have permission to access /svn/classnanoflann_1_1KDTreeSingleIndexAdaptor.html on this server.
Additionally, a 403 Forbidden error was encountered while trying to use an ErrorDocument to handle the request.

Can this be solved?

Compiling with flann I get the following warning (translated to error by -Werror)

nanoflann.hpp:468:11: error: private field 'blocksize' is not used [-Werror,-Wunused-private-field]
                 size_t  blocksize;
                         ^

In many applications we need to map N-dimensional points to a single dimension while preserving space locality. One approach is to build a kd-tree and do an in-order traversal (see e.g. here). Could this be done with nanoflann?

Hello,

I'm using radius search with a custom callback. I would like to know if there is a way to stop the search right immediately. (or maybe a link to the documentation of the ResultSet interface)

Thank you very much for your help

Hi

I'm using the Vector_of_Vectors example to find nearest neighbors to 128 dimensional float vectors.

When using 1e6 samples everything seems fast enough: Building the tree and building the index.

But When using 1e7 samples which is 10 times larger, the tree takes a LOT more time to build and also to index.

I did this example in Python/Numpy/cKdTree and it really wasn't this slow to build the tree and index.

Is my approach wrong?

#include <nanoflann.hpp>
using namespace nanoflann;

#include "KDTreeVectorOfVectorsAdaptor.h"

#include <ctime>
#include <cstdlib>
#include <iostream>

const int SAMPLES_DIM = 128;

typedef std::vector<std::vector<float>> my_vector_of_vectors_t;


void generateRandomPointCloud(my_vector_of_vectors_t& samples,
                              const size_t N = 1e7,
                              const size_t dim = 128,
                              const float max_range = 1.0)
{
	std::cout << "Generating " << N << " random points...";
	samples.resize(N);
	for (size_t i = 0; i < N; i++)
	{
		samples[i].resize(dim);
		for (size_t d = 0; d < dim; d++)
			samples[i][d] = max_range * (rand() % 1000) / (1000.0);
	}
	std::cout << "done\n";
}

void kdtree_demo(const size_t nSamples = 1e7, const size_t dim = 128)
{
	my_vector_of_vectors_t samples;

	const float max_range = 1.0;

	// Generate points:
	generateRandomPointCloud(samples, nSamples, dim, max_range);

	// Query point:
	std::vector<float> query_pt(dim);
	for (size_t d = 0; d < dim; d++)
		query_pt[d] = max_range * (rand() % 1000) / (1000.0);

	// construct a kd-tree index:
	// Dimensionality set at run-time (default: L2)
	// ------------------------------------------------------------
	std::cout << "Constructing Kd Tree" << std::endl;
	typedef KDTreeVectorOfVectorsAdaptor<my_vector_of_vectors_t, float> my_kd_tree_t;
	my_kd_tree_t mat_index(dim /*dim*/, samples, 20 /* max leaf */);

	std::cout << "Building Index" << std::endl;
	mat_index.index->buildIndex();

	std::cout << "Initializing Indexes" << std::endl;
	// do a knn search
	const size_t num_results = 3;
	std::vector<size_t> ret_indexes(num_results);
	std::vector<float> out_dists_sqr(num_results);

	std::cout << "Initializing Resultset" << std::endl;
	nanoflann::KNNResultSet<float> resultSet(num_results);
	resultSet.init(&ret_indexes[0], &out_dists_sqr[0]);

	std::cout << "Starting " << std::endl;
	mat_index.index->findNeighbors(resultSet, &query_pt[0], nanoflann::SearchParams(10));

	std::cout << "knnSearch(number or results=" << num_results << "): \n";
	for (size_t i = 0; i < num_results; i++)
		std::cout << "ret_index[" << i << "]=" << ret_indexes[i] << " out_dist_sqr=" << out_dists_sqr[i] << std::endl;
}

int main()
{
	// Randomize Seed
	srand(time(NULL));
	kdtree_demo(1e7 /* samples */, SAMPLES_DIM /* dim */);
}

I am interested in using KDTreeEigenMatrixAdaptor. I have a problem in running some example files (in particular matrix_example.cpp and vector_of_vectors_example.cpp ). They compile nicely, but they give the following run time error.

terminate called after throwing an instance of 'std::logic_error'
what(): Try to change the size of a std::array

Any suggestions? Thank you.

While studying the nanoflann.hpp I stumbled over a piece of code I don't understand. More specifically the middleSplit_ function and in there following lines (1114-1126):

cutfeat = 0;
for (int i=0; i<(DIM>0 ? DIM : dim); ++i) {
    ElementType span = bbox[i].high-bbox[i].low;
    if (span>(1-EPS)*max_span) {
        ElementType min_elem, max_elem;
        computeMinMax(ind, count, cutfeat, min_elem, max_elem);
        ElementType spread = max_elem-min_elem;;
        if (spread>max_spread) {
            cutfeat = i;
	    max_spread = spread;
        }
    }
}

Why does the call to computeMinMax get cutfeat as the split axis? Note that for the first i for which span > (1-eps) * max_span, cutfeat will be set to i. After that however computeMinMax will always return the bounds for cutfeat and therefore the same spread effectively never triggering the innermost if again.

So if I am right cutfeat will always be the first i for which the outermost if is true, not the i maximizing spread. Notice also that in practice this would only lead to inefficient, not wrong results since cutfeat is still maximizing the bounding box spread as a heuristic. The obvious fix being to use i rather than cutfeat in the computeMinMax call.

Maybe I also overlooked something rendering this issue irrelevant. Whatever the case I will be glad for any feedback.

When nanoflann is used from a different project using CMake, the user of this project cannot use nanoflann using target_link_libraries.
In order to do this what it needs to be done is to update the CMakeLists.txt to support a more modern way of using CMake.
Specially what is missing is:

add_library(nanoflann INTERFACE)

target_include_directories(nanoflann
	INTERFACE
		$<BUILD_INTERFACE:${CMAKE_CURRENT_SOURCE_DIR}/include>
		$<INSTALL_INTERFACE:${INCLUDE_INSTALL_DIR}>/include)

And then this should be removed:
INCLUDE_DIRECTORIES(${nanoflann_SOURCE_DIR}/include)

When I try to build this project by

cmake ..
make -j4

The following error message show up:

/home/username/Downloads/nanoflann/3rdparty/libkdtree/kdtree++/kdtree.hpp: In instantiation of ‘std::ostream& KDTree::operator<<(std::ostream&, const KDTree::KDTree<3ul, triplet, std::pointer_to_binary_function<triplet, long unsigned int, double> >&)’:
/home/username/Downloads/nanoflann/3rdparty/libkdtree/examples/test_kdtree.cpp:197:16:   required from here
/home/username/Downloads/nanoflann/3rdparty/libkdtree/kdtree++/kdtree.hpp:1207:28: error: no match for ‘operator<<’ (operand types are ‘std::basic_ostream<char>’ and ‘const KDTree::_Node_base’)
       o << "meta node:   " << tree._M_header << std::endl;

Did any met same problem, or could helping me to solve this building issue?

Hi I try to estimate the time consumed in building the KDtree for NN search. In the example pointcloud_kdd_radius.cpp I add the following clock() to tick the time for 100k points. But the results are both float and double cost around 150ms to build the tree. From the figures provided in main page the performance vs leaf max size, if we use default size 10, the tree building time would be around 40ms. Can anyone help explain this issue? Did I miss something to achieve the fastest speed? Thanks.

clock_t time_3 = clock();

    // construct a kd-tree index:
    typedef KDTreeSingleIndexAdaptor<
        L2_Simple_Adaptor<num_t, PointCloud<num_t> > ,
        PointCloud<num_t>,
        3 /* dim */
        > my_kd_tree_t;

    my_kd_tree_t   index(3 /*dim*/, cloud, KDTreeSingleIndexAdaptorParams(10 /* max leaf */) );
    index.buildIndex();

clock_t time_4 = clock();
printf("buildTreeIndex Time: %f ms\n", ((float)(time_4-time_3))/CLOCKS_PER_SEC*1000);

Results of the example:

Generating 100000 point cloud...done
buildTreeIndex Time: 146.358994 ms
knnSearch(): num_results=5
idx[0]=25064 dist[0]=0.0069
idx[1]=19130 dist[1]=0.0347
idx[2]=38107 dist[2]=0.0372
idx[3]=6804 dist[3]=0.0392
idx[4]=73725 dist[4]=0.0393

radiusSearch(): radius=0.1 -> 9 matches
idx[0]=25064 dist[0]=0.0069
idx[1]=19130 dist[1]=0.0347
idx[2]=38107 dist[2]=0.0372
idx[3]=6804 dist[3]=0.0392
idx[4]=73725 dist[4]=0.0393
idx[5]=85821 dist[5]=0.0609
idx[6]=82218 dist[6]=0.0612
idx[7]=88824 dist[7]=0.0746
idx[8]=9122 dist[8]=0.0835

Generating 100000 point cloud...done
buildTreeIndex Time: 149.559006 ms
knnSearch(): num_results=5
idx[0]=612 dist[0]=0.0273
idx[1]=11864 dist[1]=0.0336
idx[2]=72817 dist[2]=0.0354
idx[3]=82734 dist[3]=0.0362
idx[4]=14155 dist[4]=0.0677

radiusSearch(): radius=0.1 -> 7 matches
idx[0]=612 dist[0]=0.0273
idx[1]=11864 dist[1]=0.0336
idx[2]=72817 dist[2]=0.0354
idx[3]=82734 dist[3]=0.0362
idx[4]=14155 dist[4]=0.0677
idx[5]=89222 dist[5]=0.0763
idx[6]=13352 dist[6]=0.0986

Hi,

When I put code like this (declare ret_matches and params inside the for loop):

for (size_t i = 0; i < num_pts; ++i) {

    const double query_pt[3] = {cloud->pts[i].x, cloud->pts[i].y, cloud->pts[i].z};

    std::vector<std::pair<size_t, double> > ret_matches;
    nanoflann::SearchParams params;
    params.sorted = false;

    const size_t num_matches = index.radiusSearch(&query_pt[0], radius, ret_matches, params);
...
}

I got a weird ret_matches for a specific query_pt[3] see below idx[6] which cause my subsequent code segfault:

query_pt(): x=1.60208 y= 0.486532 z= 13.0649
radiusSearch(): radius=0.6 -> 13 matches
idx[0]=14279 dist[0]=0.501927

radiusSearch(): radius=0.6 -> 13 matches
idx[1]=14204 dist[1]=0.469623

radiusSearch(): radius=0.6 -> 13 matches
idx[2]=14154 dist[2]=0.0159013

radiusSearch(): radius=0.6 -> 13 matches
idx[3]=14208 dist[3]=0.501593

radiusSearch(): radius=0.6 -> 13 matches
idx[4]=14159 dist[4]=0

radiusSearch(): radius=0.6 -> 13 matches
idx[5]=12428 dist[5]=0

radiusSearch(): radius=0.6 -> 13 matches
**idx[6]=9218868437227405311** dist[6]=2.22507e-308

I don't know how to solve this problem because queries of all previous points seems working perfect. And even I take this specific point out and query this single point (query_pt(): x=1.60208 y= 0.486532 z= 13.0649) it is working perfect also. So I guess this is not the query problem of specific point. Finally I solve this problem in a way up till now I don't know why: Take ret_matches and param definition out of the for loop like bellow. Now it works perfectly. Any one could tell me why? I am using nanoflann-1.2.1 version on Ubuntu14.04 64bit.

std::vector< std::pair<size_t, double> > ret_matches; 
nanoflann::SearchParams params;
params.sorted = false; 

for (size_t i = 0; i < num_pts; ++i) {

    const double query_pt[3] = {cloud->pts[i].x, cloud->pts[i].y, cloud->pts[i].z};

    const size_t num_matches = index.radiusSearch(&query_pt[0], radius, ret_matches, params);
...
}

This line:

radiusSearch(): Perform a search for the N closest points

should be:

radiusSearch(): Perform a search for the points within search_radius

I compiled the example vector_of_vectors successfully. However, I got the segment fault message before the application exited. I found that it is caused by releasing the KDTreeVectorOfVectorsAdaptor structure.
I use the code of the master branch. My OS is ubuntu 14.04. Could you give me some advises? Thanks.

the error message:

Generating 1000 random points...done
knnSearch(nn=3):
ret_index[0]=46 out_dist_sqr=476.232
ret_index[1]=869 out_dist_sqr=490.892
ret_index[2]=660 out_dist_sqr=493.263
Segment fault(core dumped)

Previous issues can be checked out here: http://code.google.com/p/nanoflann/issues/list?can=1

Currently search results are the same for radius and nearest neighbor sorts (distances and indices) but the packaging is different, making it challenging to swap search modes easily. If there is interest, and a feature addition isn't already underway, I can submit a patch to add the interface (without breaking the api).

Perhaps it would be nice to have the documenation state that the kdtree_get_distance function is only needed in case you actually use the L2_Simple_Adpator,I'im using L2 and it took me a while to figure out that that half ton of traits I needed for it is actually unnecessary.
Also i think the name L2_Simple_Adaptor suggests that my own kdtree_get_distance implementation is required to deliver a L2 distance, but AFAIK you can use any well defined distance function in there. Would User_Defined_Adaptor not be a better name for this?

There are two types of NNS query: the k-NN search and the fixed radius search. The combination of the two types yields the ranged search, i.e. the retrieval of the k NN with a given maximal distance.

According to a paper ETH published in 2012[1], it's beneficial to implement this kind of search variant in the context of point cloud registration. It's reasonable as we are only interested in those points whose distance are within a prior range to get right ICP result. As a result, we reduce the search space and get better performance.

They have implemented this search variant in libnabo.

How do you think about this feature?

[1] Elseberg, J., Magnenat, S., Siegwart, R., & Andreas, N. (2012). Comparison of nearest-neighbor-search strategies and implementations for efficient shape registration. Journal of Software Engineering for Robotics (JOSER), 3(1), 2–12.

Is KDTreeSingleIndexDynamicAdaptor::addPoints() thread safe?

When trying to use nanoflann in a windows build using cmake, find_package(nanoflann REQUIRED) reports that nanoflannConfig.cmake is not suitable due to a version error.

D:/dev/test/External/usr/local/lib/cmake/nanoflann/nanoflannConfig.cmake, version: 1.2.3 (32bit)

It happens also when I set
find_package(nanoflann 1.2.3 REQUIRED)

I'd expect to work like in linux, where it can find the corresponding nanoflann without problem even if I dont specify the version.

As a workaround, I have created a Findnanoflann.cmake which creates a nanoflann::nanoflann target.

Add support for add/remove points, with selective tree-rebuild.

At https://github.com/jlblancoc/nanoflann, these links don't work:

KD-tree look-up on a rotation group (SO2): SO2_example.cpp
KD-tree look-up on a rotation group (SO3): SO3_example.cpp

First, thanks for sharing your great code. 👍

I'm a bit confused between KDTreeSingleIndexDynamicAdaptorand KDTreeSingleIndexDynamicAdaptor_. What are the differences ?

For instance , KDTreeSingleIndexDynamicAdaptor_ supports radiusSearch but your dynamic point cloud example uses the first adaptor and a findNeighbors to simulate the radiusSearch.

Have I missed something ?

thx again

I'm doing a lot of findNeighbors (for k = 1) close to each other. The results (and tree traversal) should be pretty coherent. Is there a way to re-use the previous computation for potential speed-up? Like starting at the node where the previous nearest-neighbor is located or something?