16.4 盒相交与区间跳表

16.4.1 理论基础

d维盒相交问题

盒相交问题是计算几何中的经典问题：给定两组d维轴对齐包围盒，找出所有相交的盒对。

问题定义：

输入：两组d维轴对齐盒 A = {a₁, …, aₙ} 和 B = {b₁, …, bₘ}
输出：所有满足 aᵢ ∩ bⱼ ≠ ∅ 的盒对 (aᵢ, bⱼ)

应用场景：

碰撞检测
计算机图形学中的可见性计算
CAD/CAM 中的干涉检查
分子模拟中的邻近粒子查找

算法策略

1. 朴素算法（All-Pairs）

检查所有可能的盒对
时间复杂度：O(n × m)
适用于小规模数据

2. 扫描线算法（Sweep Line）

将d维问题转化为d个一维问题
使用扫描线和区间树
时间复杂度：O(n log n + k)，k为相交对数

3. 线段树算法（Segment Tree）

基于线段树的分治策略
适用于静态数据集
时间复杂度：O(n log^{d-1} n + k)

4. 流式算法（Stream）

基于Z序曲线或Hilbert曲线的空间排序
缓存友好，适合大规模数据

区间跳表（Interval Skip List）

区间跳表是跳表（Skip List）的扩展，用于维护动态区间集合并支持高效的区间刺探查询。

核心特性：

概率平衡：使用随机化实现期望 O(log n) 的性能
动态操作：支持区间的插入和删除
标记机制：使用”标记”（marker）记录区间在跳表中的路径

支持的操作：

insert(interval)：插入区间，O(log n) 期望
remove(interval)：删除区间，O(log n) 期望
find_intervals(point)：查找包含点的所有区间，O(log n + k)

16.4.2 架构分析

Box_intersection_d 模块设计

box_intersection_d<ConcurrencyTag>(...)
box_self_intersection_d<ConcurrencyTag>(...)
box_intersection_all_pairs_d(...)
Box_d<NT, Dimension>
Box_with_handle_d<NT, Dimension, Handle>
Box_with_info_d<NT, Dimension, Info>

盒相交函数（位于 `/home/chunibyo/workspace/osc/cgal/Box_intersection_d/include/CGAL/box_intersection_d.h`）

namespace CGAL {
 
// 通用盒相交函数（两组盒）
template<class ConcurrencyTag = Sequential_tag,
          class RandomAccessIter1, class RandomAccessIter2,
          class Callback, class BoxTraits>
void box_intersection_d(
    RandomAccessIter1 begin1, RandomAccessIter1 end1,
    RandomAccessIter2 begin2, RandomAccessIter2 end2,
    Callback callback,
    BoxTraits box_traits,
    std::ptrdiff_t cutoff = 10,
    Box_intersection_d::Topology topology = Box_intersection_d::CLOSED,
    Box_intersection_d::Setting setting = Box_intersection_d::BIPARTITE);
 
// 自相交函数（单组盒）
template<class ConcurrencyTag = Sequential_tag,
          class RandomAccessIter, class Callback, class BoxTraits>
void box_self_intersection_d(
    RandomAccessIter begin, RandomAccessIter end,
    Callback callback,
    BoxTraits box_traits,
    std::ptrdiff_t cutoff = 10,
    Box_intersection_d::Topology topology = Box_intersection_d::CLOSED);
 
// 全对算法（朴素算法）
template<class ForwardIter1, class ForwardIter2, class Callback, class BoxTraits>
void box_intersection_all_pairs_d(
    ForwardIter1 begin1, ForwardIter1 end1,
    ForwardIter2 begin2, ForwardIter2 end2,
    Callback callback, BoxTraits);
 
} // namespace CGAL

参数说明

namespace Box_intersection_d {
    // 拓扑类型：CLOSED 包含边界，OPEN 不包含边界
    enum Topology { CLOSED, OPEN };
    
    // 设置类型：BIPARTITE 两组之间相交，COMPLETE 包括组内相交
    enum Setting { BIPARTITE, COMPLETE };
}

Interval_skip_list 类设计

// 位于 /home/chunibyo/workspace/osc/cgal/Interval_skip_list/include/CGAL/Interval_skip_list.h
 
