3.2 计算几何地基：版图的布尔运算

3.2 计算几何地基：版图的布尔运算

本节摘要：版图本质是多边形集合，物理验证与制造数据处理的一切操作最终落在计算几何上：多边形布尔运算、面积重叠检测、间距测量、扫描线框架。本节讲清这些操作的算法结构与复杂度，说明为什么一套版图数据库的几何引擎性能直接决定 DRC、填充生成、掩模处理的交付周期。3.4 节的布局合法性检查与第 4 章的 DRC/LVS 都站在这块地基上。

版图是一堆多边形，问题从这里开始

把一块 28 纳米芯片的 GDSII 数据摊开：几十层掩模层，每层数十万到数百万个多边形，最细结构宽度几十纳米。这些多边形要在工具之间往返流转，每一次流转都伴随几何运算：层与层做与运算提取重叠区（如"有孔层与金属层求交得到接触区"）；同层做或运算合并相邻图形；做差运算挖掉禁止区。多边形布尔运算是版图世界的算术四则——频率之高、体量之大，使得它的实现质量直接拉开工具性能差距。

精确计算的难点不在思路而在鲁棒性。坐标是整数网格（数据库单位通常 0.5 纳米或更细），交点求解要用纯整数运算避免浮点误差；两个几乎重合的边相交时，交点可能退化成一段线而非一个点；自交多边形要拆解成规范形式（manhattan 化、45 度边处理）。工业几何引擎（如开源的 KLayout 内核、各家商业签核工具的几何层）在这类边界情形上的处理能力，往往比平均速度更能区分好坏。

扫描线：所有多边形算法的公共框架

一对复杂多边形（各 n 与 m 个顶点）的布尔运算，朴素做法是逐边求交：O(nm)。扫描线框架把它降到 O((n+m) log(n+m))：一条垂直线从左往右扫过平面，维护一条活动边表（当前被扫描线穿过的边，按 y 排序），只在"事件点"（顶点、边交点）处更新表并提取输出区间。空间换结构的思路在所有计算几何问题里反复出现：把二维问题降为一维有序结构的维护，排序一次，之后每步更新 O(log n)。

扫描线求两多边形交集的事件流（简化）

事件1 x=12: 边A进入活动表  → 活动 = [A1]
事件2 x=20: 边B进入活动表  → 活动 = [A1, B1]  开始有重叠带
事件3 x=35: 边A的配对边进入 → 重叠带结束, 输出区间 x 在 20 到 35
事件4 x=48: 全部退出      → 完成
每类事件只处理一次: 总代价 = 排序 O(N log N) + 每事件表更新 O(log N)
​

EDA 对扫描线还有一层数据规模的特殊处理：千万多边形不可能整体进内存做一次全图扫描，实用引擎全部按瓦片分块（tile）：把版图切成规则网格块，多边形按包围盒注册到所属块，布尔与检查在块内并行执行，跨块边界的多边形做特殊衔接。分块还顺带解锁了并行——块间无依赖，机器核数与几何吞吐近似线性，这是签核工具在云上弹性扩容的物理基础（第 7 章会回到这一点）。

间距、重叠与包含：DRC 的几何词汇

第 4 章的 DRC 规则本质上是几十类几何谓词的大规模求值。常用的谓词及其几何实质：宽度检查是图形自身两条边之间的最小距离（膨胀腐蚀框架下的形态学开运算可高效筛违例）；间距检查是两个不同图形间的最小距离，靠扫描线或四叉树近邻查询避免两两比较；包围检查（如接触孔必须被金属层四面包围至少若干纳米）是层间的偏置与包含判定；密度检查是窗口内面积占比，用面积累积树（区间树思想）把任意窗口的面积和做到对数时间。把这些谓词批量化的统一技巧是形态学膨胀：把图形按规则距离膨胀后与原图求交，交非空即违例——一次膨胀可同时筛出全图所有同规则违例，比逐对测量便宜一个数量级。

从几何到数据格式的两点提醒

第一点：几何运算的精度边界由数据库单位决定。坐标是整数，运算全程保持整数或定点，任何引入浮点累积误差的写法在签核场景都不可接受——这也是为什么专业几何引擎都自带整数化的多边形内核而不用通用图形库。第二点：现代版图数据的演进方向是压缩与语义（OASIS 相比 GDSII 在同等信息下体积缩小一个数量级），但工具内部的真实工作形态始终是展开后的多边形几何。记住这两点，你就理解了为什么第 5 章的掩模数据处理与第 4 章的物理验证，无论产品怎么包装，底层都是本节的扫描线加形态学再加瓦片并行的组合。地基打完，下一节开始进入物理实现的正戏：电路划分。

数据格式再补两句实用的。GDSII 是二进制流格式，用记录类型加数据元素组织， decades 下来的兼容性极好但体积大；OASIS 用可变长整数、重复结构引用与矩形阵列压缩，同等版图体积通常缩小一个数量级，加载时间也随之下降。但无论哪种格式，进到引擎内部都会展开成规整的多边形链表加空间索引（四叉树或瓦片网格）——格式管存储效率，索引管查询效率，两者是独立的两层设计。签核工具报告里常见的"层级深度超过阈值"警告，说的就是层次展开后的管理成本。

把这套引擎的吞吐量级落地一下：现代签核几何引擎在几十核服务器上，全量 DRC 扫一块大型块级版图的几何吞吐以每小时数十亿次谓词求值计，其中九成以上时间花在"筛掉不相关的图形对"上——真正相交的图形对占比极小。因此空间索引（四叉树、瓦片近邻表）的查询效率比布尔运算本体更能决定总时长，这也是几何引擎调优的主战场。理解了"筛比算贵"，你就理解了为什么签核工具的性能差异往往来自索引与并行调度，而不是多边形运算的教科书复杂度。

本节要点回顾

• 版图即多边形集合：布尔运算是版图世界的算术，整数网格运算的鲁棒性区分引擎好坏。
• 扫描线框架：布尔运算从 O(nm) 降到 O(N log N)，是所有版图几何操作的公共骨架。
• 瓦片分块：千万多边形按块切分并行处理，块间独立带来核数线性加速。
• DRC 谓词：宽度、间距、包围、密度四类谓词，膨胀加求交是批量筛违例的统一技巧。
• 整数与格式：数据库单位内全程整数运算；OASIS 压缩存储但内部仍展开为几何。
• 复用地图：3.4 的合法性检查与第 4 章 DRC/LVS 都直接复用本节引擎。