几何运算内核：多边形布尔运算与空间索引
各位硬件设计同仁，今天我们来聊聊几何运算内核。说白了，这就是DRC检查的“数学心脏”。你想想看，版图里那些多边形，怎么判断它们有没有打架？间距够不够？靠的就是这套几何运算。
我个人习惯把几何内核分成三块：布尔运算、边缘检测与间距计算、空间数据结构。这三块缺一不可。我刚开始做DRC引擎时，以为布尔运算就是核心，结果发现没有好的空间索引，跑一个全芯片检查要等一整天……嗯，那滋味可不好受。
多边形布尔运算：AND/OR/NOT/XOR
布尔运算，说白了就是多边形之间的逻辑操作。你想想看，DRC规则里经常说“A层和B层不能重叠”，那怎么检查？其实就是把A和B做AND运算，看结果是不是空集。
常见的四种操作：
- AND（与）：取两个多边形的交集。我用来检查“某层必须被另一层覆盖”的场景。
- OR（或）：取两个多边形的并集。常用于合并多个碎片化的图形。
- NOT（非）：从一个多边形中减去另一个。这是做“挖孔”操作的核心。
- XOR（异或）：取两个多边形的不重叠部分。我曾在项目中用它来检测“意外的图形偏移”。
实现这些运算，最经典的是扫描线算法。我简单说一下思路：
// 伪代码：多边形AND运算
function polygonAnd(polyA, polyB):
edges = mergeEdges(polyA, polyB) // 合并所有边
sortedEdges = sortByY(edges) // 按Y坐标排序
activeList = [] // 活跃边表
result = []
for each edge in sortedEdges:
updateActiveList(activeList, edge)
// 判断当前扫描线上哪些区间属于交集
intervals = computeIntersection(activeList)
result.append(intervals)
return reconstructPolygon(result)
这里有个坑——退化多边形。我曾经遇到一个案例，两个多边形刚好边对边重合，结果算法算出来一个零面积的多边形，导致后续检查全崩了。后来我加了一个“容差处理”，把小于某个阈值的图形直接忽略掉。
边缘检测与间距计算
边缘检测，说白了就是找多边形的边界。但DRC里更关心的是边缘之间的间距。比如金属线之间最小间距0.1um，怎么检查？
我常用的方法是Voronoi图法。每个多边形的边都生成一个“势力范围”，然后检查相邻势力范围之间的距离。这个方法效率很高，尤其适合处理大量平行线的情况。
另一种方法是扫描线+最近邻搜索。具体来说：
- 把所有多边形的边按X坐标排序
- 维护一个“活跃边”集合（当前扫描线穿过的边）
- 对每条新加入的边，只检查它和活跃集合中相邻边的距离
我记得有一次，客户反馈说某个DRC检查漏报了一个间距违规。我排查了半天，发现是因为两条边虽然距离很近，但属于不同的“连通域”，我的算法默认跳过了跨域检查。从那以后，我加了一个“全局最近邻”的兜底逻辑。
空间数据结构：R-tree 与 Quadtree
没有好的空间索引，几何运算就是纸上谈兵。你想想看，一个芯片版图可能有上亿个多边形，如果每个检查都要两两比较，那复杂度是O(n²)，跑一次要几个月。
我常用的两种结构：
| 数据结构 | 适用场景 | 我的经验 |
|---|---|---|
| R-tree | 动态插入/删除多的场景 | 适合交互式DRC，用户边编辑边检查 |
| Quadtree | 静态版图，区域查询多 | 适合批处理DRC，全芯片一次跑完 |
R-tree 的核心思想是用最小外接矩形（MBR）来近似表示多边形。每个节点存一个MBR，子节点的MBR完全包含在父节点内。查询时，从根节点往下走，如果查询区域和某个节点的MBR不相交，那整个子树都可以跳过。
我曾在项目中优化R-tree的插入策略。默认的R-tree插入可能导致节点重叠严重，查询效率下降。我改用了“强制重插入”策略——当节点溢出时，不是简单分裂，而是把部分条目重新插入到树的其他位置。这样树的平衡性更好。
Quadtree 就更直观了。把版图区域递归四等分，直到每个格子里的多边形数量少于某个阈值。查询时，只需要访问和查询区域相交的格子。
Quadtree有个问题——边界敏感。如果一个多边形刚好跨在格子边界上，它会被存到多个格子中。我曾经遇到一个bug，就是因为多边形被重复计数，导致布尔运算结果多了一倍。后来我改用“只存到最小包含格子”的策略，才解决这个问题。
下面这张图展示了R-tree和Quadtree的核心区别：
嗯，这张图应该能帮你理解两者的区别。R-tree像是一个“俄罗斯套娃”，大盒子套小盒子；Quadtree则像是“切蛋糕”，一刀一刀切成小块。
最后说一句，不要迷信任何一种数据结构。我见过有人把R-tree吹上天，结果在密集版图上性能还不如一个简单的网格索引。关键是要根据你的数据特征来选择。如果你版图里图形分布均匀，用Quadtree；如果图形分布极不均匀（比如有些区域密集，有些区域稀疏），R-tree更合适。
好了，几何运算内核就聊到这里。下次我们聊聊如何把这些运算组合起来，构建一个完整的DRC规则检查流程。