template <class Interval_>
class Interval_skip_list {
public:
    typedef Interval_ Interval;
    typedef typename Interval::Value Value;
    
    // 构造函数
    Interval_skip_list();
    
    template <class InputIterator>
    Interval_skip_list(InputIterator b, InputIterator e);
    
    // 修改操作
    void insert(const Interval& I);
    bool remove(const Interval& I);
    void clear();
    
    // 查询操作
    template <class OutputIterator>
    OutputIterator find_intervals(const Value& searchKey, OutputIterator out);
    
    bool is_contained(const Value& searchKey) const;
    
    // 迭代器
    const_iterator begin() const;
    const_iterator end() const;
    
    int size() const;
    
private:
    int maxLevel;
    IntervalSLnode<Interval>* header;
    std::list<Interval> container;
    
    int randomLevel();  // 随机选择节点层数
    void placeMarkers(...);  // 放置区间标记
    void removeMarkers(...);  // 移除区间标记
};

16.4.3 实现细节

盒相交线段树算法

// 来自 box_intersection_d.h 的核心算法
namespace internal {
 
template<class ConcurrencyTag, class RandomAccessIter1, class RandomAccessIter2,
          class Callback, class Traits>
void box_intersection_segment_tree_d(
    RandomAccessIter1 begin1, RandomAccessIter1 end1,
    RandomAccessIter2 begin2, RandomAccessIter2 end2,
    Callback callback,
    const Traits& traits,
    const std::ptrdiff_t cutoff,
    const bool in_order)
{
    typedef typename Traits::NT NT;
    CGAL_assertion(Traits::dimension() > 0);
    const int dim = Traits::dimension() - 1;
    
    const NT inf = Box_intersection_d::box_limits<NT>::inf();
    const NT sup = Box_intersection_d::box_limits<NT>::sup();
    
    // 并行版本使用 TBB
    #ifdef CGAL_LINKED_WITH_TBB
    if(std::is_convertible<ConcurrencyTag, Parallel_tag>::value) {
        // 将数据分成4份并行处理
        static constexpr int n = 4;
        
        // 创建数据副本（因为排序会修改数据）
        val_container range_1_copies, range_2_copies;
        // ... 复制数据 ...
        
        tbb::task_group g;
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < n; ++j) {
                // 计算子范围
                It r1_start = ...;
                It r1_end = ...;
                It r2_start = ...;
                It r2_end = ...;
                
                // 并行执行
                g.run([=]{ 
                    Box_intersection_d::segment_tree(
                        r1_start, r1_end, r2_start, r2_end,
                        inf, sup, callback, traits, cutoff, dim, in_order);
                });
            }
        }
        g.wait();
    }
    else
    #endif
    {
        // 串行版本
        Box_intersection_d::segment_tree(
            begin1, end1, begin2, end2,
            inf, sup, callback, traits, cutoff, dim, in_order);
    }
}
 
} // namespace internal

线段树递归算法

// 概念性实现（基于 segment_tree.h）
template<class RandomAccessIter1, class RandomAccessIter2, 
          class Callback, class Traits>
