16.2 k-d 树与正交树（Orthtree） §

相关章节 §

• 16.1 AABB 树
• 16.3 空间搜索结构
• 16.4 盒相交与区间跳表
• 14.1 网格处理基础

16.2.1 理论基础 §

k-d 树概述 §

k-d 树（k-dimensional tree）是一种空间分割数据结构，用于组织 k 维空间中的点。它由 Bentley 于 1975 年提出，是二叉空间分割树的一种特例。

核心特性：

• 维度循环分割：在每一层递归中，沿不同维度进行分割
• 中位点分割：通常选择中位点作为分割平面，保证树的平衡
• 点存储：叶节点存储实际数据点
• 灵活查询：支持范围查询、最近邻查询等多种操作

分割策略：

1. 中位数分割（Median）：选择中位点，保证平衡但可能需要排序
2. 中点分割（Midpoint）：选择包围盒中心，可能产生空节点
3. 滑动中点（Sliding Midpoint）：中点分割的改进，避免空节点
4. 公平分割（Fair/Sliding Fair）：考虑数据分布的分割策略

正交树（Orthtree）概述 §

正交树是 k-d 树的推广，每个节点可以有 2^d 个子节点（d 为维度）。四叉树（Quadtree，2D）和八叉树（Octree，3D）是正交树的特例。

核心特性：

• 规则网格分割：每个节点将空间均匀分割为 2^d 个子区域
• 自适应细分：根据数据分布动态决定细分深度
• 层次坐标系统：使用全局和局部坐标标识节点位置
• 邻接查询：支持高效的邻接节点查找

应用场景：

• 点云数据组织与查询
• 空间哈希与索引
• 碰撞检测
• 图像处理与计算机图形学

16.2.2 架构分析 §

k-d 树类设计 §

CGAL 的 k-d 树实现位于 Spatial_searching 模块：

Kd_tree<SearchTraits, Splitter, UseExtendedNode, EnablePointsCache>
Kd_tree_node<SearchTraits, Splitter, UseExtendedNode, EnablePointsCache>
Kd_tree_leaf_node<...>
Kd_tree_internal_node<...>
Plane_separator<FT>

Kd_tree 类（位于 /home/chunibyo/workspace/osc/cgal/Spatial_searching/include/CGAL/Kd_tree.h） §

template <
    class SearchTraits,
    class Splitter_ = Sliding_midpoint<SearchTraits>,
    class UseExtendedNode = Tag_true,
    class EnablePointsCache = Tag_false>
class Kd_tree {
public:
    typedef SearchTraits Traits;
    typedef Splitter_ Splitter;
    typedef typename SearchTraits::Point_d Point_d;
    typedef typename Splitter::Container Point_container;
    typedef typename SearchTraits::FT FT;
    typedef Kd_tree_node<SearchTraits, Splitter, UseExtendedNode, EnablePointsCache> Node;
    typedef Kd_tree_leaf_node<...> Leaf_node;
    typedef Kd_tree_internal_node<...> Internal_node;
    
    // 构造函数
    Kd_tree(Splitter s = Splitter(), const SearchTraits traits = SearchTraits());
    
    template <class InputIterator>
    Kd_tree(InputIterator first, InputIterator beyond, 
            Splitter s = Splitter(), const SearchTraits traits = SearchTraits());
    
    // 构建树
    void build();
    template <typename ConcurrencyTag> void build();
    
    // 查询
    template <class OutputIterator, class FuzzyQueryItem>
    OutputIterator search(OutputIterator it, const FuzzyQueryItem& q) const;
    
    template <class FuzzyQueryItem>
    std::optional<Point_d> search_any_point(const FuzzyQueryItem& q) const;
    
    // 插入和删除
    void insert(const Point_d& p);
    template <class InputIterator> void insert(InputIterator first, InputIterator beyond);
    void remove(const Point_d& p);
    
    // 统计信息
    std::ostream& statistics(std::ostream& s) const;
};

节点类层次结构（位于 /home/chunibyo/workspace/osc/cgal/Spatial_searching/include/CGAL/Kd_tree_node.h） §

