Before they were installed into: `` lib/cmake/nanoflann/nanoflannConfig.cmake lib/cmake/nanoflann/nanoflannConfigVersion.cmake lib/cmake/nanoflann/nanoflannTargets.cmake libdata/pkgconfig/nanoflann.pc

Now they are installed into:

share/cmake/nanoflann/nanoflannConfig.cmake share/cmake/nanoflann/nanoflannConfigVersion.cmake share/cmake/nanoflann/nanoflannTargets.cmake share/pkgconfig/nanoflann.pc

pkg-config doesn't find nanoflann. cmake files that are installed by nanoflann into share/cmake are the only application specifix cmake files there, so this appears to be a wrong location too.

Hi, I'm using nanoflann to construct a class called KdTreeFLANN in order to replace pcl::KdTreeFLANN. It is almost the same as the practice in https://github.com/laboshinl/loam_velodyne. It is based on nanoflann::KDTreeSingleIndexAdaptor, so it can't add/remove points dynamicly. Then I noticed nanoflann::KDTreeSingleIndexDynamicAdaptor which support add/remove points.So I change my class to support adding points dynamicly by nanoflann::KDTreeSingleIndexDynamicAdaptor. However, I found that it consumes about 2.5x time compared with the one before changing using the same point cloud data. Is it common or am I missing something or using anying wrongly?

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.

It seems clang doesn't like variadic args after default values.

In file included from /Users/ajx/Repos/kmeans/build/nanoflann/examples/pointcloud_custom_metric.cpp:32:
/Users/ajx/Repos/kmeans/build/nanoflann/include/nanoflann.hpp:1344:70: error: missing default argument on parameter 'args'
        const KDTreeSingleIndexAdaptorParams& params = {}, Args&&... args)
                                                                     ^
/Users/ajx/Repos/kmeans/build/nanoflann/examples/pointcloud_custom_metric.cpp:102:18: note: in instantiation of function template specialization
      'nanoflann::KDTreeSingleIndexAdaptor<My_Custom_Metric_Adaptor<double, PointCloud<double>, double, unsigned int>, PointCloud<double>, 3,
      unsigned int>::KDTreeSingleIndexAdaptor<const double &>' requested here
    my_kd_tree_t index(3 /*dim*/, cloud, {10 /* max leaf */}, myMetricParam);

I'm using

clang++ --version                                                                                                                          (base) 
Apple clang version 12.0.0 (clang-1200.0.32.29)
Target: x86_64-apple-darwin19.6.0
Thread model: posix
InstalledDir: /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin

I recently encountered issues when trying to incorporate this library into an SPH code, and in trying to debug (The reason for the debug is also dubious: I realised I had to search the square of the radius I was interested in), I created some duplicate points. When I try to perform a radius search on one of the points, the library gives a segmentation fault. Whilst it's perhaps bad to have duplicate points in the space, it is possible in SPH simulations to have points overlap (normally when the simulation goes berserk), and I don't feel it's a robust handling of what is likely a common scenario. Surely the library should return it as any other neighbour, with a distance of 0.0. I am using the KDTreeVectorofVectorsAdaptor for a std::vectorEigen::Vector2d data structure, should that have any influence.

