kdtree c语言库-C语言-盈思创科技

如何选择？

库	语言	难度	性能	主要特点	推荐度
nanoflann	C/C++	⭐ (非常简单)	⭐⭐⭐⭐⭐	单头文件，纯C API，功能全面	⭐⭐⭐⭐⭐ (首选)
libkdtree++	C++	⭐⭐	⭐⭐⭐⭐	C++ 专用，Adaptor 模式	⭐⭐⭐⭐ (纯C++项目)
FLANN	C/C++	⭐⭐⭐	⭐⭐⭐⭐	算法多，支持近似搜索，适合高维	⭐⭐⭐ (高维近似搜索)

总结建议:

如果你想在 C 项目中使用，或者想最简单快捷地集成一个高性能的 KD-Tree，直接选择 nanoflann,它几乎完美地满足了所有需求。
如果你的项目是 C++，并且希望使用一个纯粹的、设计良好的 C++ 库，可以考虑 libkdtree++。
如果你的数据维度非常高（图像特征描述子），并且不追求 100% 精确的最近邻，而是追求极致的查询速度，FLANN 是更好的选择。

nanoflann C 语言使用示例

下面是一个使用 nanoflann 进行最近邻搜索的完整 C 语言示例。

步骤 1: 获取库

从 GitHub 克隆或下载 nanoflann 库。

git clone https://github.com/jlblancoc/nanoflann.git

你只需要将 nanoflann.hpp 这个文件复制到你的项目目录中即可。

步骤 2: 编写 C 代码

创建一个名为 kdtree_example.c 的文件。

#include <stdio.h>
#include <stdlib.h>
// 包含 nanoflann 的单头文件
// 注意：文件名是 .hpp，但 C 编译器可以处理
#include "nanoflann.hpp"
// 定义点的维度
const int DIM = 2;
// 使用 nanoflann 的 KDTreeSingleIndexAdaptor 模板
// 我们需要定义一个“数据集”类来包装我们的数据点
// nanoflann 会调用这个类的 kdtree_get_point_coord 方法来获取点的坐标
struct PointCloud {
    // 存储点的数据
    std::vector<double> pts;
    // 返回点的数量
    inline size_t kdtree_get_point_count() const { return pts.size() / DIM; }
    // 返回第 idx 个点的第 dim 个坐标
    inline double kdtree_get_point_coord(const size_t idx, const size_t dim) const {
        return pts[idx * DIM + dim];
    }
    // 必须的，但这里我们不需要使用它
    template <class BBOX>
    bool kdtree_get_bbox(BBOX& /* bb */) const {
        return false;
    }
};
// 定义一个 C 风格的函数，以便从纯 C 代码中调用
void find_nearest_neighbor() {
    printf("--- nanoflann C Example ---\n");
    // 1. 准备数据
    PointCloud cloud;
    // 添加一些 2D 点 (x, y)
    cloud.pts = {1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0};
    // 2. 创建 KD-Tree 索引
    // 参数: 数据点维度, 数据集对象, 建树参数 (这里使用默认)
    typedef nanoflann::KDTreeSingleIndexAdaptor<nanoflann::L2_Simple_Adaptor<double, PointCloud>, PointCloud, DIM> my_kd_tree_t;
    my_kd_tree_t index(DIM, cloud, nanoflann::KDTreeSingleIndexAdaptorParams(10 /* max leaf */) );
    // 3. 构建树
    index.buildIndex();
    // 4. 执行最近邻搜索
    double query_pt[DIM] = {4.1, 5.2}; // 我们要查找的点
    size_t num_results = 1;           // 要查找的最近邻数量
    size_t ret_index;                 // 存储找到的点的索引
    double out_dist_sqr;              // 存储找到的点的距离平方
    // 执行搜索
    // 参数: 查询点, 结果数量, 输出索引, 输出距离, 搜索选项
    nanoflann::KNNResultSet<double> resultSet(num_results);
    resultSet.init(&ret_index, &out_dist_sqr);
    index.findNeighbors(resultSet, &query_pt[0], nanoflann::SearchParams(10));
    // 5. 打印结果
    printf("Query point: (%.2f, %.2f)\n", query_pt[0], query_pt[1]);
    printf("Found nearest neighbor at index %zu with distance squared: %f\n", ret_index, out_dist_sqr);
    printf("Nearest neighbor point: (%.2f, %.2f)\n", 
           cloud.pts[ret_index * DIM + 0], 
           cloud.pts[ret_index * DIM + 1]);
}
// 注意：上面的示例使用了 C++ 的 std::vector。
// 如果你想完全避免 C++ 特性，你需要手动管理内存，并提供一个 C 风格的回调函数来获取点坐标。
// 但对于绝大多数情况，在 C 代码中混合使用 std::vector 是完全可以接受的，因为它大大简化了代码。
int main() {
    find_nearest_neighbor();
    return 0;
}

步骤 3: 编译

你需要一个 C++ 编译器来编译这个文件，因为 nanoflann 是用 C++ 实现的，即使你的代码是 .c 文件，编译器也需要理解 C++ 语法。

使用 GCC 或 Clang 进行编译：

# g++
g++ -std=c++11 -I. kdtree_example.c -o kdtree_example
# clang++
clang++ -std=c++11 -I. kdtree_example.c -o kdtree_example

-std=c++11: nanoflann 需要 C++11 或更高版本。
-I.: 告诉编译器在当前目录下查找头文件（如果你的 nanoflann.hpp 。
kdtree_example.c: 你的源文件。
-o kdtree_example: 输出的可执行文件名。

步骤 4: 运行

./kdtree_example

预期输出:

--- nanoflann C Example ---
Query point: (4.10, 5.20)
Found nearest neighbor at index 1 with distance squared: 1.000000
Nearest neighbor point: (3.00, 4.00)

(注意：根据你的点和库版本，索引可能会有所不同，但距离应该是正确的)。

这个例子展示了如何在 C 程序中无缝地使用 nanoflann 库，对于更复杂的需求，如动态添加点或范围搜索，可以参考 nanoflann 的官方文档。

kdtree c语言库

推荐的 C 语言 KD-Tree 库

nanoflann (强烈推荐)

libkdtree++

FLANN (Fast Library for Approximate Nearest Neighbors)