// 基类
template <class TreeTraits, class Splitter, class UseExtendedNode, class EnablePointsCache>
class Kd_tree_node {
    bool leaf;  // 是否为叶节点
public:
    bool is_leaf() const { return leaf; }
    
    // 搜索方法
    template <class OutputIterator, class FuzzyQueryItem>
    OutputIterator search(OutputIterator it, const FuzzyQueryItem& q,
                          Kd_tree_rectangle<FT,D>& b, ...) const;
    
    template <class FuzzyQueryItem>
    std::optional<Point_d> search_any_point(const FuzzyQueryItem& q, ...) const;
};
 
// 叶节点
template <class TreeTraits, class Splitter, class UseExtendedNode, class EnablePointsCache>
class Kd_tree_leaf_node : public Kd_tree_node<...> {
    std::int32_t n;           // 节点中点的数量
    iterator data;            // 指向数据的迭代器
public:
    unsigned int size() const { return n; }
    iterator begin() const { return data; }
    iterator end() const { return data + n; }
};
 
// 内部节点
template <class TreeTraits, class Splitter, class UseExtendedNode, class EnablePointsCache>
class Kd_tree_internal_node : public Kd_tree_node<...> {
    std::int32_t cut_dim;     // 分割维度
    FT cut_val;               // 分割值
    Node_handle lower_ch;     // 左子节点
    Node_handle upper_ch;     // 右子节点
    
    // 扩展节点额外信息
    FT upper_low_val, upper_high_val;
    FT lower_low_val, lower_high_val;
public:
    Node_const_handle lower() const { return lower_ch; }
    Node_const_handle upper() const { return upper_ch; }
    FT cutting_value() const { return cut_val; }
    int cutting_dimension() const { return cut_dim; }
};

正交树类设计 §

CGAL 的 Orthtree 实现位于 Orthtree 模块：

Orthtree<GeomTraits>
Orthtree_traits_point<GeomTraits, PointRange, PointMap, hypercubic_nodes, dimension>
Orthtree_traits_face_graph<...>
Orthtree_traits_polygons<...>

Orthtree 类（位于 /home/chunibyo/workspace/osc/cgal/Orthtree/include/CGAL/Orthtree.h） §

template <typename GeomTraits>
class Orthtree {
public:
    using Traits = GeomTraits;
    static inline constexpr bool has_data = Orthtree_impl::has_Node_data<GeomTraits>::value;
    static inline constexpr bool supports_neighbor_search = 
        Orthtree_impl::has_Squared_distance_of_element<GeomTraits>::value;
    
    static constexpr int dimension = Traits::dimension;  // 空间维度
    static constexpr int degree = (2 << (dimension - 1));  // 子节点数
    
    using Kernel = typename Traits::Kernel;
    using FT = typename Traits::FT;
    using Point = typename Traits::Point_d;
    using Bbox = typename Traits::Bbox_d;
    using Node_index = typename Traits::Node_index;
    using Local_coordinates = std::bitset<dimension>;       // 局部坐标
    using Global_coordinates = std::array<std::uint32_t, dimension>;  // 全局坐标
    
    // 构造函数
    explicit Orthtree(Traits traits);
    
    // 树构建
    void refine(const Split_predicate& split_predicate);
    auto refine(size_t max_depth = 10, size_t bucket_size = 20) -> std::enable_if_t<Orthtree::has_data, void>;
    void grade();  // 使树满足分级约束
    
    // 查询
    Node_index locate(const Point& point) const;  // 点定位
    
    template<typename OutputIterator, typename Orthtree = Self>
    auto nearest_k_neighbors(const Point& query, std::size_t k, OutputIterator output) const
        -> std::enable_if_t<Orthtree::supports_neighbor_search, OutputIterator>;
    
    template<typename OutputIterator, typename Orthtree = Self>
    auto neighbors_within_radius(const Sphere& query, OutputIterator output) const
        -> std::enable_if_t<Orthtree::supports_neighbor_search, OutputIterator>;
    