in the constructor of KDTreeSingleIndexAdaptor, you expect inputData lifetime should be longer rather then Adaptor itself, but it is not always true and user of the code can easily break it.

    KDTreeSingleIndexAdaptor(
        const Dimension dimensionality, const DatasetAdaptor& inputData,
        const KDTreeSingleIndexAdaptorParams& params = {}, Args&&... args)
        : dataset(inputData),
          index_params(params),
          distance(inputData, std::forward<Args>(args)...)
    {

for exmple, calling this would cause indefined behaviour:
ModelKDTreeIndex index(2, std::vector {}, nanoflann::KDTreeSingleIndexAdaptorParams(10));

Would it be possible to replace the m_indices_dists container within RadiusResultSet of type std::vector<std::pair<IndexType, DistanceType>> with something that interoperates better with C? Currently, any attempt to use nanoflann from a language other than C++ will probably have to make a copy of the results.

The KNNResultSet is much easier to interoperate with since it simply uses two arrays as storage, i.e.

    IndexType*    indices;
    DistanceType* dists;

One can easily pass a contiguous array from C, Python, or Fortran.

I understand the motivation for using std::vector because in the radius search we generally don't know the number of points that will be found in a query, hence the need for a dynamic container. One simple solution would be to simply replace std::pair with a struct:

struct { 
IndexType idx; 
DistanceType dist;
};

Then we can recover a C-interoperable array of structs via m_indices_dists.data().

Hi,

I have attempted to use nanoflann for data structures where the access to the elements is not provided using indexes of integral types, or more efficiently provided by other accessors. While doing so I have found certain issues, most of which arose due to mixing up the type of the values stored in KDTreeBaseClass::vind and the type with which vind is accessed.

In many places this worked fine, as the values stored in vind were typically of integral types well, since they are used to quantify indices in an array or a similar data structure. However, with these fixes nanoflann can be used with data structures that provide access to its elements using other types of accessors (such as pointers for example).

Here is a quick summary of the changes:

• Metrics adaptors (L1_Adaptor, L2_Adaptor, ...) did not have a template parameter for IndexType. They expected b_idx to be of size_t, and by doing so casted implicitly to size_t, if possible.
• In several places, IndexType was used to store the location in vind in which the IndexType is stored, whereas the type for the argument of std::vector<IndexType>::operator[] has nothing to do with IndexType itself. E.g. KDTreeBaseClass::Node::node_type, KDTreeBaseClass::divideTree.
• Since the argument of std::vector<IndexType>::operator[] is not a template parameter, uint64_t was used
• As the IndexType is not necessarily an index, I renamed it to AccessorType.

I built and ran all tests as well as the examples (all build targets), each of which passed.

I hope you find these changes useful and will merge them into your repository. If there is anything that I should change, don't hesitate to let me know.

This pull request addresses issue #96.

When working with MSVC, _USE_MATH_DEFINES must be defined before the first inclusion of <cmath> for M_PI to be available for use. This requirement is problematic for projects that use <cmath> as the first inclusion of <cmath> isn't always obvious or easy to track down and defining _USE_MATH_DEFINES globally leads to redefinition warnings. This commit addresses the issue by replacing all uses of M_PI with a constexpr value for pi defined in the nanoflann namespace.

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;
                         ^

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?

Hello, I wonder if there is a way to completely remove point instead of just recording its index as "-1", otherwise the memory usage will increase over time.

Does nanoflann have any facilities for finding all points within a box? To give a 2D example, we may be looking to list all $(x,y)$ points so that $x \in [x_1, x_2]$ and $y \in [y_1, y_2]$.

Motivation: If my understanding of $k$-d trees is correct, the natural way to search is precisely in a box. My application requires listing all points within a given region of a non-trivial shape. I can determine the bounding box of this region, so one approach is to list all points within the box, then test each of these points for inclusion within the region. With radiusSearch, I can implement the same approach, but use a bounding disk instead of a bounding box. However, if the underlying mechanism operates with a bounding box anyway, I am wondering if using boxes would be faster. My shape tends to be long and narrow, and when it happens to be aligned with the axes, the area of its bounding box will be much smaller than that of its bounding disk. This translates into having to test fewer points.

Hi thanks for the great work. I encountered a potential bug within the lib. I want to filter my point cloud based on how many Neighbors a point has. For this i firstly used the PCL kdTreeFLANN implementation (see if flann_lib_ == 0). In comparison i wanted to try your Implementation (see if flann_lib_==1). To bring first things out of the way, i think i am right with squaring the radius in your library in comparison to the pcl implementation?

if(flann_lib_ == 0){
    // init. kd search tree
    KdTreePtr kd_tree_(new pcl::KdTreeFLANN<pcl::PointXYZI>());
    kd_tree_->setInputCloud(input_cloud);
    // Go over all the points and check which doesn't have enough neighbors
    // perform filtering
    for (pcl::PointCloud<pcl::PointXYZI>::iterator it = input_cloud->begin();
        it != input_cloud->end(); ++it) {
      float x_i = it->x;
      float y_i = it->y;
      double intes = it->intensity;
      float range_i = sqrt(pow(x_i, 2) + pow(y_i, 2));
      float search_radius_dynamic =
          radius_multiplier_ * azimuth_angle_ * 3.14159265359 / 180 * range_i;
          
      if (search_radius_dynamic < min_search_radius_) {
        search_radius_dynamic = min_search_radius_;
      }

      std::vector<int> pointIdxRadiusSearch;
      std::vector<float> pointRadiusSquaredDistance;
      if (intensity_ && intes > th_intensity_){
        filtered_cloud.push_back(*it);
      }else{
        int neighbors =
          kd_tree_->radiusSearch(*it, search_radius_dynamic, pointIdxRadiusSearch,
                                pointRadiusSquaredDistance,min_neighbors_);
        if (neighbors >= min_neighbors_) { filtered_cloud.push_back(*it);}
      }
    }
  }
  else if(flann_lib_ == 1) {
    // init. kd search tree
    nanoflann::KdTreeFLANN<pcl::PointXYZI> kd_tree_flann_;
    kd_tree_flann_.setInputCloud(input_cloud);

    for (pcl::PointCloud<pcl::PointXYZI>::iterator it = input_cloud->begin();
        it != input_cloud->end(); ++it) {
      float x_i = it->x;
      float y_i = it->y;
      double intes = it->intensity;
      float range_i = sqrt(pow(x_i, 2) + pow(y_i, 2));
      float search_radius_dynamic =
          radius_multiplier_ * azimuth_angle_ * 3.14159265359 / 180 * range_i;
          
      if (search_radius_dynamic < min_search_radius_) {
        search_radius_dynamic = min_search_radius_;
      }

      std::vector<int> pointIdxRadiusSearch;
      std::vector<float> pointRadiusSquaredDistance;
      if (intensity_ && intes > th_intensity_){
        filtered_cloud.push_back(*it);
      }else{
        int neighbors =
          kd_tree_flann_.radiusSearch(*it, pow(search_radius_dynamic,2), pointIdxRadiusSearch,
                                pointRadiusSquaredDistance);
        if (neighbors >= min_neighbors_) { filtered_cloud.push_back(*it);}
      }
    }
  }

For both implementations i made a short video of a visualization of the output point cloud via Rviz. As you might noticed i have an intesity filter which overwrites the the radius Search. Thats why i colored the pointcloud based on the intensity. Yellow points are put through with the intensity filter and red points are the points which have not enough intensity and are filtered by the radius search. PCL Implementation shows a consistent point cloud output https://www.youtube.com/watch?v=a8EuP8oOWDg

With the NanoFlann implementation the red points are "flickering" in some point cloud outputs there are included in some not. And within this flicker it is also not consistent and there are some strange "sharp" edges which look as a dimension filter would be applied. The fuction returns 0 as a result for found Neighbors in the flicker cases. https://youtu.be/AOaBHOvWsnI

Actually i don't have an idea what could cause this behavior maybe you have an idea. First i saw this on the commit from April updated the code to the current commit and in both cases this happens.

Greets Sven

Hey thanks for the great project! I am wondering if there is any easy way (or forked project) to enable parallelism for KD-Tree construction with nanoflann? Or do you have plans to integrate this feature in the future?

inline bool addPoint(DistanceType dist, IndexType index) { CountType i; for (i = count; i > 0; --i) { #ifdef NANOFLANN_FIRST_MATCH // If defined and two points have the same // distance, the one with the lowest-index will be // returned first. if ((dists[i - 1] > dist) || ((dist == dists[i - 1]) && (indices[i - 1] > index))) { #else if (dists[i - 1] > dist) { #endif if (i < capacity) { dists[i] = dists[i - 1]; indices[i] = indices[i - 1]; } } else break; } if (i < capacity) { dists[i] = dist; indices[i] = index; } if (count < capacity) count++;

// tell caller that the search shall continue
return false;
// return true; 

}

if i turn it to false, time cost reduced , but result poor, but if it to true, result quality going up but time cost increased.

can you explain why??