一种集成电路版图多边形自适应简化处理方法及装置

摘要

本申请实施例公开了一种集成电路版图多边形自适应简化处理方法及装置。该方法包括获取包含多个顶点的集成电路版图的多个多边形，形成以多边形顶点为网格节点的Delaunay三角形网格；根据边交换法将Delaunay三角形网格对齐到多个多边形各边，形成第一三角形网格；根据外推法识别第一三角形网格中多个多边形内所有三角形，其中，外推法将所有多边形形成集合，从该集合中一一取出多边形并对其进行识别三角形的处理，重复操作直到集合为空集，之后结束识别；判断第一三角形网格中多个多边形的边是否满足预设规则，在满足预设规则时依据各三角形质量对多个多边形进行自适应简化处理。本申请可保证集成电路版图多边形自适应简化处理方法的准确、完整以及高效。

权利要求

1.一种集成电路版图多边形自适应简化处理方法，其特征在于，包括：

获取包含多个顶点的集成电路版图的多个多边形，根据Delaunay三角剖分算法形成以多边形顶点为网格节点的Delaunay三角形网格；

根据边交换法将所述Delaunay三角形网格对齐到所述多个多边形的各个边，形成第一三角形网格；

根据外推法识别所述第一三角形网格中多个多边形内所有的三角形，其中，所述外推法将所有的所述多边形形成集合，从该集合中一一取出多边形并对其进行识别三角形的处理，重复操作直到所述集合为空集，之后结束所述识别；

判断所述第一三角形网格中多个多边形的边是否满足预设规则，并在满足所述预设规则时依据各个所述三角形的质量对所述多个多边形进行自适应简化处理；

其中，所述根据边交换法将所述Delaunay三角形网格对齐到所述多个多边形的各个边，形成第一三角形网格，包括：步骤2.1：收集所有不是两个三角形公共边的多边形的边，按边长排序形成集合Lost；

步骤2.2：从所述集合Lost取出边长最长的边 并将其从所述集合Lost中移除；

步骤2.3：从所述边 的一个顶点A出发，搜索包含所述顶点A且顶点C、D位于所述边两侧的三角形ΔACD，交换所述ΔACD与其邻居三角形ΔDCE的公共边，得到三角形ΔACE与ΔEDA，其中，所述邻居三角形为与该三角形有公共边的三角形；

步骤2.4：重复所述步骤2.3直到边 为两个邻居三角形的公共边；

步骤2.5：判断所述集合Lost是否为空集，若否，转入步骤2.2，若是，结束所述交换。

2.如权利要求1所述的方法，其特征在于，所述根据外推法识别所述第一三角形网格中多个多边形内所有的三角形，其中，所述外推法将所有的所述多边形形成集合，从该集合中一一取出多边形并对其进行识别三角形的处理，重复操作直到所述集合为空集，之后结束所述识别，包括：步骤3.1：收集所有的所述多边形形成集合Poly；

步骤3.2：从所述集合Poly中取出一个多边形P并将所述多边形P从所述集合Poly中移除，以所述多边形P任意边e的左三角形形成集合Front和Polytri，其中，所述多边形P任意边e的左三角形为包含该边e且三角形边e的方向与多边形P边e的方向相同的三角形；其中，所述边的方向定义为由起始点A到终止点B形成的向量的方向，即 的方向，若所述多边形P边e的方向与所述三角形边e的方向相同则二者的边都表示为 ，若所述多边形P边e的方向与所述三角形边e的方向相反，且二者有公共的边，所述多边形P边e的方向则为 的方向，即其边由起始点B指向终止点A，所述三角形边e的方向则为 的方向；

步骤3.3：从所述集合Front中取出一个三角形T并将其从所述集合Front中移除，判断所述三角形T的三个邻居三角形中的任何一个或多个邻居三角形与所述三角形T的公共边是否为所述多边形P的一条边，若否，且该一个或多个邻居三角形不在所述集合Polytri中，则将所述三角形T的该一个或多个邻居三角形加入所述集合Front以及所述集合Polytri中，若是，继续下一步操作；

步骤3.4：重复所述步骤3.3直到所述集合Front为空；