    // 节点访问
    Node_index root() const { return 0; }
    bool is_leaf(Node_index n) const;
    bool is_root(Node_index n) const;
    std::size_t depth(Node_index n) const;
    Node_index parent(Node_index n) const;
    Node_index child(Node_index n, std::size_t i) const;
    
    // 邻接查询
    std::optional<Node_index> adjacent_node(Node_index n, const Local_coordinates& direction) const;
    
    // 遍历
    template <typename Traversal>
    Node_index_range traverse(Traversal traversal) const;
};

16.2.3 实现细节 §

k-d 树构建算法 §

// 来自 Kd_tree.h
template <typename ConcurrencyTag>
void Kd_tree<...>::build()
{
    CGAL_assertion(\!is_built());
    CGAL_assertion(\!pts.empty());
    
    // 确定维度
    const Point_d& p = *pts.begin();
    dim_ = static_cast<int>(std::distance(ccci(p), ccci(p,0)));
    
    // 构建点指针数组
    data.reserve(pts.size());
    for(std::size_t i = 0; i < pts.size(); i++){
        data.push_back(&pts[i]);
    }
    
    // 创建点容器并计算包围盒
    Point_container c(dim_, data.begin(), data.end(), traits_);
    bbox = new Kd_tree_rectangle<FT,D>(c.bounding_box());
    
    // 递归构建
    if(c.size() <= split.bucket_size() || CGAL::is_zero(c.max_tight_spread())){
        tree_root = create_leaf_node(c);
    } else {
        tree_root = new_internal_node();
        create_internal_node(tree_root, c, ConcurrencyTag());
    }
    
    // 重排数据以提高空间局部性
    // ...
    built_ = true;
}
 
// 递归创建内部节点
template <typename ConcurrencyTag>
void create_internal_node(Node_handle n, Point_container& c, const ConcurrencyTag& tag)
{
    Internal_node_handle nh = static_cast<Internal_node_handle>(n);
    
    // 使用分割器创建分割平面
    Separator sep;
    Point_container c_low(c.dimension(), traits_);
    split(sep, c, c_low);  // 分割容器
    nh->set_separator(sep);
    
    // 处理扩展节点信息（可选）
    handle_extended_node(nh, c, c_low, UseExtendedNode());
    
    // 并行构建（如果启用）
    if(try_parallel_internal_node_creation(nh, c, c_low, tag))
        return;
    
    // 递归构建左子树
    if(c_low.size() > split.bucket_size() && \!CGAL::is_zero(c_low.max_tight_spread())) {
        nh->lower_ch = new_internal_node();
        create_internal_node(nh->lower_ch, c_low, tag);
    } else {
        nh->lower_ch = create_leaf_node(c_low);
    }
    
    // 递归构建右子树
    if(c.size() > split.bucket_size() && \!CGAL::is_zero(c.max_tight_spread())) {
        nh->upper_ch = new_internal_node();
        create_internal_node(nh->upper_ch, c, tag);
    } else {
        nh->upper_ch = create_leaf_node(c);
    }
}

滑动中点分割策略 §

// 来自 Splitters.h
template <class SearchTraits, class Separator_>
class Sliding_midpoint : public Splitter_base<typename SearchTraits::FT> {
public:
    void operator()(Separator& sep, Container& c0, Container& c1) const
    {
        // 选择最大跨度维度
        int cutdim = c0.max_span_coord();
        
        // 避免退化情况
        if(c0.tight_bounding_box().min_coord(cutdim) \!= 
           c0.tight_bounding_box().max_coord(cutdim)) {
            sep = Separator(cutdim, (c0.max_span_upper() + c0.max_span_lower())/FT(2));
        } else {
            cutdim = c0.max_tight_span_coord();
            sep = Separator(cutdim, 
                (c0.max_tight_span_upper() + c0.max_tight_span_lower())/FT(2));
        }
        
        // 滑动分割值到数据范围内
        FT max_span_lower = c0.tight_bounding_box().min_coord(cutdim);
        FT max_span_upper = c0.tight_bounding_box().max_coord(cutdim);
        
        if(max_span_upper <= sep.cutting_value())
            sep.set_cutting_value(max_span_upper);
        if(max_span_lower >= sep.cutting_value())
            sep.set_cutting_value(max_span_lower);
        
        c0.split(c1, sep, true);
    }
};