void segment_tree(
    RandomAccessIter1 begin1, RandomAccessIter1 end1,
    RandomAccessIter2 begin2, RandomAccessIter2 end2,
    NT inf, NT sup,
    Callback& callback,
    const Traits& traits,
    std::ptrdiff_t cutoff,
    int dim,
    bool in_order)
{
    // 基本情况：使用全对算法
    if(std::distance(begin1, end1) <= cutoff ||
       std::distance(begin2, end2) <= cutoff) {
        all_pairs(begin1, end1, begin2, end2, callback, traits, in_order);
        return;
    }
    
    // 选择分割维度（循环选择）
    // 沿当前维度排序
    std::sort(begin1, end1, Compare_by_coordinate<dim>());
    std::sort(begin2, end2, Compare_by_coordinate<dim>());
    
    // 找到中点
    auto mid1 = begin1 + (end1 - begin1) / 2;
    auto mid2 = begin2 + (end2 - begin2) / 2;
    NT split_value = ...;  // 计算分割值
    
    // 分割第一组
    auto split1 = std::partition(begin1, end1, 
        [split_value](const Box& b) { return b.max_coord(dim) <= split_value; });
    
    // 分割第二组
    auto split2_lo = std::partition(begin2, end2,
        [split_value](const Box& b) { return b.max_coord(dim) <= split_value; });
    auto split2_hi = std::partition(split2_lo, end2,
        [split_value](const Box& b) { return b.min_coord(dim) >= split_value; });
    
    // 递归处理三个子问题：
    // 1. 完全在左侧的盒
    segment_tree(begin1, split1, begin2, split2_lo, ..., dim-1, ...);
    
    // 2. 完全在右侧的盒
    segment_tree(split1, end1, split2_hi, end2, ..., dim-1, ...);
    
    // 3. 跨越分割线的盒（需要在所有维度上检查）
    // 收集跨越的盒
    std::vector crossing1, crossing2;
    for(auto it = split1; it \!= end1; ++it)
        if(it->min_coord(dim) <= split_value) crossing1.push_back(*it);
    for(auto it = begin2; it \!= split2_hi; ++it)
        if(it->max_coord(dim) >= split_value) crossing2.push_back(*it);
    
    // 对跨越的盒进行全对检查
    all_pairs(crossing1.begin(), crossing1.end(),
              crossing2.begin(), crossing2.end(), callback, traits, in_order);
}

区间跳表节点结构

// 来自 Interval_skip_list.h
template <class Interval_>
class IntervalSLnode {
    typedef Interval_ Interval;
    typedef typename Interval::Value Value;
    
    bool is_header;           // 是否为头节点
    Value key;                // 节点键值
    IntervalSLnode** forward; // 前向指针数组
    IntervalList<Interval>** markers;  // 标记数组
    IntervalList<Interval>* eqMarkers; // 等值标记
    int ownerCount;           // 拥有该键值的区间数
    int topLevel;             // 最高层数
    
public:
    IntervalSLnode(const Value& searchKey, int levels);
    IntervalSLnode(int levels);  // 头节点构造函数
    
    int level() const { return topLevel + 1; }
    const Value& getValue() { return key; }
    bool isHeader() const { return is_header; }
    IntervalSLnode* get_next() { return forward[0]; }
};

区间跳表插入算法

// 来自 Interval_skip_list.h
template <class Interval>
IntervalSLnode<Interval>* Interval_skip_list<Interval>::insert(
    const Value& searchKey)
{
    // update数组记录需要修改的指针
    IntervalSLnode<Interval>* update[MAX_FORWARD];
    IntervalSLnode<Interval>* x;
    int i;
    
    // 搜索插入位置，同时构建update数组
    x = search(searchKey, update);
    
    if(x == 0 || x->key \!= searchKey) {
        // 创建新节点
        int newLevel = randomLevel();
        if(newLevel > maxLevel) {
            // 扩展头节点的指针数组
            for(i = maxLevel + 1; i <= newLevel; i++) {
                update[i] = header;
                header->markers[i]->clear();
            }
            maxLevel = newLevel;
        }
        
        x = new IntervalSLnode<Interval>(searchKey, newLevel);
        
        // 插入节点
        for(i = 0; i <= newLevel; i++) {
            x->forward[i] = update[i]->forward[i];
            update[i]->forward[i] = x;
        }
        
        // 调整标记以维护不变量
        adjustMarkersOnInsert(x, update);
    }
    return x;
}
 
// 随机层数选择（几何分布）
template <class Interval>
int Interval_skip_list<Interval>::randomLevel()
{
    boost::geometric_distribution<> proba(0.5);
    boost::variate_generator<boost::rand48&, boost::geometric_distribution<>> 
        die(random, proba);
    return (std::min)(die(), (int)maxLevel) + 1;
}

区间跳表标记放置