步骤3.5：判断所述集合Poly是否为空集，若否，转入步骤3.2，若是，结束所述识别。

3.如权利要求1或2所述的方法，其特征在于，所述三角形的质量的计算公式为：

，其中， R为三角形的外接圆半径；l1，l2，l3为三角形的边长；当所述三角形的Q值大于预设阈值，该三角形为质量差的三角形。

4.如权利要求3所述的方法，其特征在于，所述预设规则包括第一规则，所述第一规则包括：对一条多边形的边，如果两个邻居三角形以该边为公共边，所述两个邻居三角形均为质量差的三角形，并且所述两个邻居三角形最小角对的边均为所述公共边，则将该边选为待删除边；和/或所述预设规则还包括第二规则，所述第二规则包括：对两条相邻的多边形的边，如果两条相邻的多边形的边属于同一个三角形，所述三角形的三个邻居三角形均为质量差的三角形，且所述三个邻居三角形的最小角对的边分别对应所述三角形的三条边，则将所述两条相邻的多边形的边选为待删除边。

5.如权利要求4所述的方法，其特征在于，所述多个多边形的边若同时满足所述第一规则和第二规则，将该边按仅满足所述第二规则进行判断。

6.如权利要求5所述的方法，其特征在于，所述判断所述第一三角形网格中多个多边形的边是否满足预设规则，并在满足所述预设规则时依据各个所述三角形的质量对所述多个多边形进行自适应简化处理，包括：步骤4.1：收集所有满足所述第一规则或第二规则的多个多边形的边，按边长顺序排列形成集合DelEdges；

步骤4.2：判断所述集合DelEdges是否为空集，若是，结束所述多个多边形的自适应简化处理，若否，继续执行；

步骤4.3：从所述集合DelEdges找出最短边emin，如果所述最短边emin满足所述第一规则，按改变多边形面积最小原则删除所述最短边emin及其两个相邻的多边形边中的一个，形成新的多边形边enew；如果所述最短边emin满足所述第二规则，删除所述最短边emin及其满足所述第二规则的一个相邻的多边形边，形成新的多边形边enew；删除所述两个相邻的多边形边的公共顶点，并更新与所述公共顶点关联的三角形网格，形成第二三角形网格；

步骤4.4：如果所述多边形边enew不在两个三角形的公共边上，根据所述边交换法将所述第二三角形网格对齐到所述多边形边enew，使得所述多边形边enew成为两个三角形的公共边；

步骤4.5：判断所述多边形边enew是否满足所述第一规则或第二规则，若是，将所述多边形边enew按边长顺序插入所述集合DelEdges，之后转入所述步骤4.2，若否，直接转入所述步骤4.2。

说明书

一种集成电路版图多边形自适应简化处理方法及装置

技术领域

[0001] 本发明涉及集成电路版图多边形的简化处理领域，尤其涉及一种集成电路版图多边形自适应简化处理方法及装置。

背景技术

[0002] 集成电路版图是集成电路原理图与集成电路工艺实现之间的中间环节，是一个必不可少的重要环节。通过集成电路版图设计，可以将立体的电路系统变为一个二维的平面图形，再经过工艺加工还原为基于硅材料的立体结构。

[0003] 分析集成电路的直流电场时，首先要面临的是集成电路复杂版图多个多边形的网格剖分问题。由于工程中对复杂的集成电路版图多个多边形通常用很密集的点集连线来描述，该多个多边形中包含大量冗余的短边，直接针对原始的多个多边形进行网格剖分，在保证网格质量的前提下，最后生成的网格会非常密集，使得最终的计算难度非常大，几乎不可能，因此在网格细分之前有必要对描述集成电路版图形状的多个多边形进行简化处理。

[0004] 然而，发明人在实施本发明的过程中发现，在现有分析集成电路的直流电场的技术对集成电路版图多个多边形进行简化处理的过程中，若要识别三角形网格中多个多边形内所有的三角形，会发生由于操作量巨大，容易重复或者遗漏执行对部分多边形的处理，该部分多边形内的三角形相应未被识别，导致该外推法的准确性、完整性以及高效性得不到保证的问题，进而影响到该集成电路版图多边形的自适应简化处理方法的准确、完整以及高效。