k-d 树搜索算法 §

// 来自 Kd_tree_node.h
template <class OutputIterator, class FuzzyQueryItem>
OutputIterator Kd_tree_node<...>::search(
    OutputIterator it, const FuzzyQueryItem& q,
    Kd_tree_rectangle<FT,D>& b, ...) const
{
    if(is_leaf()) {
        // 叶节点：检查所有点
        Leaf_node_const_handle node = static_cast<Leaf_node_const_handle>(this);
        if(node->size() > 0) {
            // 使用缓存优化或标准遍历
            it = search_in_leaf(node, q, ..., it, dummy);
        }
    } else {
        // 内部节点：递归搜索
        Internal_node_const_handle node = static_cast<Internal_node_const_handle>(this);
        
        Kd_tree_rectangle<FT,D> b_upper(b);
        node->split_bbox(b, b_upper);  // 分割包围盒
        
        // 查询完全包含左子树
        if(q.outer_range_contains(b))
            it = node->lower()->tree_items(it);
        else if(q.inner_range_intersects(b))
            it = node->lower()->search(it, q, b, ...);
        
        // 查询完全包含右子树
        if(q.outer_range_contains(b_upper))
            it = node->upper()->tree_items(it);
        else if(q.inner_range_intersects(b_upper))
            it = node->upper()->search(it, q, b_upper, ...);
    }
    return it;
}

正交树构建与细分 §

// 来自 Orthtree.h
void refine(const Split_predicate& split_predicate) {
    std::queue<Node_index> todo;
    todo.push(0);  // 从根节点开始
    
    while(\!todo.empty()) {
        auto current = todo.front();
        todo.pop();
        
        // 检查是否需要分割
        if(split_predicate(current, *this)) {
            split(current);  // 分割节点
        }
        
        // 将子节点加入队列
        if(\!is_leaf(current)) {
            for(int i = 0; i < degree; ++i)
                todo.push(child(current, i));
        }
    }
}
 
void split(Node_index n) {
    CGAL_precondition(is_leaf(n));
    
    // 创建子节点组
    m_node_children[n] = m_node_properties.emplace_group(degree);
    
    for(std::size_t i = 0; i < degree; i++) {
        Node_index c = *m_node_children[n] + i;
        
        // 计算局部坐标
        Local_coordinates local_coordinates{i};
        for(int j = 0; j < dimension; j++)
            m_node_coordinates[c][j] = (2 * m_node_coordinates[n][j]) + local_coordinates[j];
        
        m_node_depths[c] = m_node_depths[n] + 1;
        m_node_parents[c] = n;
    }
    
    // 更新深度信息
    if(depth(n) + 1 == m_side_per_depth.size()) {
        Bbox_dimensions size = m_side_per_depth.back();
        Bbox_dimensions child_size;
        for(int i = 0; i < dimension; ++i)
            child_size[i] = size[i] / FT(2);
        m_side_per_depth.push_back(child_size);
    }
    
    // 重新分配节点内容到子节点
    Point center = barycenter(n);
    if constexpr(has_data)
        m_traits.distribute_node_contents_object()(n, *this, center);
}

正交树最近邻搜索 §