// 来自 Interval_skip_list.h
template <class Interval>
void Interval_skip_list<Interval>::placeMarkers(
    IntervalSLnode<Interval>* left,
    IntervalSLnode<Interval>* right,
    const Interval_handle& I)
{
    IntervalSLnode<Interval>* x = left;
    if(I->contains(x->key)) 
        x->eqMarkers->insert(I);
    
    int i = 0;  // 从第0层开始向上
    
    // 上升阶段：找到区间跨越的最高层
    while(x->forward[i] \!= 0 && 
          I->contains_interval(x->key, x->forward[i]->key)) {
        // 尽可能向上
        while(i \!= x->level() - 1 && x->forward[i+1] \!= 0 &&
              I->contains_interval(x->key, x->forward[i+1]->key))
            i++;
        
        // 在当前层放置标记
        if(x->forward[i] \!= 0) {
            x->markers[i]->insert(I);
            x = x->forward[i];
            if(I->contains(x->key))
                x->eqMarkers->insert(I);
        }
    }
    
    // 下降阶段：处理剩余路径
    while(x->key \!= right->key) {
        // 找到合适的层
        while(i \!= 0 && (x->forward[i] == 0 ||
               \!I->contains_interval(x->key, x->forward[i]->key)))
            i--;
        
        x->markers[i]->insert(I);
        x = x->forward[i];
        if(I->contains(x->key))
            x->eqMarkers->insert(I);
    }
}

区间刺探查询

// 来自 Interval_skip_list.h
template <class OutputIterator>
OutputIterator Interval_skip_list<Interval>::find_intervals(
    const Value& searchKey, OutputIterator out)
{
    IntervalSLnode<Interval>* x = header;
    
    // 自顶向下遍历
    for(int i = maxLevel; i >= 0 && 
        (x->isHeader() || x->key \!= searchKey); i--) {
        
        // 在当前层向前移动
        while(x->forward[i] \!= 0 && 
              searchKey >= x->forward[i]->key) {
            x = x->forward[i];
        }
        
        // 收集该层的标记（区间）
        if(\!x->isHeader() && x->key \!= searchKey) {
            out = x->markers[i]->copy(out);
        } else if(\!x->isHeader()) {
            // 到达目标点，收集等值标记
            out = x->eqMarkers->copy(out);
        }
    }
    return out;
}

16.4.4 使用示例

示例1：两组盒相交检测

#include <CGAL/Simple_cartesian.h>
#include <CGAL/box_intersection_d.h>
#include <CGAL/Box_intersection_d/Box_d.h>
#include <vector>
#include <iostream>
 
typedef CGAL::Simple_cartesian<double> K;
typedef K::Point_3 Point;
 
// 定义3D盒类型
typedef CGAL::Box_intersection_d::Box_d<double, 3> Box;
 
// 回调函数：处理相交的盒对
void intersect_callback(const Box& a, const Box& b)
{
    std::cout << "盒相交: [" << &a << ", " << &b << "]" << std::endl;
}
 
int main()
{
    // 创建第一组盒
    std::vector<Box> boxes1;
    boxes1.push_back(Box(Point(0, 0, 0), Point(1, 1, 1)));
    boxes1.push_back(Box(Point(2, 2, 2), Point(3, 3, 3)));
    boxes1.push_back(Box(Point(0.5, 0.5, 0.5), Point(1.5, 1.5, 1.5)));
    
    // 创建第二组盒
    std::vector<Box> boxes2;
    boxes2.push_back(Box(Point(0.8, 0.8, 0.8), Point(2, 2, 2)));
    boxes2.push_back(Box(Point(5, 5, 5), Point(6, 6, 6)));
    
    // 执行相交检测
    CGAL::box_intersection_d(
        boxes1.begin(), boxes1.end(),
        boxes2.begin(), boxes2.end(),
        intersect_callback,
        CGAL::Box_intersection_d::Box_traits_d<Box>(),
        10,  // cutoff
        CGAL::Box_intersection_d::CLOSED,
        CGAL::Box_intersection_d::BIPARTITE
    );
    
    return 0;
}

示例2：自相交检测（带句柄）

#include <CGAL/Simple_cartesian.h>
#include <CGAL/box_intersection_d.h>
#include <CGAL/Box_intersection_d/Box_with_handle_d.h>
#include <vector>
#include <iostream>
 
typedef CGAL::Simple_cartesian<double> K;
typedef K::Point_3 Point;
 
// 自定义数据结构
struct Triangle {
    Point p1, p2, p3;
    int id;
};
 