发明内容

[0005] 本申请实施例提供了一种集成电路版图多边形自适应简化处理方法及装置，可以避免在集成电路版图多边形自适应简化处理过程中，根据外推法识别三角形网格中多个多边形内所有的三角形时，重复或者遗漏对部分多边形的处理，相应地未识别出该部分多边形内的三角形的问题，以保证所述外推法的准确性、完整性以及高效性，进而保证该集成电路版图多边形的自适应简化处理方法的准确、完整以及高效。

[0006] 第一方面，本申请实施例提供了一种集成电路版图多边形自适应简化处理方法，所述方法包括：

[0007] 获取包含多个顶点的集成电路版图的多个多边形，根据Delaunay三角剖分算法形成以多边形顶点为网格节点的Delaunay三角形网格；

[0008] 根据边交换法将所述Delaunay三角形网格对齐到所述多个多边形的各个边，形成第一三角形网格；

[0009] 根据外推法识别所述第一三角形网格中多个多边形内所有的三角形，其中，所述外推法将所有的所述多边形形成集合，从该集合中一一取出多边形并对其进行识别三角形的处理，重复操作直到所述集合为空集，之后结束所述识别；

[0010] 判断所述第一三角形网格中多个多边形的边是否满足预设规则，并在满足所述预设规则时依据各个所述三角形的质量对所述多个多边形进行自适应简化处理。

[0011] 作为一种可能的实施方式，所述根据外推法识别所述第一三角形网格中多个多边形内所有的三角形，其中，所述外推法将所有的所述多边形形成集合，从该集合中一一取出多边形并对其进行识别三角形的处理，重复操作直到所述集合为空集，之后结束所述识别，包括：

[0012] 步骤3.1：收集所有的所述多边形形成集合Poly；

[0013] 步骤3.2：从所述集合Poly中取出一个多边形P并将所述多边形P从所述集合Poly中移除，以所述多边形P任意边e的左三角形形成集合Front和Polytri，其中，所述多边形P任意边e的左三角形为包含该边e且三角形边e的方向与多边形P边e的方向相同的三角形；其中，所述边的方向定义为由起始点A到终止点B形成的向量的方向，即 的方向，若所述多边形P边e的方向与所述三角形边e的方向相同则二者的边都表示为 ，若所述多边形P边e的方向与所述三角形边e的方向相反，且二者有公共的边，所述多边形P边e的方向则为的方向，即其边由起始点B指向终止点A，所述三角形边e的方向则为 的方向；

[0014] 步骤3.3：从所述集合Front中取出一个三角形T并将其从所述集合Front中移除，判断所述三角形T的三个邻居三角形中的任何一个或多个邻居三角形与所述三角形T的公共边是否为所述多边形P的一条边，若否，且该一个或多个邻居三角形不在所述集合Polytri中，则将所述三角形T的该一个或多个邻居三角形加入所述集合Front以及所述集合Polytri中，若是，继续下一步操作；

[0015] 步骤3.4：重复所述步骤3.3直到所述集合Front为空；

[0016] 步骤3.5：判断所述集合Poly是否为空集，若否，转入步骤3.2，若是，结束所述识别。

[0017] 作为一种可能的实施方式，所述三角形的质量的计算公式为： ，其中，R为三角形的外接圆半径；l1，l2，l3为三角形的边长；当所述三角形的Q值大于预设阈值，该三角形为质量差的三角形。

[0018] 作为一种可能的实施方式，所述预设规则包括第一规则，所述第一规则包括：对一条多边形的边，如果两个邻居三角形以该边为公共边，所述两个邻居三角形均为质量差的三角形，并且所述两个邻居三角形最小角对的边均为所述公共边，则将该边选为待删除边；和/或

[0019] 所述预设规则还包括第二规则，所述第二规则包括：对两条相邻的多边形的边，如果两条相邻的多边形的边属于同一个三角形，所述三角形的三个邻居三角形均为质量差的三角形，且所述三个邻居三角形的最小角对的边分别对应所述三角形的三条边，则将所述两条相邻的多边形的边选为待删除边。

