D01:10.13374/i.issn1001053x.1981.04.014 大规模集成电路原图图形的最小划分 工程图学教研室陈仁宽 摘 要 本文给出LSI原图图形划分成最小矩形数的公式，并为这样 的划分提出改进的算法。， 集成电路掩膜原图上的图形，都是由水平和垂直的直线所围成，其内部包括中空部分。 感光板靠透过图形发生器的矩形小窗的光照来曝光。适当地变换矩形小窗的尺寸、形状进行 曝光可在感光板上描绘出所需的图形，因此希望图形用最少的单元矩形之和来表示，而且要 求矩形不互相重迭，以保证原图的精度。发生器工作由计算机控制。 平面上有限个矩形单元的集合称为矩形单元组合体。集成电路原图上所呈现的图形，对 应为矩形单元组合体结构的一个平面图形。具有上述特征的图形，以下称图形P。集合所包 含的矩形单元的个数M称为划分数，本文将论述这样一个计算几何问题一一给出任何一个图 形P的最小划分数和完成这种刘分的算法。 设图形P的顶点数为N,构成闭合的边界数为B,即P没有中空部分时B=1,K个中空 部分时B=K+1。内角为直角的顶点称为凸点，设其个数为N1,内角是三个直角的顶点 (图1中用小圆圈表示)，称为凹点，设其个数为N2。 定理一：对于任何图形P有下列关系 N1=N+4-2B (1.1) 2 N2=N-4+2B 2 (1.2) N=12 B=2 =6 N=6 图1 图2 证：作辅助线，把P划分为若干三角形（图2）。设三角形的个数为R,辅助线的条数 为E。根据图论里欧拉公式（参阅参考文献2） n(頂点数)+r(区域数)-e(边数)=2 144大规模集成电路原图图形的最小划分 工 程 图学教研 室 陈仁 宽 摘 要 本文给 出 原 图 图形 划分成最小矩形傲 的公 式 ， 并为这样 的划分提 出改进的 算法 。 、 集成 电路掩膜原 图上 的 图形 ， 都是 由水 平和垂直 的直线所 围成 ， 其 内部包 括 中空部分 。 感光板靠透过图 形发生器的 矩形小窗 的光照 来 曝光 。 适 当地 变换矩形小窗的尺寸 、 形状进 行 曝光可在 感光板上描绘 出所 需的 图形 ， 因此希望 图形用 最少 的单元 矩形 之和 来表 示 ， 而且要 求矩形 不 互 相重 迭 ， 以 保证原图的精度 。 发生 器工 作 由计算机控 制 。 平面 上 有限 个矩形单 元 的集合称为矩 形单元组 合 体 。 集成 电路原 图上所 呈现的图形 ， 对 应 为矩形单元组 合体结 构 的一 个平面 图 形 。 具有上 述特征 的图形 ， 以 下称 图形 。 集合所包 含的 矩形单元 的个数 称为划分数 ， 本文将论述这样一个计算几何 问题— 给出任何一个图 形 的最小划 分数和完成这种 划 分 的算法 。 设 图形 的 顶点数为 ， 构成 闭合 的边界数为 ， 即 没 有中空 部分时 一 ， 个 中空 部分 时 。 内角为直 角的顶点 称为凸点 ， 设 其个数 为 ， 内角是 三 个直 角的顶点 图 中用 小 圆圈 表示 ， 称为凹点 ， 设其 个数为 。 定理 一 对于 任何图 形 有下列关 系 · · 夸 一 斗 一 。 二 二 户 广 ‘ 习 图 图 证 作辅助线 ， 把 划 分为若干三 角形 图 。 设 三 角形的个数为 ， 辅 助线 的 条数 为 。 根 据图 论里 欧拉公 式 参阅参考文献 顶点数 区域数 一 边数 科 DOI ：10．13374／j ．issn1001—053x．1981．04．014