// 使用带句柄的盒类型
typedef CGAL::Box_intersection_d::Box_with_handle_d<double, 3, const Triangle*> Box;
 
// 回调函数
void self_intersect_callback(const Box& a, const Box& b)
{
    const Triangle* t1 = a.handle();
    const Triangle* t2 = b.handle();
    
    std::cout << "三角形 " << t1->id << " 和 " << t2->id << " 的包围盒相交" << std::endl;
    // 这里可以进一步进行精确的三角形相交测试
}
 
int main()
{
    // 创建三角形
    std::vector<Triangle> triangles = {
        {Point(0, 0, 0), Point(1, 0, 0), Point(0, 1, 0), 1},
        {Point(0.5, 0.5, 0), Point(1.5, 0.5, 0), Point(0.5, 1.5, 0), 2},
        {Point(5, 5, 0), Point(6, 5, 0), Point(5, 6, 0), 3}
    };
    
    // 创建包围盒
    std::vector<Box> boxes;
    for(const auto& tri : triangles) {
        double min_coord[3] = {
            std::min({tri.p1.x(), tri.p2.x(), tri.p3.x()}),
            std::min({tri.p1.y(), tri.p2.y(), tri.p3.y()}),
            std::min({tri.p1.z(), tri.p2.z(), tri.p3.z()})
        };
        double max_coord[3] = {
            std::max({tri.p1.x(), tri.p2.x(), tri.p3.x()}),
            std::max({tri.p1.y(), tri.p2.y(), tri.p3.y()}),
            std::max({tri.p1.z(), tri.p2.z(), tri.p3.z()})
        };
        boxes.push_back(Box(min_coord, max_coord, &tri));
    }
    
    // 执行自相交检测
    CGAL::box_self_intersection_d(
        boxes.begin(), boxes.end(),
        self_intersect_callback
    );
    
    return 0;
}

示例3：区间跳表基本使用

#include <CGAL/Interval_skip_list.h>
#include <CGAL/Interval_skip_list_interval.h>
#include <list>
#include <iostream>
 
// 定义区间类型
typedef CGAL::Interval_skip_list_interval<double> Interval;
typedef CGAL::Interval_skip_list<Interval> Interval_skip_list;
 
int main()
{
    // 创建区间跳表
    Interval_skip_list isl;
    
    // 插入区间
    isl.insert(Interval(1.0, 5.0));
    isl.insert(Interval(3.0, 7.0));
    isl.insert(Interval(6.0, 10.0));
    isl.insert(Interval(0.0, 2.0));
    
    std::cout << "区间数量: " << isl.size() << std::endl;
    
    // 刺探查询：查找包含点4的所有区间
    std::list<Interval> result;
    isl.find_intervals(4.0, std::back_inserter(result));
    
    std::cout << "包含点4的区间:" << std::endl;
    for(const auto& interval : result) {
        std::cout << "  [" << interval.inf() << ", " << interval.sup() << "]" << std::endl;
    }
    
    // 检查点是否被包含
    if(isl.is_contained(1.5)) {
        std::cout << "点1.5被至少一个区间包含" << std::endl;
    }
    
    // 删除区间
    isl.remove(Interval(1.0, 5.0));
    std::cout << "删除后区间数量: " << isl.size() << std::endl;
    
    // 批量插入
    std::vector<Interval> intervals = {
        Interval(10.0, 15.0),
        Interval(12.0, 18.0),
        Interval(20.0, 25.0)
    };
    isl.insert(intervals.begin(), intervals.end());
    
    return 0;
}

示例4：并行盒相交检测

#include <CGAL/Simple_cartesian.h>
#include <CGAL/box_intersection_d.h>
#include <CGAL/Box_intersection_d/Box_d.h>
#include <CGAL/Parallel_tag.h>
#include <vector>
#include <iostream>
 
typedef CGAL::Simple_cartesian<double> K;
typedef CGAL::Box_intersection_d::Box_d<double, 3> Box;
 
std::atomic<int> intersection_count(0);
 
void count_callback(const Box& a, const Box& b)
{
    intersection_count++;
}
 