[0020] 作为一种可能的实施方式，所述多个多边形的边若同时满足所述第一规则和第二规则，将该边按仅满足所述第二规则进行判断。

[0021] 作为一种可能的实施方式，所述根据边交换法将所述Delaunay三角形网格对齐到所述多个多边形的各个边，形成第一三角形网格，包括：

[0022] 步骤2.1：收集所有不是两个三角形公共边的多边形的边，按边长排序形成集合Lost；

[0023] 步骤2.2：从所述集合Lost取出边长最长的边 并将其从所述集合Lost中移除；

[0024] 步骤2.3：从所述边 的一个顶点A出发，搜索包含所述顶点A且顶点C、D位于所述边 两侧的三角形ΔACD，交换所述ΔACD与其邻居三角形ΔDCE的公共边，得到三角形ΔACE与ΔEDA，其中，所述邻居三角形为与该三角形有公共边的三角形；

[0025] 步骤2.4：重复所述步骤2.3直到边 为两个邻居三角形的公共边；

[0026] 步骤2.5：判断所述集合Lost是否为空集，若否，转入步骤2.2，若是，结束所述交换。

[0027] 作为一种可能的实施方式，所述判断所述第一三角形网格中多个多边形的边是否满足预设规则，并在满足所述预设规则时依据各个所述三角形的质量对所述多个多边形进行自适应简化处理，包括：

[0028] 步骤4.1：收集所有满足所述第一规则或第二规则的多个多边形的边，按边长顺序排列形成集合DelEdges；

[0029] 步骤4.2：判断所述集合DelEdges是否为空集，若是，结束所述多个多边形的自适应简化处理，若否，继续执行；

[0030] 步骤4.3：从所述集合DelEdges找出最短边emin，如果所述最短边emin满足所述第一规则，按改变多边形面积最小原则删除所述最短边emin及其两个相邻的多边形边中的一个，形成新的多边形边enew；如果所述最短边emin满足所述第二规则，删除所述最短边emin及其满足所述第二规则的一个相邻的多边形边，形成新的多边形边enew；删除所述两个相邻的多边形边的公共顶点，并更新与所述公共顶点关联的三角形网格，形成第二三角形网格；

[0031] 步骤4.4：如果所述多边形边enew不在两个三角形的公共边上，根据所述边交换法将所述第二三角形网格对齐到所述多边形边enew，使得所述多边形边enew成为两个三角形的公共边；

[0032] 步骤4.5：判断所述多边形边enew是否满足所述第一规则或第二规则，若是，将所述多边形边enew按边长顺序插入所述集合DelEdges，之后转入所述步骤4.2，若否，直接转入所述步骤4.2。

[0033] 第二方面，本申请实施例提供了一种集成电路版图多边形自适应简化处理装置，所述装置包括：

[0034] 获取模块，用于获取包含多个顶点的集成电路版图的多个多边形，根据Delaunay三角剖分算法形成以多边形顶点为网格节点的Delaunay三角形网格；

[0035] 第一处理模块，用于根据边交换法将所述Delaunay三角形网格对齐到所述多个多边形的各个边，形成第一三角形网格；

[0036] 第二处理模块，用于根据外推法识别所述第一三角形网格中多个多边形内所有的三角形，其中，所述外推法将所有的所述多边形形成集合，从该集合中一一取出多边形并对其进行识别三角形的处理，重复操作直到所述集合为空集，之后结束所述识别；

[0037] 简化处理模块，用于判断所述第一三角形网格中多个多边形的边是否满足预设规则，并在满足所述预设规则时依据各个所述三角形的质量对所述多个多边形进行自适应简化处理。

[0038] 作为一种可能的实施方式，所述三角形的质量的计算公式为： ，其中，R为三角形的外接圆半径；l1，l2，l3为三角形的边长；当所述三角形的Q值大于预设阈值，该三角形为质量差的三角形。

[0039] 作为一种可能的实施方式，所述预设规则包括第一规则，所述第一规则包括：对一条多边形的边，如果两个邻居三角形以该边为公共边，所述两个邻居三角形均为质量差的三角形，并且所述两个邻居三角形最小角对的边均为所述公共边，则将该边选为待删除边；和/或

