《Geometric Data Structures for Computer Graphics》全书导览

按2006年第一版10章目录建立从静态层次、邻近关系到动态化与鲁棒计算的学习路线。

先做预测

先预测结果，再观察结构变化并解释偏差。先给同一场景设计窗口查询、最近邻、碰撞候选和动态更新四种需求，预测四叉树、kd树、BSP、BVH、距离场和Voronoi图各自最先失效的条件。导览的目标不是记住结构名称，而是建立问题特征到数据结构的可解释选择链。 本页用、、、、建立从对象、表示、查询到证书的完整链路。

第一版权威目录定位

本页一一对应Elmar Langetepe与Gabriel Zachmann在A K Peters出版的2006年第一版《Geometric Data Structures for Computer Graphics》Geometric Data Structures for Computer Graphics全书导览。出版社页面确认第一版、两位作者、362页和正式10章目录；作者所在研究组同时给出原书信息、ISBN 9781568812359、目录以及第7章材料。

原书小节覆盖

  1. 第1章 Quadtrees and Octrees
  2. 第2章 Orthogonal Windowing and Stabbing Queries
  3. 第3章 BSP Trees
  4. 第4章 Bounding Volume Hierarchies
  5. 第5章 Distance Fields
  6. 第6章 Voronoi Diagrams
  7. 第7章 Geometric Proximity Graphs
  8. 第8章 Kinetic Data Structures
  9. 第9章 Degeneracy and Robustness
  10. 第10章 Dynamization of Geometric Data Structures

核心对象

  1. 几何查询契约：把输入对象、查询区域、输出集合、复杂度和数值语义同时写清。
  2. 空间层次：通过递归分割或对象包围把不相关候选在高层剪枝。
  3. 邻近结构：用距离、空圆或局部邻域显式编码点集之间的接近关系。
  4. 动态结构：在对象运动或集合增删时维护查询证书与复杂度保证。
  5. 验收证书：保存构建参数、访问节点、候选集合、精确谓词与基准结果。

查询与表示契约

先固定数据域、维数、闭开边界、查询输出和数值语义。树高或节点数不是独立目标；只有候选完备、结果无重复、复杂度含输出规模且数值分支一致时，结构才算正确。

Q=(D,R,O,Π,C)Q=(D,R,O,\Pi,C) Ttotal=Tbuild+mTquery+uTupdateT_{total}=T_{build}+mT_{query}+uT_{update} accept⁡=exact⁡∧complete⁡∧bounded⁡\operatorname{accept}=\operatorname{exact}\land\operatorname{complete}\land\operatorname{bounded} S=TbruteTstructureS=\frac{T_{brute}}{T_{structure}}

原书先按灵活性递增介绍四叉树、kd树、BSP和BVH，再由栅格携带距离得到距离场，由连续距离分区得到Voronoi图与邻近图，最后集中处理运动、退化和动态增删。学习时以查询契约为主线：每一章都记录划分对象、节点不变量、剪枝条件、构建代价和失败边界。 每个剪枝判断都应能回答两个问题：被排除的集合是什么，以及哪个不变量证明它不含答案。

可核查构建与查询

建立统一实验场景，所有结构接收同一批点、线段、三角形和运动轨迹；输出访问节点数、候选数、精确测试数、更新时间和内存。静态正确性用穷举查询作基线，动态正确性在每个事件后重建一份小规模基线。

def query_with_trace(root, request):
    stack, hits, trace = [root], [], []
    while stack:
        node = stack.pop()
        trace.append(node.id)
        if node.disjoint(request):
            continue
        if node.is_leaf:
            hits.extend(node.exact_matches(request))
        else:
            stack.extend(node.children)
    return sorted(set(hits)), trace

通用骨架必须由本章的具体不变量实例化：区域不相交、包围体不重叠、空邻域、证书未失效或静态块版本有效。不能把候选生成误写成最终答案，叶节点仍需执行本章定义的精确测试。

复杂度与工程取舍

复杂度报告分离构建、查询、更新、内存和输出规模。平均值之外记录P95与最坏样例；同时保存访问节点、候选对象和精确谓词次数，这样才能判断瓶颈来自树质量、数据分布还是数值回退。

metrics = {
    "build_ms": 0.0,
    "visited_nodes": 0,
    "candidates": 0,
    "exact_tests": 0,
    "update_ms": 0.0,
}
assert set(metrics) == {"build_ms", "visited_nodes", "candidates", "exact_tests", "update_ms"}

只在结果集合与基线一致后比较性能。构建更慢可能换来大量查询收益，更新更便宜也可能逐渐恶化结构；因此工作负载中的查询次数、更新比例和生命周期必须写入报告。

边界、退化与反例

空场景、所有对象共面、重复点、查询落在分割面、无限射线、极端尺度和高速运动都必须单独定义归属规则。若不同章节使用不同边界约定，跨结构比较会产生无法解释的假差异。

audit = {
    "normal": "representative geometry",
    "boundary": "closed-open convention",
    "degenerate": "duplicate or co-located input",
    "baseline": "brute-force exact result",
}
assert all(audit.values())

图形学应用

对可编辑三维场景做混合工作负载：视锥窗口用kd树或层次结构，碰撞候选用BVH，表面偏移用距离场，最近站点用Voronoi结构，运动期间用事件证书或增量重建。最终报告必须解释选择依据，而不只给耗时排行榜。 应用层还要记录从世界坐标到结构坐标的变换，避免把坐标系错误误判为数据结构错误。

  1. 用五到十个对象手算结构，标出节点覆盖、邻接或证书。
  2. 执行一个正常查询和一个恰落在边界的查询，逐节点记录剪枝理由。
  3. 删除一个一般位置或静态假设，构造首个失败样例。
  4. 与穷举答案逐项比较，再扩大规模测构建、查询、更新和内存。

验收证书

验收包包含原始输入、结构参数、节点或图邻接、查询日志、候选集合、精确结果、复杂度计数和失败反例。固定数据集、查询序列和数值策略，同时报告构建、查询、更新、内存与错误率。 任何无法重放的截图或孤立耗时都不能替代证书。

常见误区

本章回顾

本页覆盖几何查询契约、空间层次、邻近结构、动态结构、验收证书。掌握标准是能从查询契约选择表示，推导剪枝或邻近条件，实现构建与更新，并用精确基线、退化输入和复杂度计数形成可重放证书。

术语表

讨论

评论区加载中…