int main()
{
    // 生成大量随机盒
    std::vector<Box> boxes1, boxes2;
    for(int i = 0; i < 10000; ++i) {
        double x1 = rand() / (double)RAND_MAX * 100;
        double y1 = rand() / (double)RAND_MAX * 100;
        double z1 = rand() / (double)RAND_MAX * 100;
        double s1 = rand() / (double)RAND_MAX * 10;
        boxes1.push_back(Box(
            K::Point_3(x1, y1, z1),
            K::Point_3(x1 + s1, y1 + s1, z1 + s1)
        ));
        
        double x2 = rand() / (double)RAND_MAX * 100;
        double y2 = rand() / (double)RAND_MAX * 100;
        double z2 = rand() / (double)RAND_MAX * 100;
        double s2 = rand() / (double)RAND_MAX * 10;
        boxes2.push_back(Box(
            K::Point_3(x2, y2, z2),
            K::Point_3(x2 + s2, y2 + s2, z2 + s2)
        ));
    }
    
    // 使用并行标签执行相交检测
    CGAL::box_intersection_d<CGAL::Parallel_tag>(
        boxes1.begin(), boxes1.end(),
        boxes2.begin(), boxes2.end(),
        count_callback,
        CGAL::Box_intersection_d::Box_traits_d<Box>(),
        100  // 较大的cutoff以减少任务开销
    );
    
    std::cout << "相交盒对数量: " << intersection_count << std::endl;
    
    return 0;
}

16.4.5 复杂度分析

盒相交算法复杂度

算法	预处理	查询时间	空间	适用场景
全对算法	O(1)	O(n × m)	O(1)	小规模数据（n,m < 100）
线段树	O(n log^{d-1} n)	O(n log^{d-1} n + k)	O(n log^{d-1} n)	静态数据
扫描线	O(n log n)	O((n+m) log n + k)	O(n)	低维数据（d ≤ 3）
流式算法	O(n)	O(n + k)	O(1)	超大规模数据

其中：

n, m 是两组盒的数量
d 是维度
k 是相交对数

区间跳表复杂度

操作	期望时间	最坏情况	说明
插入	O(log n)	O(n)	随机化保证期望性能
删除	O(log n)	O(n)	需要调整标记
刺探查询	O(log n + k)	O(n)	k是包含该点的区间数
空间	O(n)	O(n log n)	每个区间存储在O(log n)个节点

参数调优建议

Cutoff 参数：

较小的 cutoff（如10）：更多递归，适合数据分布均匀的情况
较大的 cutoff（如100-1000）：减少递归开销，适合数据分布不均匀
并行模式下建议使用较大的 cutoff（如100）以减少任务调度开销

拓扑类型选择：

CLOSED：包含边界，适用于大多数几何应用
OPEN：不包含边界，适用于严格的内部相交检测

设置类型选择：

BIPARTITE：只检测两组之间的相交，效率更高
COMPLETE：包括组内相交，适用于自相交检测

16.4.6 关键文件位置

Box_intersection_d 模块

文件	说明
`/home/chunibyo/workspace/osc/cgal/Box_intersection_d/include/CGAL/box_intersection_d.h`	主接口文件
`/home/chunibyo/workspace/osc/cgal/Box_intersection_d/include/CGAL/Box_intersection_d/Box_d.h`	基本盒类型
`/home/chunibyo/workspace/osc/cgal/Box_intersection_d/include/CGAL/Box_intersection_d/Box_with_handle_d.h`	带句柄的盒
`/home/chunibyo/workspace/osc/cgal/Box_intersection_d/include/CGAL/Box_intersection_d/Box_with_info_d.h`	带信息的盒
`/home/chunibyo/workspace/osc/cgal/Box_intersection_d/include/CGAL/Box_intersection_d/Box_traits_d.h`	盒 traits
`/home/chunibyo/workspace/osc/cgal/Box_intersection_d/include/CGAL/Box_intersection_d/segment_tree.h`	线段树算法
`/home/chunibyo/workspace/osc/cgal/Box_intersection_d/include/CGAL/Box_intersection_d/box_limits.h`	数值极限

Interval_skip_list 模块