// 来自 Orthtree.h
template <typename Result, typename Orthtree = Self>
auto nearest_k_neighbors_recursive(
    Sphere& search_bounds,
    Node_index node,
    std::vector<Result>& results,
    std::size_t k,
    FT epsilon = 0) const -> std::enable_if_t<Orthtree::supports_neighbor_search>
{
    if(is_leaf(node)) {
        // 叶节点：检查所有元素
        for(auto& e : data(node)) {
            Result current = {
                e, 
                m_traits.squared_distance_of_element_object()(e, 
                    m_traits.construct_center_d_object()(search_bounds))
            };
            
            if(current.distance < m_traits.compute_squared_radius_d_object()(search_bounds)) {
                if(results.size() == k)
                    results.pop_back();
                
                results.push_back(current);
                std::sort(results.begin(), results.end(), 
                    [](auto& l, auto& r) { return l.distance < r.distance; });
                
                if(results.size() == k) {
                    // 缩小搜索范围
                    search_bounds = m_traits.construct_sphere_d_object()(
                        m_traits.construct_center_d_object()(search_bounds),
                        results.back().distance + epsilon);
                }
            }
        }
    } else {
        // 内部节点：按距离排序子节点，优先访问近的
        struct Node_index_with_distance {
            Node_index index;
            FT distance;
        };
        
        std::vector<Node_index_with_distance> children_with_distances;
        children_with_distances.reserve(Self::degree);
        
        for(int i = 0; i < Self::degree; ++i) {
            auto child_node = child(node, i);
            FT squared_distance = 0;
            Point c = m_traits.construct_center_d_object()(search_bounds);
            Point b = barycenter(child_node);
            // 计算到子节点中心的距离
            for(const auto r : cartesian_range(c, b)) {
                FT d = (get<0>(r) - get<1>(r));
                squared_distance += d * d;
            }
            children_with_distances.emplace_back(child_node, squared_distance);
        }
        
        // 按距离排序
        std::sort(children_with_distances.begin(), children_with_distances.end(),
            [](auto& l, auto& r) { return l.distance < r.distance; });
        
        // 递归访问
        for(auto child_with_distance : children_with_distances) {
            if(CGAL::do_intersect(bbox(child_with_distance.index), search_bounds)) {
                nearest_k_neighbors_recursive(search_bounds, 
                    child_with_distance.index, results, k, epsilon);
            }
        }
    }
}

正交树邻接节点查找 §

// 来自 Orthtree.h
std::optional<Node_index> adjacent_node(Node_index n, const Local_coordinates& direction) const {
    CGAL_precondition(direction.to_ulong() < dimension * 2);
    
    if(is_root(n)) return {};  // 根节点无邻接节点
    
    // 解析方向
    bool sign = direction[0];  // 正负方向
    uint8_t dim = uint8_t((direction >> 1).to_ulong());  // 维度
    int8_t offset = (uint8_t)1 << dim;
    offset = sign ? offset : -offset;
    
    // 检查是否是直接兄弟节点
    if(local_coordinates(n)[dim] \!= sign) {
        return {child(parent(n), local_coordinates(n).to_ulong() + offset)};
    }
    
    // 递归查找父节点的邻接节点
    auto adjacent_node_of_parent = adjacent_node(parent(n), direction);
    if(\!adjacent_node_of_parent) return {};
    
    // 如果父节点的邻接节点是叶节点，则返回它
    if(is_leaf(*adjacent_node_of_parent))
        return adjacent_node_of_parent;
    
    // 返回对应子节点
    return {child(*adjacent_node_of_parent, local_coordinates(n).to_ulong() - offset)};
}

16.2.4 使用示例 §

示例1：k-d 树最近邻搜索 §

#include <CGAL/Simple_cartesian.h>
#include <CGAL/Kd_tree.h>
#include <CGAL/Search_traits_3.h>
#include <CGAL/Fuzzy_sphere.h>
#include <CGAL/Orthogonal_k_neighbor_search.h>
#include <vector>
#include <iostream>
 
typedef CGAL::Simple_cartesian<double> K;
typedef K::Point_3 Point;
typedef CGAL::Search_traits_3<K> Traits;
typedef CGAL::Kd_tree<Traits> Tree;
typedef CGAL::Fuzzy_sphere<Traits> Fuzzy_sphere;
 
