nanoflann下载nanoflann源代码下载

nanoflann

C/C++

v1.6.2

下载

1。大约

Nanoflann是一个C ++ 11个标头库，用于构建具有不同拓扑的数据集的KD-Trees：R ² ，R ³ （点云），So（2），So（3）（3）（2D和3D旋转组）。不提供大约NN的支持。 Nanoflann不需要编译或安装。您只需要在代码中#include <nanoflann.hpp>即可。

该图书馆是Marius Muja和David G. Lowe的Flann图书馆的叉子，出生于Mrpt的儿童项目。按照原始许可条款， Nanoflann根据BSD许可分配。请使用错误，请使用“问题”按钮或叉子，然后打开拉动请求。

引用为：

 @misc{blanco2014nanoflann,
  title        = {nanoflann: a {C}++ header-only fork of {FLANN}, a library for Nearest Neighbor ({NN}) with KD-trees},
  author       = {Blanco, Jose Luis and Rai, Pranjal Kumar},
  howpublished = {url{https://github.com/jlblancoc/nanoflann}},
  year         = {2014}
}

有关项目更改的列表，请参见发行版ChangElog。

1.1。获取代码

最简单的方法：克隆此git存储库，然后将include/nanoflann.hpp文件供您使用。
Debian或Ubuntu（21.04或更新）用户可以简单地安装它：
```
$ sudo apt install libnanoflann-dev
```

MacOS用户可以与Homebrew一起安装nanoflann ：

$ brew install brewsci/science/nanoflann

或者

$ brew tap brewsci/science
$ brew install nanoflann

MacPorts用户可以使用：

$ sudo port install nanoflann

Linux用户还可以与LinuxBrew一起安装： brew install homebrew/science/nanoflann
稳定版本列表。查看Changelog

尽管不必编译Nanoflann本身，但您可以使用以下方式构建一些示例和测试：

$ sudo apt-get install build-essential cmake libgtest-dev libeigen3-dev
$ mkdir build && cd build && cmake ..
$ make && make test

1.2。 C ++ API参考

浏览doxygen文档。
重要说明：如果使用L2规范，请注意搜索半径和通过和返回的距离实际上是平方距离。

1.3。代码示例

kd-tree查找使用knnSearch()和radiusSearch() ：pointcloud_kdd_radius.cpp
kd-tree查找点云数据集：pointcloud_example.cpp
动态点云数据集上的KD-Tree查找：Dynamic_pointCloud_example.cpp
旋转组（SO2）上的KD-Tree查找：SO2_EXAMPLE.CPP
旋转组（SO3）上的KD-Tree查找：SO3_EXAMPLE.CPP
带有外部适配器类的点云数据集上的KD-Tree查找：PointCloud_adaptor_example.cpp
kd-tree直接在Eigen::Matrix<> ：matrix_example.cpp上查找
直接在std::vector<std::vector<T> >或std::vector<Eigen::VectorXd> ：vector_of_of_vectors_example.cpp上的KD-Tree查找
示例通过pkg-config使用Makefile用于使用（例如，在进行“ make install”或从Ubuntu存储库中安装之后）：example_with_with_pkggconfig/
如何构建索引并将其保存到磁盘以供以后使用：saveload_example.cpp
GUI示例（需要mrpt-gui ，例如sudo apt install libmrpt-gui-dev ）：
- nanoflann_gui_example_r3

Nanoflann-Demo-1

1.4。为什么要叉？

执行时间效率：
- 原始flann库的力量来自于在不同的ANN算法之间进行选择的可能性。这种灵活性的成本是声明纯虚拟方法，在某些情况下（在某些情况下）施加了运行时罚款。在nanoflann中，所有这些虚拟方法都被奇怪的重复模板模式（CRTP）和内线方法的组合所取代，这些方法快得多。
- 对于radiusSearch() ，无需打电话来确定半径内的点数，然后再次调用以获取数据。通过将STL容器用于输出数据，可以自动调整容器的大小。
- 用户可以（选项）通过模板参数在编译时设置问题维度，从而使编译器可以完全展开循环。
- nanoflann允许用户提供一个预先计算的数据框（如果有），以避免重新计算。
- 数据点的索引已从int转换为size_t ，在处理非常大的数据集时，它会删除限制。
内存效率： nanoflann在构建KD -TREE索引之前，没有将整个数据集的flann状矩阵，而是允许通过适配器接口直接访问您的数据，该界面必须在类中实现。

有关更多信息，请参见下面的示例或Nanoflann :: Kdtreesingleindexadaptor <>的C ++ API。

1.5。 Nanoflann可以做什么？

用单个索引构建KD树（没有随机的KD-Trees，没有近似搜索）。
快速，线程安全的查询，以查询KD-Trees上最接近的邻居。入口点是：
- nanoflann :: kdtreesingleindexadaptor <> ::knnSearch()
  - 找到num_closest最近的邻居到query_point[0:dim-1] 。它们的索引存储在结果对象中。请参阅示例用法代码。
- nanoflann :: kdtreesingleindexadaptor <> ::radiusSearch()
  - 在最大半径内找到所有邻居query_point[0:dim-1] 。输出作为对向量给出，其中第一个元素是点索引，第二个元素是相应距离。请参阅示例用法代码。
- nanoflann :: kdtreesingleindexadaptor <> ::radiusSearchCustomCallback()
  - 可用于接收范围中发现的每个点的回调。在某些情况下，这可能更有效，而不是与结果建立大量的对矢量。
使用2D和3D点云或N维数据集。
直接与Eigen::Matrix<>类（矩阵和向量向量）一起工作。
使用动态点云，而无需重建整个KD-Tree索引。
使用距离指标：
- R^N ：欧几里得空间：
  - L1 （曼哈顿）
  - L2 （平方欧几里得规范，有利于SSE2优化）。
  - L2_Simple （对于诸如点云之类的低维数据集，平方的欧几里得规范）。
- SO(2) ：2D旋转组
  - metric_SO2 ：绝对角度差异。
- SO(3) ：3D旋转组（以后发行中提供更好的支持）
  - metric_SO3 ：四元组之间的内部产品。
保存并加载内置索引到磁盘。
基于GUI的支持对多个KD-Tree库，即Nanoflann，Flann，Fastann和Libkdtree。

1.6。 Nanoflann不能做什么？

除了L1，L2，SO2和SO3外，请使用其他距离指标。
支持SE（3）组。
仅存在C ++接口：不支持C，Matlab或Python。
没有自动算法配置（如原始Muja＆Lowe的纸张中所述）。

1.7。通过CMAKE在您的项目中使用

您可以将nanoflann.hpp文件直接放入项目中。另外，也可以使用CMAKE标准方法：

构建并“安装”纳米兰恩。将CMAKE_INSTALL_PREFIX设置为适当的路径，然后执行make install （Linux，OSX）或构建INSTALL目标（Visual Studio）。
然后，将类似的内容添加到您项目的CMake脚本中：

 # Find nanoflannConfig.cmake:
find_package (nanoflann)

add_executable (my_project test .cpp)

# Make sure the include path is used:
target_link_libraries (my_project nanoflann::nanoflann)

1.8。包装经理

使用`conan`

您可以为nanoflann安装预构建的二进制文件，也可以使用柯南从源构建它。使用以下命令安装最新版本：

$ conan install --requires= " nanoflann/[*] " --build=missing

有关如何使用柯南的详细说明，请参考柯南文档。

nanoflann Conan食谱由Conan维护者和社区贡献者保持最新状态。如果该版本已过时，请在ConancentErindex存储库上创建问题或提取请求。

使用`vcpkg`

您可以使用VCPKG依赖项管理器下载并安装Nanoflann：

$ git clone https://github.com/Microsoft/vcpkg.git
$ cd vcpkg
$ ./bootstrap-vcpkg.sh
$ ./vcpkg integrate install
$ ./vcpkg install nanoflann

Microsoft团队成员和社区贡献者保持最新的VCPKG Nanoflann端口。如果该版本已过时，请在VCPKG存储库上创建问题或拉出请求。

1.9。编译时间定义

NANOFLANN_FIRST_MATCH ：如果定义并且两个点具有相同的距离，则最低点的距离将首先返回。否则就没有特定的顺序。
NANOFLANN_NO_THREADS ：如果定义，将禁用多线程功能，以便可以使用库而无需与pthreads链接。如果一个人试图使用多个线程，则将抛出一个例外。

2。选择KD-Tree参数有任何帮助吗？

2.1。 `KDTreeSingleIndexAdaptorParams::leaf_max_size`

kd-tree是...好吧，一棵树:-)。因此，它具有一个根节点，一组中间节点，最后是“叶”节点，即没有孩子的那些节点。

点（或正确的是点索引）仅存储在叶节点中。每个叶子都包含一个列表，其中哪个点属于其范围内。

在建造树时，节点会递归分配，直到内部的点数相等或低于某个阈值。那就是leaf_max_size 。在进行查询时，“树算法”结束了结束，然后选择叶子节点，然后对叶子中所有的查询最接近的查询进行线性搜索（一对一）。

因此，必须将leaf_max_size设置为权衡：

较大的值意味着将树木建造得更快（因为树将较小），但是每个查询都会较慢（因为叶片中的线性搜索要在更多点上进行）。
小值会构建树的速度慢得多（会有很多树节点），但是查询将更快……最高的一点，因为搜索的“树零件”（对数复杂性）仍然具有很大的成本。

选择什么数字真正取决于应用程序，甚至取决于处理器缓存内存的大小，因此理想情况下，您应该做一些基准测试以最大化效率。

但是，为了帮助选择良好的经验价值，我提供以下两个基准。每个图代表不同leaf_max_size值1至10K之间的树的构建（水平）和查询（垂直）时间（作为对数尺度的95％不确定性椭圆形，变形）。

100K点云，均匀分布（每个点都有（x，y，z） float坐标）：

来自真实数据集的〜150K点云（ scan_071_points.dat ，来自弗雷堡校园360数据集，每个点都有（x，y，z） float坐标）：

因此，在查询成本主导（例如ICP）的应用中， leaf_max_size在10到50之间是最佳的。目前，其默认值为10。

2.2。 `KDTreeSingleIndexAdaptorParams::checks`

该参数在nanoflann中确实被忽略了，但是保留了与原始Flann接口的向后兼容。只是忽略它。

2.3。 `KDTreeSingleIndexAdaptorParams::n_thread_build`

此参数确定在KD树构造过程中可以同时调用的最大线程数。默认值为1。当将参数设置为0时， nanoflann自动确定要使用的线程数。

请参阅此拉的请求，以表明使用最大线程数并不总是最有效的方法。对您的数据进行基准测试！

3。性能

3.1。 `nanoflann` ：更快，更少的内存使用

请参阅“为什么要叉？”上面的部分是nanoflann背后的主要优化思想。

请注意， nanoflann中没有明确的SSE2/SSE3优化，但是在实践中inline和模板的大量用法变成了编译器生成的自动SSE优化代码。

3.2。基准：原始`flann` vs `nanoflann`

许多点云算法（例如ICP）中最耗时的部分是向最近的邻居查询KD-Tree。因此，此操作是最关键的时间。

nanoflann相对于原始flann实施提供了约50％的节省时间（此图表中的时间为每个查询的微秒）：

尽管大部分收益来自查询（由于在任何典型操作中使用点云的数量大量），但由于构建KD-Tree索引时，还可以节省一些时间，这是由于模板化的代码，也可以避免在辅助Matrix中重复数据（在下一张图表中，在毫秒中是在毫秒中）

这些性能测试仅代表我们的测试。如果您想重复它们，请以完整的测试阅读说明

4。其他KD-Tree项目

Flann -Marius Muja和David G. Lowe（不列颠哥伦比亚大学）。
Fastann -James Philbin（牛津大学VGG）。
Ann -David M. Mount和Sunil Arya（马里兰大学）。
libkdtree ++ -Martin F. Krafft等。

注意：项目徽标是由于Cedarsed引起的

贡献者

展开

附加信息

版本 v1.6.2
类型 C/C++
更新时间 2025-03-14
大小 594.45KB
来自于 Github

nanoflann

1。大约

1.1。获取代码

1.2。 C ++ API参考

1.3。代码示例

1.4。为什么要叉？

1.5。 Nanoflann可以做什么？

1.6。 Nanoflann不能做什么？

1.7。通过CMAKE在您的项目中使用

1.8。包装经理

使用`conan`

使用`vcpkg`

1.9。编译时间定义

2。选择KD-Tree参数有任何帮助吗？

2.1。 `KDTreeSingleIndexAdaptorParams::leaf_max_size`

2.2。 `KDTreeSingleIndexAdaptorParams::checks`

2.3。 `KDTreeSingleIndexAdaptorParams::n_thread_build`

3。性能

3.1。 `nanoflann` ：更快，更少的内存使用

3.2。基准：原始`flann` vs `nanoflann`

4。其他KD-Tree项目

DragonBonesCPP

Beeftext

networkit

TensorflowASR

libjson rpc cpp

PEGTL

chat.petals.dev

GPT Prompt Templates

GPTyped

DragonBonesCPP

Beeftext

networkit

Google Dorks

shepherd

mongo express

nanoflann

1。大约

1.1。获取代码

1.2。 C ++ API参考

1.3。代码示例

1.4。为什么要叉？

1.5。 Nanoflann可以做什么？

1.6。 Nanoflann不能做什么？

1.7。通过CMAKE在您的项目中使用

1.8。包装经理

使用conan

使用vcpkg

1.9。编译时间定义

2。选择KD-Tree参数有任何帮助吗？

2.1。 KDTreeSingleIndexAdaptorParams::leaf_max_size

2.2。 KDTreeSingleIndexAdaptorParams::checks

2.3。 KDTreeSingleIndexAdaptorParams::n_thread_build

3。性能

3.1。 nanoflann ：更快，更少的内存使用

3.2。基准：原始flann vs nanoflann

4。其他KD-Tree项目

使用`conan`

使用`vcpkg`

2.1。 `KDTreeSingleIndexAdaptorParams::leaf_max_size`

2.2。 `KDTreeSingleIndexAdaptorParams::checks`

2.3。 `KDTreeSingleIndexAdaptorParams::n_thread_build`

3.1。 `nanoflann` ：更快，更少的内存使用

3.2。基准：原始`flann` vs `nanoflann`