[0040] 所述预设规则还包括第二规则，所述第二规则包括：对两条相邻的多边形的边，如果两条相邻的多边形的边属于同一个三角形，所述三角形的三个邻居三角形均为质量差的三角形，且所述三个邻居三角形的最小角对的边分别对应所述三角形的三条边，则将所述两条相邻的多边形的边选为待删除边。

[0041] 本申请实施例具有如下有益效果：

[0042] 本申请实施例通过获取包含多个顶点的集成电路版图的多个多边形，根据Delaunay三角剖分算法形成以多边形顶点为网格节点的Delaunay三角形网格；根据边交换法将所述Delaunay三角形网格对齐到所述多个多边形的各个边，形成第一三角形网格；根据外推法识别所述第一三角形网格中多个多边形内所有的三角形，其中，所述外推法将所有的所述多边形形成集合，从该集合中一一取出多边形并对其进行识别三角形的处理，重复操作直到所述集合为空集，之后结束所述识别；判断所述第一三角形网格中多个多边形的边是否满足预设规则，并在满足所述预设规则时依据各个所述三角形的质量对所述多个多边形进行自适应简化处理，可以避免在集成电路版图多边形自适应简化处理过程中，根据外推法识别三角形网格中多个多边形内所有的三角形时，重复或者遗漏对部分多边形的处理，相应地未识别出该部分多边形内的三角形的问题，以保证所述外推法的准确性、完整性以及高效性，进而保证该集成电路版图多边形的自适应简化处理方法的准确、完整以及高效。

附图说明

[0043] 为了更清楚地说明本发明实施例中的技术方案，下面将对实施例的描述中所需要使用的附图做一简单地介绍，显而易见地，下面描述中的附图是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

[0044] 图1为本发明提供的集成电路版图多边形自适应简化处理方法实施例的流程示意图。

[0045] 图2为本发明提供的集成电路版图多边形自适应简化处理方法实施例中符合第一规则的待删除多边形示意图。

[0046] 图3为本发明提供的集成电路版图多边形自适应简化处理方法实施例中符合第二规则的待删除多边形示意图。

[0047] 图4为本发明提供的集成电路版图多边形自适应简化处理方法实施例中所述边交换法的交换过程的示意图。

[0048] 图5为本发明提供的集成电路版图多边形自适应简化处理方法实施例中集成电路版图多个多边形的局部放大示意图。

[0049] 图6为本发明提供的集成电路版图多边形自适应简化处理方法实施例中集成电路版图多个多边形自适应简化处理后的局部放大示意图。

[0050] 图7为本发明提供的集成电路版图多边形自适应简化处理方法实施例中集成电路版图多个多边形自适应网格细分的局部示意图。

[0051] 图8为本发明提供的集成电路版图多边形自适应简化处理方法实施例中集成电路版图多个多边形自适应简化处理后的自适应网格细分的局部示意图。

[0052] 图9为本发明提供的集成电路版图多边形自适应简化处理装置实施例的结构示意图。

具体实施方式

[0053] 为使本发明的目的、技术方案和优点更加清楚，以下将参照本发明实施例中的附图，通过实施方式详细地描述本发明的技术方案，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有作出创造性劳动的前提下所获得的所有其他实施例，都属于本发明保护的范围。

[0054] 在本发明的描述中，除非另有说明，“多个”的含义是两个或两个以上。在本发明的描述中，“第一”、“第二”等仅用于彼此的区分，而非表示它们的重要程度及顺序等。

[0055] 请参考图1-图8，本申请实施例提供了一种集成电路版图多边形自适应简化处理方法；如图所示，所述方法主要包括：

[0056] 步骤S1：获取包含多个顶点的集成电路版图的多个多边形，根据Delaunay三角剖分算法形成以多边形顶点为网格节点的Delaunay三角形网格；

[0057] 步骤S2：根据边交换法将所述Delaunay三角形网格对齐到所述多个多边形的各个边，形成第一三角形网格；

[0058] 步骤S3：根据外推法识别所述第一三角形网格中多个多边形内所有的三角形，其中，所述外推法将所有的所述多边形形成集合，从该集合中一一取出多边形并对其进行识别三角形的处理，重复操作直到所述集合为空集，之后结束所述识别；