文件	说明
`/home/chunibyo/workspace/osc/cgal/Interval_skip_list/include/CGAL/Interval_skip_list.h`	区间跳表主类
`/home/chunibyo/workspace/osc/cgal/Interval_skip_list/include/CGAL/Interval_skip_list_interval.h`	区间类型定义

文件	说明
`/home/chunibyo/workspace/osc/cgal/Spatial_sorting/include/CGAL/spatial_sort.h`	空间排序（Hilbert/Morton曲线）
`/home/chunibyo/workspace/osc/cgal/Spatial_sorting/include/CGAL/hilbert_sort.h`	Hilbert曲线排序
`/home/chunibyo/workspace/osc/cgal/Spatial_sorting/include/CGAL/hilbert_sort_2.h`	2D Hilbert排序
`/home/chunibyo/workspace/osc/cgal/Spatial_sorting/include/CGAL/hilbert_sort_3.h`	3D Hilbert排序

Chunibyo

Explorer

16.4 盒相交与区间跳表

16.4 盒相交与区间跳表

相关章节

16.4.1 理论基础

d维盒相交问题

算法策略

区间跳表（Interval Skip List）

16.4.2 架构分析

Box_intersection_d 模块设计

盒相交函数（位于 `/home/chunibyo/workspace/osc/cgal/Box_intersection_d/include/CGAL/box_intersection_d.h`）

参数说明

Interval_skip_list 类设计

16.4.3 实现细节

盒相交线段树算法

线段树递归算法

区间跳表节点结构

区间跳表插入算法

区间跳表标记放置

区间刺探查询

16.4.4 使用示例

示例1：两组盒相交检测

示例2：自相交检测（带句柄）

示例3：区间跳表基本使用

示例4：并行盒相交检测

16.4.5 复杂度分析

盒相交算法复杂度

区间跳表复杂度

参数调优建议

16.4.6 关键文件位置

Box_intersection_d 模块

Interval_skip_list 模块

相关模块

Graph View

Table of Contents

Backlinks

Chunibyo

Explorer

16.4 盒相交与区间跳表

16.4 盒相交与区间跳表 §

相关章节 §

16.4.1 理论基础 §

d维盒相交问题 §

算法策略 §

区间跳表（Interval Skip List） §

16.4.2 架构分析 §

Box_intersection_d 模块设计 §

盒相交函数（位于 /home/chunibyo/workspace/osc/cgal/Box_intersection_d/include/CGAL/box_intersection_d.h） §

参数说明 §

Interval_skip_list 类设计 §

16.4.3 实现细节 §

盒相交线段树算法 §

线段树递归算法 §

区间跳表节点结构 §

区间跳表插入算法 §

区间跳表标记放置 §

区间刺探查询 §

16.4.4 使用示例 §

示例1：两组盒相交检测 §

示例2：自相交检测（带句柄） §

示例3：区间跳表基本使用 §

示例4：并行盒相交检测 §

16.4.5 复杂度分析 §

盒相交算法复杂度 §

区间跳表复杂度 §

参数调优建议 §

16.4.6 关键文件位置 §

Box_intersection_d 模块 §

Interval_skip_list 模块 §

相关模块 §

Graph View

Table of Contents

Backlinks

16.4 盒相交与区间跳表

相关章节

16.4.1 理论基础

d维盒相交问题

算法策略

区间跳表（Interval Skip List）

16.4.2 架构分析

Box_intersection_d 模块设计

盒相交函数（位于 `/home/chunibyo/workspace/osc/cgal/Box_intersection_d/include/CGAL/box_intersection_d.h`）

参数说明

Interval_skip_list 类设计

16.4.3 实现细节

盒相交线段树算法

线段树递归算法

区间跳表节点结构

区间跳表插入算法

区间跳表标记放置

区间刺探查询

16.4.4 使用示例

示例1：两组盒相交检测

示例2：自相交检测（带句柄）

示例3：区间跳表基本使用

示例4：并行盒相交检测

16.4.5 复杂度分析

盒相交算法复杂度

区间跳表复杂度

参数调优建议

16.4.6 关键文件位置

Box_intersection_d 模块

Interval_skip_list 模块

相关模块