int main()
{
    // 生成随机点
    std::vector<Point> points;
    for(int i = 0; i < 1000; ++i) {
        points.push_back(Point(
            rand() / (double)RAND_MAX,
            rand() / (double)RAND_MAX,
            rand() / (double)RAND_MAX
        ));
    }
    
    // 构建 k-d 树
    Tree tree(points.begin(), points.end());
    tree.build();
    
    // 查询点
    Point query(0.5, 0.5, 0.5);
    
    // 范围查询：查找球体内的所有点
    double radius = 0.1;
    Fuzzy_sphere sphere(query, radius);
    std::vector<Point> result;
    tree.search(std::back_inserter(result), sphere);
    
    std::cout << "在半径 " << radius << " 内找到 " 
              << result.size() << " 个点" << std::endl;
    
    // 打印统计信息
    tree.statistics(std::cout);
    
    return 0;
}

示例2：八叉树点云组织 §

#include <CGAL/Simple_cartesian.h>
#include <CGAL/Octree.h>
#include <CGAL/Orthtree_traits_point.h>
#include <vector>
#include <iostream>
 
typedef CGAL::Simple_cartesian<double> K;
typedef K::Point_3 Point;
typedef K::Sphere_3 Sphere;
 
// 定义点范围
typedef std::vector<Point> Point_range;
 
// 定义八叉树 traits
typedef CGAL::Orthtree_traits_point<K, Point_range> Traits;
typedef CGAL::Orthtree<Traits> Octree;
 
int main()
{
    // 创建点云
    Point_range points;
    for(int i = 0; i < 10000; ++i) {
        points.push_back(Point(
            rand() / (double)RAND_MAX,
            rand() / (double)RAND_MAX,
            rand() / (double)RAND_MAX
        ));
    }
    
    // 构建八叉树
    Octree octree(points);
    
    // 细化树：最大深度10，每个节点最多20个点
    octree.refine(10, 20);
    
    // 点定位
    Point query(0.5, 0.5, 0.5);
    auto node = octree.locate(query);
    std::cout << "查询点位于节点: " << node << std::endl;
    std::cout << "节点深度: " << octree.depth(node) << std::endl;
    
    // 最近邻搜索
    std::vector<Point> neighbors;
    octree.nearest_k_neighbors(query, 5, std::back_inserter(neighbors));
    
    std::cout << "5个最近邻:" << std::endl;
    for(const auto& p : neighbors) {
        std::cout << "  " << p << std::endl;
    }
    
    // 半径搜索
    Sphere search_sphere(query, 0.05);  // 半径为 sqrt(0.05)
    std::vector<Point> in_sphere;
    octree.neighbors_within_radius(search_sphere, std::back_inserter(in_sphere));
    
    std::cout << "球体内有 " << in_sphere.size() << " 个点" << std::endl;
    
    // 邻接节点查询
    auto neighbor = octree.adjacent_node(node, Octree::Adjacency(0));  // 左邻接
    if(neighbor) {
        std::cout << "左邻接节点: " << *neighbor << std::endl;
    }
    
    return 0;
}

示例3：自定义 k-d 树分割策略 §

#include <CGAL/Simple_cartesian.h>
#include <CGAL/Kd_tree.h>
#include <CGAL/Search_traits_2.h>
#include <CGAL/Splitters.h>
 
typedef CGAL::Simple_cartesian<double> K;
typedef K::Point_2 Point;
typedef CGAL::Search_traits_2<K> Traits;
 
// 使用公平分割策略
typedef CGAL::Fair<Traits> Fair_splitter;
typedef CGAL::Kd_tree<Traits, Fair_splitter> Fair_tree;
 
// 使用中位数分割策略
typedef CGAL::Median_of_max_spread<Traits> Median_splitter;
typedef CGAL::Kd_tree<Traits, Median_splitter> Median_tree;
 
int main()
{
    std::vector<Point> points = {
        Point(0, 0), Point(1, 0), Point(0, 1), Point(1, 1),
        Point(0.5, 0.5), Point(0.2, 0.8), Point(0.8, 0.2)
    };
    
    // 使用公平分割构建树
    Fair_splitter fair_split(5, 3.0);  // bucket_size=5, aspect_ratio=3
    Fair_tree fair_tree(points.begin(), points.end(), fair_split);
    fair_tree.build();
    
    // 使用中位数分割构建树
    Median_splitter median_split(5);
    Median_tree median_tree(points.begin(), points.end(), median_split);
    median_tree.build();
    
    return 0;
}