[0059] 步骤S4：判断所述第一三角形网格中多个多边形的边是否满足预设规则，并在满足所述预设规则时依据各个所述三角形的质量对所述多个多边形进行自适应简化处理。

[0060] 采用上述方法，可以避免在集成电路版图多边形自适应简化处理过程中，根据外推法识别三角形网格中多个多边形内所有的三角形时，重复或者遗漏对部分多边形的处理，相应地未识别出该部分多边形内的三角形的问题，以保证所述外推法的准确性、完整性以及高效性，进而保证该集成电路版图多边形的自适应简化处理方法的准确、完整以及高效。

[0061] 所述多边形定义为，由N条（N≥3）线段首尾顺序连接起来形成的封闭图形，其线段端点形成多边形顶点。如果多边形顶点逆时针排列，定义多边形为正，其内对应集成电路版图导电区域；如果多边形顶点顺时针排列，定义多边形为负，其内对应集成电路版图绝缘区域；所述根据Delaunay三角剖分算法形成的Delaunay三角形网格中的所有三角形的方向都为正。通过数值计算方法计算电磁波在集成电路中的传播时，需考虑集成电路版图的导电区域、介质层等等。

[0062] 作为一种可能的实施方式，所述根据外推法识别所述第一三角形网格中多个多边形内所有的三角形，其中，所述外推法将所有的所述多边形形成集合，从该集合中一一取出多边形并对其进行识别三角形的处理，重复操作直到所述集合为空集，之后结束所述识别，主要包括：

[0063] 步骤3.1：收集所有的所述多边形形成集合Poly；

[0064] 步骤3.2：从所述集合Poly中取出一个多边形P并将所述多边形P从所述集合Poly中移除，以所述多边形P任意边e的左三角形形成集合Front和Polytri，其中，所述多边形P任意边e的左三角形为包含该边e且三角形边e的方向与多边形P边e的方向相同的三角形；其中，所述边的方向定义为由起始点A到终止点B形成的向量的方向，即 的方向，若所述多边形P边e的方向与所述三角形边e的方向相同则二者的边都表示为 ，若所述多边形P边e的方向与所述三角形边e的方向相反，且二者有公共的边，所述多边形P边e的方向则为的方向，即其边由起始点B指向终止点A，所述三角形边e的方向则为 的方向；

[0065] 步骤3.3：从所述集合Front中取出一个三角形T并将其从所述集合Front中移除，判断所述三角形T的三个邻居三角形中的任何一个或多个邻居三角形与所述三角形T的公共边是否为所述多边形P的一条边，若否，且该一个或多个邻居三角形不在所述集合Polytri中，则将所述三角形T的该一个或多个邻居三角形加入所述集合Front以及所述集合Polytri中，若是，继续下一步操作；

[0066] 步骤3.4：重复所述步骤3.3直到所述集合Front为空；

[0067] 步骤3.5：判断所述集合Poly是否为空集，若否，转入步骤3.2，若是，结束所述识别。

[0068] 作为一种可能的实施方式，所述三角形的质量的计算公式为： ，其中，R为三角形的外接圆半径；l1，l2，l3为三角形的边长；当所述三角形的Q值大于预设阈值，该三角形为质量差的三角形。

[0069] 作为一种可能的实施方式，所述预设规则可包括第一规则，所述第一规则包括：对一条多边形的边，如果两个邻居三角形以该边为公共边，所述两个邻居三角形均为质量差的三角形，并且所述两个邻居三角形最小角对的边均为所述公共边，则将该边选为待删除边；和/或

[0070] 所述预设规则还可包括第二规则，所述第二规则包括：对两条相邻的多边形的边，如果两条相邻的多边形的边属于同一个三角形，所述三角形的三个邻居三角形均为质量差的三角形，且所述三个邻居三角形的最小角对的边分别对应所述三角形的三条边，则将所述两条相邻的多边形的边选为待删除边。

[0071] 请参考图2，图2为本发明提供的集成电路版图多边形自适应简化处理方法实施例中符合第一规则的待删除多边形示意图，如图所示，边 的两个邻居三角形ΔADB和ΔABE均为质量差的三角形，边 的两个邻居三角形ΔBCD和ΔBCE也均为质量差的三角形。

[0072] 请参考图3，图3为本发明提供的集成电路版图多边形自适应简化处理方法实施例中符合第二规则的待删除多边形示意图，如图所示，相邻多边形边 、边 与另一条短边形成三角形ΔABC，所述三角形ΔABC的三个邻居三角形均为质量差的三角形。

[0073] 作为一种可能的实施方式，所述多个多边形的边若同时满足所述第一规则和第二规则，可将该边按仅满足所述第二规则进行判断。

[0074] 作为一种可能的实施方式，所述根据边交换法将所述Delaunay三角形网格对齐到所述多个多边形的各个边，形成第一三角形网格，主要包括：

[0075] 步骤2.1：收集所有不是两个三角形公共边的多边形的边，按边长排序形成集合Lost；

[0076] 步骤2.2：从所述集合Lost取出边长最长的边 并将其从所述集合Lost中移除；

[0077] 步骤2.3：从所述边 的一个顶点A出发，搜索包含所述顶点A且顶点C、D位于所述边 两侧的三角形ΔACD，交换所述ΔACD与其邻居三角形ΔDCE的公共边，得到三角形ΔACE与ΔEDA，其中，所述邻居三角形为与该三角形有公共边的三角形；

[0078] 步骤2.4：重复所述步骤2.3直到边 为两个邻居三角形的公共边；请参考图4，图4为本发明提供的集成电路版图多边形自适应简化处理方法实施例中所述边交换法的交换过程的示意图；

[0079] 步骤2.5：判断所述集合Lost是否为空集，若否，转入步骤2.2，若是，结束所述交换。

[0080] 作为一种可能的实施方式，所述判断所述第一三角形网格中多个多边形的边是否满足预设规则，并在满足所述预设规则时依据各个所述三角形的质量对所述多个多边形进行自适应简化处理，包括：

[0081] 步骤4.1：收集所有满足所述第一规则或第二规则的多个多边形的边，按边长顺序排列形成集合DelEdges；

[0082] 步骤4.2：判断所述集合DelEdges是否为空集，若是，结束所述多个多边形的自适应简化处理，若否，继续执行；

[0083] 步骤4.3：从所述集合DelEdges找出最短边emin，如果所述最短边emin满足所述第一规则，按改变多边形面积最小原则删除所述最短边emin及其两个相邻的多边形边中的一个，形成新的多边形边enew；如果所述最短边emin满足所述第二规则，删除所述最短边emin及其满足所述第二规则的一个相邻的多边形边，形成新的多边形边enew；删除所述两个相邻的多边形边的公共顶点，并更新与所述公共顶点关联的三角形网格，形成第二三角形网格；

[0084] 在所述步骤4.3中，如果所述最短边emin满足所述第一规则，则所述最短边emin的两个顶点、以及与该边共顶点的两个相邻的多边形边的另一个不同顶点分别形成一个三角形，比较该两个三角形的面积，删除最短边emin和面积较小的三角形包含的最短边emin的相邻的多边形边及该两条边的公共顶点，并重新基于该两条边的其他两个顶点形成新的多边形边enew；如果所述最短边emin满足所述第二规则，则必有一条相邻的边共同满足所述第二规则，直接删除该两条相邻的多边形边，并重新基于该两条边的其他两个顶点形成新的多边形边enew；

[0085] 步骤4.4：如果所述多边形边enew不在两个三角形的公共边上，根据所述边交换法将所述第二三角形网格对齐到所述多边形边enew，使得所述多边形边enew成为两个三角形的公共边；

[0086] 步骤4.5：判断所述多边形边enew是否满足所述第一规则或第二规则，若是，将所述多边形边enew按边长顺序插入所述集合DelEdges，之后转入所述步骤4.2，若否，直接转入所述步骤4.2。

[0087] 请参考图5和图6，图5为本发明提供的集成电路版图多边形自适应简化处理方法实施例中集成电路版图多个多边形的局部放大示意图；图6为本发明提供的集成电路版图多边形自适应简化处理方法实施例中集成电路版图多个多边形自适应简化处理后的局部放大示意图，如图所示，所述多个集成电路版图多个多边形经过所述自适应简化处理后，所述多个多边形的形状与自适应简化处理前多个多边形的形状几乎保持一致；