16.2.5 复杂度分析 §

k-d 树复杂度 §

操作	平均情况	最坏情况	说明
构建	O(n log n)	O(n log n)	每层需要 O(n) 的分割操作
最近邻查询	O(log n)	O(n)	取决于数据分布
k 近邻查询	O(log n + k)	O(n)	需要维护大小为 k 的优先队列
范围查询	O(log n + m)	O(n)	m 是结果数量
插入	O(log n)	O(log n)	需要重建时变为 O(n log n)
删除	O(log n)	O(log n)	惰性删除策略

空间复杂度：O(n)，每个点存储一次

正交树复杂度 §

操作	平均情况	最坏情况	说明
构建	O(n log n)	O(n h)	h 是树深度
点定位	O(h)	O(h)	h 是树深度
最近邻查询	O(log n)	O(n)	分支限界剪枝
k 近邻查询	O(log n + k log k)	O(n)	需要排序结果
邻接查询	O(h)	O(h)	递归向上再向下
细化（refine）	O(n log n)	O(n h)	取决于分割谓词

空间复杂度：O(n + 2^h)，h 是最大深度

性能比较 §

特性	k-d 树	正交树（八叉树）
适用维度	任意	任意（但通常用于低维）
子节点数	2	2^d
分割策略	数据驱动	空间驱动
平衡性	通常平衡	取决于数据分布
邻接查询	不支持	支持
内存效率	高	中等
构建速度	快	中等
最近邻查询	快	快

16.2.6 关键文件位置 §

k-d 树相关文件 §

文件	说明
/home/chunibyo/workspace/osc/cgal/Spatial_searching/include/CGAL/Kd_tree.h	k-d 树主类
/home/chunibyo/workspace/osc/cgal/Spatial_searching/include/CGAL/Kd_tree_node.h	树节点实现
/home/chunibyo/workspace/osc/cgal/Spatial_searching/include/CGAL/Splitters.h	分割策略实现
/home/chunibyo/workspace/osc/cgal/Spatial_searching/include/CGAL/Plane_separator.h	分割平面
/home/chunibyo/workspace/osc/cgal/Spatial_searching/include/CGAL/Kd_tree_rectangle.h	节点包围盒
/home/chunibyo/workspace/osc/cgal/Spatial_searching/include/CGAL/Fuzzy_sphere.h	模糊球查询
/home/chunibyo/workspace/osc/cgal/Spatial_searching/include/CGAL/Fuzzy_iso_box.h	模糊包围盒查询
/home/chunibyo/workspace/osc/cgal/Spatial_searching/include/CGAL/Orthogonal_k_neighbor_search.h	正交k近邻搜索

正交树相关文件 §

文件	说明
/home/chunibyo/workspace/osc/cgal/Orthtree/include/CGAL/Orthtree.h	正交树主类
/home/chunibyo/workspace/osc/cgal/Orthtree/include/CGAL/Octree.h	八叉树别名
/home/chunibyo/workspace/osc/cgal/Orthtree/include/CGAL/Quadtree.h	四叉树别名
/home/chunibyo/workspace/osc/cgal/Orthtree/include/CGAL/Orthtree_traits.h	通用 traits
/home/chunibyo/workspace/osc/cgal/Orthtree/include/CGAL/Orthtree_traits_point.h	点数据 traits
/home/chunibyo/workspace/osc/cgal/Orthtree/include/CGAL/Orthtree_traits_face_graph.h	面图 traits
/home/chunibyo/workspace/osc/cgal/Orthtree/include/CGAL/Orthtree_traits_polygons.h	多边形 traits
/home/chunibyo/workspace/osc/cgal/Orthtree/include/CGAL/Orthtree/Traversals.h	遍历策略