[0088] 请参考图7和图8，图7为本发明提供的集成电路版图多边形自适应简化处理方法实施例中集成电路版图多个多边形自适应网格细分的局部示意图；图8为本发明提供的集成电路版图多边形自适应简化处理方法实施例中集成电路版图多个多边形自适应简化处理后的自适应网格细分的局部示意图，如图所示，本申请实施例在对集成电路版图多个多边形的简化处理中，还可以避免出现直接对多个多边形的顶点进行Delaunay三角网格剖分并自适应细分网格，导致出现最后生成的网格非常密集、计算难度非常大的情况，实现在几乎保持版图多个多边形形状的前提下大大减少网格数量，并且使得即使自适应简化处理前版图多边形之间缝隙宽度为纳米量级，自适应简化处理后多边形彼此之间的缝隙仍完整保留，从而保持原始正常的集成电路版图的电路连接。

[0089] 请参考图9，本申请实施例提供了一种集成电路版图多边形自适应简化处理装置，所述装置主要包括：

[0090] 获取模块M1，用于获取包含多个顶点的集成电路版图的多个多边形，根据Delaunay三角剖分算法形成以多边形顶点为网格节点的Delaunay三角形网格；

[0091] 第一处理模块M2，用于根据边交换法将所述Delaunay三角形网格对齐到所述多个多边形的各个边，形成第一三角形网格；

[0092] 第二处理模块M3，用于根据外推法识别所述第一三角形网格中多个多边形内所有的三角形，其中，所述外推法将所有的所述多边形形成集合，从该集合中一一取出多边形并对其进行识别三角形的处理，重复操作直到所述集合为空集，之后结束所述识别；

[0093] 简化处理模块M4，用于判断所述第一三角形网格中多个多边形的边是否满足预设规则，并在满足所述预设规则时依据各个所述三角形的质量对所述多个多边形进行自适应简化处理。

[0094] 采用上述装置，通过所述第二处理模块中的所述外推法将所有的所述多边形形成集合，从该集合中一一取出多边形并对其进行识别三角形的处理，重复操作直到所述集合为空集，之后结束所述识别，可以避免在集成电路版图多边形自适应简化处理过程中，根据外推法识别三角形网格中多个多边形内所有的三角形时，重复或者遗漏对部分多边形的处理，相应地未识别出该部分多边形内的三角形的问题，以保证所述外推法的准确性、完整性以及高效性，进而保证该集成电路版图多边形的自适应简化处理方法的准确、完整以及高效。

[0095] 作为一种可能的实施方式，所述三角形的质量的计算公式为： ，其中，R为三角形的外接圆半径；l1，l2，l3为三角形的边长；当所述三角形的Q值大于预设阈值，该三角形为质量差的三角形。

[0096] 作为一种可能的实施方式，所述预设规则可包括第一规则，所述第一规则包括：对一条多边形的边，如果两个邻居三角形以该边为公共边，所述两个邻居三角形均为质量差的三角形，并且所述两个邻居三角形最小角对的边均为所述公共边，则将该边选为待删除边；和/或

[0097] 所述预设规则还可包括第二规则，所述第二规则包括：对两条相邻的多边形的边，如果两条相邻的多边形的边属于同一个三角形，所述三角形的三个邻居三角形均为质量差的三角形，且所述三个邻居三角形的最小角对的边分别对应所述三角形的三条边，则将所述两条相邻的多边形的边选为待删除边。

[0098] 以上所述，仅为本申请的较佳实施例及所运用的技术原理。本领域技术人员会理解，本申请不限于这里所述的特定实施例，对本领域技术人员来说能够进行各种明显的变化、重新调整和替代而不会脱离本申请的保护范围。因此，虽然通过以上实施例对本申请进行了较为详细的说明，但是本申请不仅仅限于以上实施例，在不脱离本申请构思的情况下，还可以包括更多其他等效实施例，而本申请的范围由所附的权利要求范围决定。