一种用于集成电路版图检测孤岛的方法和系统，包括如下步骤：将集成电路版图中的定义为孔的部分和覆铜的部分转换为版图多边形并进行布尔操作并对其进行网格剖分，基于网格剖分生成以版图多边形的边界为约束的统一版图的约束三角形网格；基于约束三角形网格查找覆铜区域中的三角形网格并根据邻居搜索的方法将其编号；基于相同编号三角形的面积和判断孤岛；将集成电路版图转变为可网格划分的形式，提取覆铜区域内的三角形网格并根据邻居搜索的方法将其编号，并基于覆铜区域的相同编号的网格面积和来判断孔是否为孤岛，不仅避免如果不检测孤岛直接生产影响版图的可靠性，还能避免集成电路版图的孤岛数量多，密集不易识别，靠人工去查找孤岛费时费力。
1.一种用于集成电路版图检测孤岛的方法，其特征在于，包括如下步骤： S1、将集成电路版图中的定义为孔的部分和覆铜的部分转换为版图多边形并进行布尔操作，形成统一的版图多边形；所述将集成电路版图中的定义为孔的部分和覆铜的部分转换为版图多边形并进行布尔操作，形成统一的版图多边形包括：
S11、对集成电路版图中定义为孔的部分转换为挖空的多边形；其中，将孔的部分中由过孔引起的隔离垫片转换为第一挖空的多边形，当所述由过孔引起的隔离垫片的形状在集成电路的版图中定义为圆时，所述第一挖空的多边形为正多边形，当所述由过孔引起的隔离垫片的形状在集成电路的版图中定义为椭圆时，按椭圆在极坐标下等弧度取离散点，所述第一挖空的多边形为由离散点依次连成的多边形，当所述由过孔引起的隔离垫片的形状在集成电路的版图中定义为多边形时，所述第一挖空的多边形为版图中定义的多边形；将孔的部分中由集成电路版图中定义为覆铜的部分内的挖空圆、挖空椭圆和挖空多边形转换为第二挖空的多边形，当所述定义为覆铜的部分内的挖空圆时，所述第二挖空的多边形为正多边形，当所述定义为覆铜的部分内的挖空椭圆时，按椭圆在极坐标下等弧度取离散点，所述第二挖空的多边形为由离散点依次连成的多边形，当所述定义为覆铜的部分内的挖空多边形时，所述第二挖空的多边形为版图中定义的多边形；
S12、对集成电路版图中定义为覆铜的部分转换为覆铜的多边形；其中，将覆铜的部分中的走线按起始点、终止点和宽度转换为第一覆铜的多边形，所述第一覆铜的多边形为矩形，将覆铜的部分中由过孔引起的焊盘转换为第二覆铜的多边形，所述第二覆铜的多边形在由所述隔离垫片转换为的挖空多边形内，当所述焊盘的形状在集成电路的版图中定义为圆时，所述第二覆铜的多边形为正多边形，当所述焊盘的形状在集成电路的版图中定义为椭圆时，按椭圆在极坐标下等弧度取离散点，所述第二覆铜的多边形为由离散点依次连成的多边形，当所述焊盘的形状在集成电路的版图中定义为多边形时，所述第二覆铜的多边形为版图中定义的多边形，将覆铜的其他部分转换为第三覆铜的多边形，当覆铜的其他部分定义为圆时，所述第三覆铜的多边形为正多边形，当覆铜的其他部分定义为椭圆时，按椭圆在极坐标下等弧度取离散点，所述第三覆铜的多边形为由离散点依次连成的多边形，当覆铜的其他部分定义为多边形时，所述第三覆铜的多边形为版图中定义的多边形；
S13、将所述第一覆铜的多边形和第三覆铜的多边形进行布尔或操作，形成第三新的覆铜多边形；
S14、将所述第三新的覆铜多边形分别和所述第一挖空的多边形、所述第二挖空的多边形进行布尔差操作，形成第一新的覆铜多边形；
S15、将所述第一新的覆铜多边形和所述第二覆铜的多边形进行布尔或操作，形成统一的版图多边形； S2、基于统一的版图多边形及其边，对所述统一的版图多边形进行网格剖分并进行边交换，生成以所述统一的版图多边形的边为约束的约束三角形网格； S3、基于约束三角形网格查找覆铜区域中的三角形网格并根据邻居搜索的方法将其编号；
S4、基于相同编号的三角形网格的面积和的大小判断孤岛。
2.根据权利要求1所述的一种用于集成电路版图检测孤岛的方法，其特征在于，所述对所述统一的版图多边形进行网格剖分并进行边交换，生成以所述统一的版图多边形的边为约束的约束三角形网格包括： S21、依据Delaunay剖分准则对所述统一的版图多边形的顶点进行网格剖分，形成网格剖分； S22、收集网格剖分中所有不是两个三角形公共边的多边形的边，按边长排序形成集合Lost；
S23、从所述集合Lost中取出边长最长的边并将其从所述集合Lost中移除； S24、从所述边长最长的边的一个顶点出发，搜索包含所述顶点且其他两个顶点位于边两侧的三角形，交换所述三角形与其邻居三角形的公共边，得到两个新的三角形，其中，所述邻居三角形为与该三角形有公共边的三角形； S25、重复步骤S24直到所述边长最长的边为两个邻居三角形的公共边； S26、判断所述集合Lost是否为空集，若否，则转入步骤S23，若是，则生成所述统一的版图多边形中以所述统一的版图多边形的边为约束的约束三角形网格。
3.根据权利要求2所述的一种用于集成电路版图检测孤岛的方法，其特征在于，所述基于约束三角形网格查找覆铜区域中的三角形网格并根据邻居搜索的方法将其编号包括： S31、初始设置所有三角形的编号为未编号；设置当前覆铜区域的三角形填充编号为fp=1；
设置当前待处理的覆铜多边形为第q=1个覆铜多边形；设置当前外围覆铜网格单元集合Frontp为空； S32、对第q个覆铜多边形，从多边形的任意边e出发，找到这个边关联的左三角形t1，若所述左三角形t1的编号为未编号，设置三角形t1的编号为fp，将其加入到集合Frontp中，所述多边形任意边e的左三角形为包含该边e且三角形边e的方向与多边形边e的方向相同的三角形； S33、从所述集合Frontp取出一个三角形t并将其从所述集合Frontp中移除，若所述三角形t的三个邻居三角形中的任何一个或多个邻居三角形的编号为未编号，且公共边不为任何多边形的边，则将所述三角形t的该一个或多个邻居三角形加入所述集合Frontp中，并将新加入所述集合Frontp的三角形的编号为fp，其中，所述公共边指与所述三角形t相邻的三角形与所述三角形t的公共边； S34、判断所述集合Frontp是否为空集，若否，执行步骤S33，若是，设置fp=fp+1，q=q+1，执行步骤S32，直到处理完成所有统一的版图多边形中的覆铜多边形，结束。
4.根据权利要求3所述的一种用于集成电路版图检测孤岛的方法，其特征在于，所述基于相同编号的三角形网格的面积和的大小判断孤岛包括：计算所有编号为正的三角形网格的面积，并将相同编号的三角形面积累加到以编号归类的面积和的集合中，面积和与编号形成一一对应关系，找出三角形面积和小于给定阈值对应的编号，所述编号对应的区域为检测出的孤岛。
5.一种用于集成电路版图检测孤岛的系统，其特征在于，包括版图转换模块、约束三角形生成模块、覆铜区域识别模块和孤岛判断模块；其中，所述版图转换模块用于将集成电路版图中的定义为孔的部分和覆铜的部分转换为版图多边形并进行布尔操作，形成统一的版图多边形；所述约束三角形生成模块用于基于统一的版图多边形及其边，对所述统一的版图多边形进行网格剖分并进行边交换，生成以所述统一的版图多边形的边为约束的约束三角形网格；所述覆铜区域识别模块用于基于约束三角形网格查找覆铜区域中的三角形网格并根据邻居搜索的方法将其编号；所述孤岛判断模块用于基于相同编号的三角形网格的面积和的大小判断孤岛；所述版图转换模块包括孔转换单元、覆铜转换单元、第三新的覆铜多边形布尔操作单元、第一新的覆铜多边形布尔操作单元和统一的版图多边形布尔操作单元； 所述孔转换单元用于对集成电路版图中定义为孔的部分转换为挖空的多边形；其中，将孔的部分中由过孔引起的隔离垫片转换为第一挖空的多边形，当所述由过孔引起的隔离垫片的形状在集成电路的版图中定义为圆时，所述第一挖空的多边形为正多边形，当所述由过孔引起的隔离垫片的形状在集成电路的版图中定义为椭圆时，按椭圆在极坐标下等弧度取离散点，所述第一挖空的多边形为由离散点依次连成的多边形，当所述由过孔引起的隔离垫片的形状在集成电路的版图中定义为多边形时，所述第一挖空的多边形为版图中定义的多边形；将孔的部分中由集成电路版图中定义为覆铜的部分内的挖空圆、挖空椭圆和挖空多边形转换为第二挖空的多边形，当所述定义为覆铜的部分内的挖空圆时，所述第二挖空的多边形为正多边形，当所述定义为覆铜的部分内的挖空椭圆时，按椭圆在极坐标下等弧度取离散点，所述第二挖空的多边形为由离散点依次连成的多边形，当所述定义为覆铜的部分内的挖空多边形时，所述第二挖空的多边形为版图中定义的多边形； 所述覆铜转换单元用于对集成电路版图中定义为覆铜的部分转换为覆铜的多边形；其中，将覆铜的部分中的走线按起始点、终止点和宽度转换为第一覆铜的多边形，所述第一覆铜的多边形为矩形，将覆铜的部分中由过孔引起的焊盘转换为第二覆铜的多边形，所述第二覆铜的多边形在由所述隔离垫片转换为的挖空多边形内，当所述焊盘的形状在集成电路的版图中定义为圆时，所述第二覆铜的多边形为正多边形，当所述焊盘的形状在集成电路的版图中定义为椭圆时，按椭圆在极坐标下等弧度取离散点，所述第二覆铜的多边形为由离散点依次连成的多边形，当所述焊盘的形状在集成电路的版图中定义为多边形时，所述第二覆铜的多边形为版图中定义的多边形，将覆铜的其他部分转换为第三覆铜的多边形，当覆铜的其他部分定义为圆时，所述第三覆铜的多边形为正多边形，当覆铜的其他部分定义为椭圆时，按椭圆在极坐标下等弧度取离散点，所述第三覆铜的多边形为由离散点依次连成的多边形，当覆铜的其他部分定义为多边形时，所述第三覆铜的多边形为版图中定义的多边形；
第三新的覆铜多边形布尔操作单元用于将所述第一覆铜的多边形和第三覆铜的多边形进行布尔或操作，形成第三新的覆铜多边形； 所述第一新的覆铜多边形布尔操作单元用于将所述第三新的覆铜多边形分别和所述第一挖空的多边形、所述第二挖空的多边形进行布尔差操作，形成第一新的覆铜多边形； 所述统一的版图多边形布尔操作单元用于将所述第一新的覆铜多边形和所述第二覆铜的多边形进行布尔或操作，形成统一的版图多边形。
6.根据权利要求5所述的一种用于集成电路版图检测孤岛的系统，其特征在于，所述约束三角形生成模块包括第一单元、第二单元、第三单元、第四单元、第五单元和第六单元；其中，所述第一单元用于依据Delaunay剖分准则对所述统一的版图多边形的顶点进行网格剖分，形成网格剖分；所述第二单元用于收集网格剖分中所有不是两个三角形公共边的多边形的边，按边长排序形成集合Lost；所述第三单元用于从所述集合Lost中取出边长最长的边并将其从所述集合Lost中移除；所述第四单元从所述边长最长的边的一个顶点出发，搜索包含所述顶点且其他两个顶点位于边两侧的三角形，交换所述三角形与其邻居三角形的公共边，得到两个新的三角形，其中，所述邻居三角形为与该三角形有公共边的三角形；所述第五单元用于重复所述第三单元执行的内容直到所述边长最长的边为两个邻居三角形的公共边；所述第六单元用于判断所述集合Lost是否为空集，若否，则返回所述第三单元，若是，则生成所述统一的版图多边形中以所述统一的版图多边形的边为约束的约束三角形网格。
7.根据权利要求6所述的一种用于集成电路版图检测孤岛的系统，其特征在于，所述覆铜区域识别模块包括第一识别单元、第二识别单元、第三识别单元和第四识别单元； 其中第一识别单元用于初始设置所有三角形的编号为未编号；设置当前覆铜区域的三角形填充编号为fp=1；设置当前待处理的覆铜多边形为第q=1个覆铜多边形；设置当前外围覆铜网格单元集合Frontp为空；所述第二识别单元用于对第q个覆铜多边形，从多边形的任意边e出发，找到这个边关联的左三角形t1，若所述左三角形t1的编号为未编号，设置三角形t1的编号为fp，将其加入到集合Frontp中，所述多边形任意边e的左三角形为包含该边e且三角形边e的方向与多边形边e的方向相同的三角形；所述第三识别单元用于从所述集合Frontp取出一个三角形t并将其从所述集合Frontp中移除，若所述三角形t的三个邻居三角形中的任何一个或多个邻居三角形的编号为未编号，且公共边不为任何多边形的边，则将所述三角形t的该一个或多个邻居三角形加入所述集合Frontp中，并将新加入所述集合Frontp的三角形的编号为fp，其中，所述公共边指与所述三角形t相邻的三角形与所述三角形t的公共边；
所述第四识别单元用于判断所述集合Frontp是否为空集，若否，返回第三识别单元，若是，设置fp=fp+1，q=q+1，返回第二识别单元，直到处理完成所有统一的版图多边形中的覆铜多边形。
8.根据权利要求7所述的一种用于集成电路版图检测孤岛的系统，其特征在于：所述基于相同编号的三角形网格的面积和的大小判断孤岛包括：计算所有编号为正的三角形网格的面积，并将相同编号的三角形面积累加到以编号归类的面积和的集合中，面积和与编号形成一一对应关系，找出三角形面积和小于给定阈值对应的编号，所述编号对应的区域为检测出的孤岛。
一种用于集成电路版图检测孤岛的方法和系统
技术领域
[0001] 本申请涉及集成电路技术领域，具体涉及一种用于集成电路版图检测孤岛的方法和系统。
背景技术
[0002] 随着通信技术的发展，超大规模集成电路的研究与发展已逐渐展开。为了提高电子设备的性能，缩小体积，降低成本，将晶体管与其他元器件以及线路都集成在一小块半导体基片上。为了实现更多的功能，超大规模集成电路有几层到上百层结构，每层结构极其复杂，集成数千万甚至数亿的晶体管，具有多尺度结构，从厘米级到目前最新的纳米级。集成电路的覆铜版图也因为不同网络的不同元器件的连接形成的走线被裁剪成非常复杂的几何图形，通常，需要将这些复杂的几何图形离散成形状简单的网格单元，再基于这些网格单元进行数值计算以获得形状复杂的版图的电位分布和电流分布。随着集成电路制备的工艺水平越来越高，层之间连通的过孔越来越多使得过孔越来越密集，使生产出来的集成电路中由这些密集分布的过孔对应的隔离垫片之间形成一些毫无意义的孤岛的覆铜区域，如图2孤岛示意图中的孤岛，这些在生产出来的集成电路中存在的孤岛会影响电路使用的安全性和精确性，需要在集成电路版图中识别出孤岛并做相应处理，如图3，是对孤岛填充后的示意图。如何在集成电路版图中识别孤岛是本领域技术人员亟待解决的技术问题。
发明内容
[0003] （一）申请目的
[0004] 有鉴于此，本申请的目的在于提供一种用于集成电路版图检测孤岛的方法和系统，用于解决现有技术中不能在集成电路版图中识别孤岛的技术问题。
[0005] （二）技术方案
[0006] 本申请公开一种用于集成电路版图检测孤岛的方法，包括如下步骤：
[0007] S1、将集成电路版图中的定义为孔的部分和覆铜的部分转换为版图多边形并进行布尔操作，形成统一的版图多边形；
[0008] S2、基于统一的版图多边形及其边，对所述统一的版图多边形进行网格剖分并进行边交换，生成以所述统一的版图多边形的边为约束的约束三角形网格；
[0009] S3、基于约束三角形网格查找覆铜区域中的三角形网格并根据邻居搜索的方法将其编号；
[0010] S4、基于相同编号的三角形网格的面积和的大小判断孤岛。
[0011] 在一种可能的实施方式中，所述将集成电路版图中的定义为孔的部分和覆铜的部分转换为版图多边形并进行布尔操作，形成统一的版图多边形包括：
[0012] S11、对集成电路版图中定义为孔的部分转换为挖空的多边形；其中，将孔的部分中由过孔引起的隔离垫片转换为第一挖空的多边形，当所述由过孔引起的隔离垫片的形状在集成电路的版图中定义为圆时，所述第一挖空的多边形为正多边形，当所述由过孔引起的隔离垫片的形状在集成电路的版图中定义为椭圆时，按椭圆在极坐标下等弧度取离散点，所述第一挖空的多边形为由离散点依次连成的多边形，当所述由过孔引起的隔离垫片的形状在集成电路的版图中定义为多边形时，所述第一挖空的多边形为版图中定义的多边形；将孔的部分中由集成电路版图中定义为覆铜的部分内的挖空圆、挖空椭圆和挖空多边形转换为第二挖空的多边形，当所述定义为覆铜的部分内的挖空圆时，所述第二挖空的多边形为正多边形，当所述定义为覆铜的部分内的挖空椭圆时，按椭圆在极坐标下等弧度取离散点，所述第二挖空的多边形为由离散点依次连成的多边形，当所述定义为覆铜的部分内的挖空多边形时，所述第二挖空的多边形为版图中定义的多边形；
[0013] S12、对集成电路版图中定义为覆铜的部分转换为覆铜的多边形；其中，将覆铜的部分中的走线按起始点、终止点和宽度转换为第一覆铜的多边形，所述第一覆铜的多边形为矩形，将覆铜的部分中由过孔引起的焊盘转换为第二覆铜的多边形，所述第二覆铜多边形在由所述隔离垫片转换为的挖空多边形内，当所述焊盘的形状在集成电路的版图中定义为圆时，所述第二覆铜的多边形为正多边形，当所述焊盘的形状在集成电路的版图中定义为椭圆时，按椭圆在极坐标下等弧度取离散点，所述第二覆铜的多边形为由离散点依次连成的多边形，当所述焊盘的形状在集成电路的版图中定义为多边形时，所述第二覆铜的多边形为版图中定义的多边形，将覆铜的其他部分转换为第三覆铜的多边形，当覆铜的其他部分定义为圆时，所述第三覆铜的多边形为正多边形，当覆铜的其他部分定义为椭圆时，按椭圆在极坐标下等弧度取离散点，所述第三覆铜的多边形为由离散点依次连成的多边形，当覆铜的其他部分定义为多边形时，所述第三覆铜的多边形为版图中定义的多边形；
[0014] S13、将所述第一覆铜的多边形和第三覆铜的多边形进行布尔或操作，形成第三新的覆铜多边形；
[0015] S14、将所述第三新的覆铜多边形分别和所述第一挖空的多边形、所述第二挖空的多边形进行布尔差操作，形成第一新的覆铜多边形；
[0016] S15、将所述第一新的覆铜多边形和所述第二覆铜的多边形进行布尔或操作，形成统一的版图多边形。
[0017] 在一种可能的实施方式中，所述对所述统一的版图多边形进行网格剖分并进行边交换，生成以所述统一的版图多边形的边为约束的的约束三角形网格包括：
[0018] S21、依据Delaunay剖分准则对所述统一的版图多边形的顶点进行网格剖分，形成网格剖分； S22、收集网格剖分中所有不是两个三角形公共边的多边形的边，按边长排序形成集合Lost；
[0019] S23、从所述集合Lost中取出边长最长的边并将其从所述集合Lost中移除；
[0020] S24、从所述边长最长的边的一个顶点出发，搜索包含所述顶点且其他两个顶点位于边两侧的三角形，交换所述三角形与其邻居三角形的公共边，得到两个新的三角形，其中，所述邻居三角形为与该三角形有公共边的三角形；
[0021] S25、重复步骤S23直到所述边长最长的边为两个邻居三角形的公共边；
[0022] S26、判断所述集合Lost是否为空集，若否，则转入步骤S22，若是，则生成所述统一的版图多边形中以所述统一的版图多边形的边为约束的约束三角形网格。
[0023] 在一种可能的实施方式中，所述基于约束三角形网格查找覆铜区域中的三角形网格并根据邻居搜索的方法将其编号包括：
[0024] S31、初始设置所有三角形的编号为未编号；设置当前覆铜区域的三角形填充编号为fp=1；设置当前待处理的覆铜多边形为第q=1个覆铜多边形；设置当前外围覆铜网格单元集合Frontp为空；
[0025] S32、对第q个覆铜多边形，从多边形的任意边e出发，找到这个边关联的左三角形t1，若所述左三角形t1的编号为未编号，设置三角形t1的编号为fp，将其加入到集合Frontp中，所述多边形任意边e的左三角形为包含该边e且三角形边e的方向与多边形边e的方向相同的三角形；
[0026] S33、从所述集合Frontp取出一个三角形t并将其从所述集合Frontp中移除，若所述三角形t的三个邻居三角形中的任何一个或多个邻居三角形的编号为未编号，且公共边不为任何多边形的边，则将所述三角形t的该一个或多个邻居三角形加入所述集合Frontp中，并将新加入所述集合Frontp的三角形的编号为fp，其中，所述公共边指与所述三角形t相邻的三角形与所述三角形t的公共边；
[0027] S34、判断所述集合Frontp是否为空集，若否，执行步骤S33，若是，设置fp=fp+1，q=q+1，执行步骤S32，直到处理完成所有统一的版图多边形中的覆铜多边形，结束。
[0028] 在一种可能的实施方式中，所述基于相同编号的三角形网格的面积和的大小判断孤岛包括：计算所有编号为正的三角形网格的面积，并将相同编号的三角形面积累加到以编号归类的面积和的集合中，面积和与编号形成一一对应关系，找出三角形面积和小于给定阈值对应的编号，所述编号对应的区域为检测出的孤岛。
[0029] 作为本申请的第二方面，还公开了一种用于集成电路版图检测孤岛的系统，包括版图转换模块、约束三角形生成模块、覆铜区域识别模块和孤岛判断模块；其中，所述版图转换模块用于将集成电路版图中的定义为孔的部分和覆铜的部分转换为版图多边形并进行布尔操作，形成统一的版图多边形；所述约束三角形生成模块用于基于统一的版图多边形及其边，对所述统一的版图多边形进行网格剖分并进行边交换，生成以所述统一的版图多边形的边为约束的约束三角形网格；所述覆铜区域识别模块用于基于约束三角形网格查找覆铜区域中的三角形网格并根据邻居搜索的方法将其编号；所述孤岛判断模块用于基于相同编号的三角形网格的面积和的大小判断孤岛。
[0030] 在一种可能的实施方式中，所述版图转换模块包括孔转换单元、覆铜转换单元、第三新的覆铜多边形布尔操作单元、第一新的覆铜多边形布尔操作单元和统一的版图多边形布尔操作单元；
[0031] 所述孔转换单元用于对集成电路版图中定义为孔的部分转换为挖空的多边形；其中，将孔的部分中由过孔引起的隔离垫片转换为第一挖空的多边形，当所述由过孔引起的隔离垫片的形状在集成电路的版图中定义为圆时，所述第一挖空的多边形为正多边形，当所述由过孔引起的隔离垫片的形状在集成电路的版图中定义为椭圆时，按椭圆在极坐标下等弧度取离散点，所述第一挖空的多边形为由离散点依次连成的多边形，当所述由过孔引起的隔离垫片的形状在集成电路的版图中定义为多边形时，所述第一挖空的多边形为版图中定义的多边形；将孔的部分中由集成电路版图中定义为覆铜的部分内的挖空圆、挖空椭圆和挖空多边形转换为第二挖空的多边形，当所述定义为覆铜的部分内的挖空圆时，所述第二挖空的多边形为正多边形，当所述定义为覆铜的部分内的挖空椭圆时，按椭圆在极坐标下等弧度取离散点，所述第二挖空的多边形为由离散点依次连成的多边形，当所述定义为覆铜的部分内的挖空多边形时，所述第二挖空的多边形为版图中定义的多边形；
[0032] 所述覆铜转换单元用于对集成电路版图中定义为覆铜的部分转换为覆铜的多边形；其中，将覆铜的部分中的走线按起始点、终止点和宽度转换为第一覆铜的多边形，所述第一覆铜的多边形为矩形，将覆铜的部分中由过孔引起的焊盘转换为第二覆铜的多边形，所述第二覆铜多边形在由所述隔离垫片转换为的挖空多边形内，当所述焊盘的形状在集成电路的版图中定义为圆时，所述第二覆铜的多边形为正多边形，当所述焊盘的形状在集成电路的版图中定义为椭圆时，按椭圆在极坐标下等弧度取离散点，所述第二覆铜的多边形为由离散点依次连成的多边形，当所述焊盘的形状在集成电路的版图中定义为多边形时，所述第二覆铜的多边形为版图中定义的多边形，将覆铜的其他部分转换为第三覆铜的多边形，当覆铜的其他部分定义为圆时，所述第三覆铜的多边形为正多边形，当覆铜的其他部分定义为椭圆时，按椭圆在极坐标下等弧度取离散点，所述第三覆铜的多边形为由离散点依次连成的多边形，当覆铜的其他部分定义为多边形时，所述第三覆铜的多边形为版图中定义的多边形；
[0033] 第三新的覆铜多边形布尔操作单元用于将所述第一覆铜的多边形和第三覆铜的多边形进行布尔或操作，形成第三新的覆铜多边形；
[0034] 所述第一新的覆铜多边形布尔操作单元用于将所述第三新的覆铜多边形分别和所述第一挖空的多边形、所述第二挖空的多边形进行布尔差操作，形成第一新的覆铜多边形；
[0035] 所述统一的版图多边形布尔操作单元用于将所述第一新的覆铜多边形和所述第二覆铜的多边形进行布尔或操作，形成统一的版图多边形。
[0036] 在一种可能的实施方式中，所述约束三角形生成模块包括第一单元、第二单元、第三单元、第四单元、第五单元和第六单元；其中，所述第一单元用于依据Delaunay剖分准则对所述统一的版图多边形的顶点进行网格剖分，形成网格剖分；所述第二单元用于收集网格剖分中所有不是两个三角形公共边的多边形的边，按边长排序形成集合Lost；
[0037] 所述第三单元用于从所述集合Lost中取出边长最长的边并将其从所述集合Lost中移除；所述第四单元从所述边长最长的边的一个顶点出发，搜索包含所述顶点且其他两个顶点位于边两侧的三角形，交换所述三角形与其邻居三角形的公共边，得到两个新的三角形，其中，所述邻居三角形为与该三角形有公共边的三角形；
[0038] 所述第五单元用于重复所述第三单元执行的内容直到所述边长最长的边为两个邻居三角形的公共边；
[0039] 所述第六单元用于判断所述集合Lost是否为空集，若否，则返回所述第三单元，若是，则生成所述统一的版图多边形中以所述统一的版图多边形的边为约束的约束三角形网格。
[0040] 在一种可能的实施方式中，所述覆铜区域识别模块包括第一识别单元、第二识别单元、第三识别单元和第四识别单元；
[0041] 其中第一识别单元用于初始设置所有三角形的编号为未编号；设置当前覆铜区域的三角形填充编号为fp=1；设置当前待处理的覆铜多边形为第q=1个覆铜多边形；设置当前外围覆铜网格单元集合Frontp为空；所述第二识别单元用于对第q个覆铜多边形，从多边形的任意边e出发，找到这个边关联的左三角形t1，若所述左三角形t1的编号为未编号，设置三角形t1的编号为fp，将其加入到集合Frontp中，所述多边形任意边e的左三角形为包含该边e且三角形边e的方向与多边形边e的方向相同的三角形；
[0042] 所述第三识别单元用于从所述集合Frontp取出一个三角形t并将其从所述集合Frontp中移除，若所述三角形t的三个邻居三角形中的任何一个或多个邻居三角形的编号为未编号，且公共边不为任何多边形的边，则将所述三角形t的该一个或多个邻居三角形加入所述集合Frontp中，并将新加入所述集合Frontp的三角形的编号为fp，其中，所述公共边指与所述三角形t相邻的三角形与所述三角形t的公共边；所述第四识别单元用于判断所述集合Frontp是否为空集，若否，返回第三识别单元，若是，设置fp=fp+1，q=q+1，返回第二识别单元，直到处理完成所有统一的版图多边形中的覆铜多边形。
[0043] 在一种可能的实施方式中，所述基于相同编号的三角形网格的面积和的大小判断孤岛包括：计算所有编号为正的三角形网格的面积，并将相同编号的三角形面积累加到以编号归类的面积和的集合中，面积和与编号形成一一对应关系，找出三角形面积和小于给定阈值对应的编号，所述编号对应的区域为检测出的孤岛。
[0044] （三）有益效果
[0045] 本申请通过将集成电路版图转变为可网格划分的形式，然后对其进行网格划分，并对划分的网格进行变换处理为生成以版图多边形的边界为约束的统一版图的约束三角形网格，提取覆铜区域内的三角形网格并根据邻居搜索的方法将其编号，并基于覆铜区域的网格的面积和来判断孔是否为孤岛；不仅避免如果不检测孤岛直接生产影响板的可靠性，还能避免集成电路版图的孤岛数量多，密集不易识别，靠人工去查找孤岛费时费力。
[0046] 本申请的其他优点、目标和特征在某种程度上将在随后的说明书中进行阐述，并且在某种程度上，基于对下文的考察研究对本领域技术人员而言将是显而易见的，或者可以从本申请的实践中得到教导。本申请的目标和其他优点可以通过下面的说明书来实现和获得。
附图说明
[0047] 以下参考附图描述的实施例是示例性的，旨在用于解释和说明本申请，而不能理解为对本申请的保护范围的限制。
[0048] 图1是本申请的方法流程图；
[0049] 图2是本申请的孤岛示意图；
[0050] 图3是本申请的孤岛填充后的示意图；
[0051] 图4是本申请约束三角形网格生成过程示意图；
[0052] 图5是本申请覆铜区域三角形网格编号示意图；
[0053] 图6是本申请的系统结构图；
[0054] 其中，1、版图转换模块；2、约束三角形生成模块；3、覆铜区域识别模块；4、孤岛判断模块。
具体实施方式
[0055] 为使本申请实施例的目的、技术方案和优点更加清楚，下面将结合本申请实施例中的附图，对本申请实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本申请一部分实施例，而不是全部的实施例。通常在此处附图中描述和示出的本申请实施例的组件可以以各种不同的配置来布置和设计。
[0056] 因此，以下对在附图中提供的本申请的实施例的详细描述并非旨在限制要求保护的本申请的范围，而是仅仅表示本申请的选定实施例。基于本申请中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其他实施例，都属于本申请保护的范围。
[0057] 应注意到：相似的标号和字母在下面的附图中表示类似项，因此，一旦某一项在一个附图中被定义，则在随后的附图中不需要对其进行进一步定义和解释。
[0058] 在本申请的上述描述中，需要说明的是，术语“一侧”、“另一侧”等指示的方位或位置关系为基于附图所示的方位或位置关系，或者是该申请产品使用时惯常摆放的方位或位置关系，仅是为了便于描述本申请和简化描述，而不是指示或暗示所指的装置或元件必须具有特定的方位、以特定的方位构造和操作，因此不能理解为对本申请的限制。此外，术语“第一”、“第二”等仅用于区分描述，而不能理解为指示或暗示相对重要性。
[0059] 如图1所示，本实施例提供了一种用于集成电路版图检测孤岛的方法，包括如下步骤：
[0060] S1、将集成电路版图中的定义为孔的部分和覆铜的部分转换为版图多边形并进行布尔操作，形成统一的版图多边形。
[0061] 在一些实施例中，所述将集成电路版图中的定义为孔的部分和覆铜的部分转换为版图多边形并进行布尔操作，形成统一的版图多边形包括：
[0062] S11、对集成电路版图中定义为孔的部分转换为挖空的多边形；其中，将孔的部分中由过孔引起的隔离垫片转换为第一挖空的多边形，当所述由过孔引起的隔离垫片的形状在集成电路的版图中定义为圆时，所述第一挖空的多边形为正多边形，当所述由过孔引起的隔离垫片的形状在集成电路的版图中定义为椭圆时，按椭圆在极坐标下等弧度取离散点，所述第一挖空的多边形为由离散点依次连成的多边形，当所述由过孔引起的隔离垫片的形状在集成电路的版图中定义为多边形时，所述第一挖空的多边形为版图中定义的多边形；将孔的部分中由集成电路版图中定义为覆铜的部分内的挖空圆、挖空椭圆和挖空多边形转换为第二挖空的多边形，当所述定义为覆铜的部分内的挖空圆时，所述第二挖空的多边形为正多边形，当所述定义为覆铜的部分内的挖空椭圆时，按椭圆在极坐标下等弧度取离散点，所述第二挖空的多边形为由离散点依次连成的多边形，当所述定义为覆铜的部分内的挖空多边形时，所述第二挖空的多边形为版图中定义的多边形；
[0063] S12、对集成电路版图中定义为覆铜的部分转换为覆铜的多边形；其中，将覆铜的部分中的走线按起始点、终止点和宽度转换为第一覆铜的多边形，所述第一覆铜的多边形为矩形，将覆铜的部分中由过孔引起的焊盘转换为第二覆铜的多边形，所述第二覆铜多边形在由所述隔离垫片转换为的挖空多边形内，当所述焊盘的形状在集成电路的版图中定义为圆时，所述第二覆铜的多边形为正多边形，当所述焊盘的形状在集成电路的版图中定义为椭圆时，按椭圆在极坐标下等弧度取离散点，所述第二覆铜的多边形为由离散点依次连成的多边形，当所述焊盘的形状在集成电路的版图中定义为多边形时，所述第二覆铜的多边形为版图中定义的多边形，将覆铜的其他部分转换为第三覆铜的多边形，当覆铜的其他部分定义为圆时，所述第三覆铜的多边形为正多边形，当覆铜的其他部分定义为椭圆时，按椭圆在极坐标下等弧度取离散点，所述第三覆铜的多边形为由离散点依次连成的多边形，当覆铜的其他部分定义为多边形时，所述第三覆铜的多边形为版图中定义的多边形；
[0064] S13、将所述第一覆铜的多边形和第三覆铜的多边形进行布尔或操作，形成第三新的覆铜多边形；
[0065] S14、将所述第三新的覆铜多边形分别和所述第一挖空的多边形、所述第二挖空的多边形进行布尔差操作，形成第一新的覆铜多边形；
[0066] S15、将所述第一新的覆铜多边形和所述第二覆铜的多边形进行布尔或操作，形成统一的版图多边形。
[0067] S2、基于统一的版图多边形及其边，对所述统一的版图多边形进行网格剖分并进行边交换，生成以所述统一的版图多边形的边为约束的约束三角形网格。
[0068] 统一的版图多边形通过Delaunay进行三角形网格剖分，并基于Delaunay划分的三角形网格生成统一的版图多边形的边为约束的约束三角形网格，即在统一的版图多边形中两种区域的边界上形成约束三角形网格，两种区域中一种区域为在统一的版图多边形中覆铜区域，覆铜区域包括了在集成电路版图中定义的覆铜的部分，还包括了经过了布尔操作后新生成覆铜部分，另一种区域为非覆铜区域，即挖空区域，挖空区域包括了在集成电路版图中定义的孔的部分，还包括经过了布尔操作后新生成的孔。
[0069] 在一些实施例中，如图4所示，所述对所述统一的版图多边形进行网格剖分并进行边交换，生成以所述统一的版图多边形的边为约束的约束三角形网格包括：S21、依据Delaunay剖分准则对所述统一的版图多边形的顶点进行网格剖分，形成网格剖分；S22、收集网格剖分中所有不是两个三角形公共边的多边形的边，按边长排序形成集合Lost；S23、从所述集合Lost中取出边长最长的边并将其从所述集合Lost中移除，如图4中的边 ；S24、从所述边长最长的边的一个顶点出发，搜索包含所述顶点且其他两个顶点位于边两侧的三角形，交换所述三角形与其邻居三角形的公共边，得到两个新的三角形，其中,所述边长最长的边即为步骤S23中取出并移除的边，所述邻居三角形为与该三角形有公共边的三角形；如图4中，从所述边 的一个顶点A出发，搜索包含所述顶点A且顶点C、D位于所述边两侧的三角形ΔACD，交换所述三角形ΔACD与其邻居三角形ΔDCE的公共边，得到三角形ΔACE与ΔEDA，其中，所述邻居三角形为与该三角形有公共边的三角形，交换所述三角形与其邻居三角形的公共边，得到两个新的三角形，其中，所述邻居三角形为与该三角形有公共边的三角形；S25、重复步骤S24直到所述边长最长的边为两个邻居三角形的公共边；S26、判断所述集合Lost是否为空集，若否，则转入步骤S23，若是，则生成所述统一的版图多边形中以所述统一的版图多边形的边为约束的约束三角形网格。
[0070] 在收集多边形边的时候是无差别对待，不论是覆铜多边形边还是挖孔多边形的边边构成封闭的孔（多边形）是输入决定的，一定会形成首尾相连的封闭线段集合。S3、基于约束三角形网格查找覆铜区域中的三角形网格并根据邻居搜索的方法将其编号。
[0071] 如图5，在一些实施例中，所述基于约束三角形网格查找覆铜区域中的三角形网格并根据邻居搜索的方法将其编号包括：S31、初始设置所有三角形的编号为未编号；设置当前覆铜区域的三角形填充编号为fp=1；设置当前待处理的覆铜多边形为第q=1个覆铜多边形；设置当前外围覆铜网格单元集合Frontp为空；S32、对第q个覆铜多边形，从多边形的任意边e出发，找到这个边关联的左三角形t1，若所述左三角形t1的编号为未编号，设置三角形t1的编号为fp，将其加入到集合Frontp中，所述多边形任意边e的左三角形为包含该边e且三角形边e的方向与多边形边e的方向相同的三角形；S33、从所述集合Frontp取出一个三角形t并将其从所述集合Frontp中移除，若所述三角形t的三个邻居三角形中的任何一个或多个邻居三角形的编号为未编号，且公共边不为任何多边形的边，则将所述三角形t的该一个或多个邻居三角形加入所述集合Frontp中，并将新加入所述集合Frontp的三角形的编号为fp，其中，所述公共边指与所述三角形t相邻的三角形与所述三角形t的公共边；S34、判断所述集合Frontp是否为空集，若否，执行步骤S33，若是，设置fp=fp+1，q=q+1，执行步骤S32，直到处理完成所有统一的版图多边形中的覆铜多边形，结束。
[0072] S4、基于相同编号的三角形网格的面积和的大小判断孤岛。如图5中，编号1、编号2、编号3、编号4和编号对应代表了不同的覆铜区域，未编号的部分则对应挖空区域。分别计算全为编号1的三角形网格的面积和，全为编号2的三角形网格的面积和，全为编号3的三角形网格的面积和，全为编号4的三角形网格的面积和，全为编号5的三角形网格的面积和，并根据不同编号的面积和的大小判断孤岛。
[0073] 在一些实施例中，所述基于相同编号的三角形网格的面积和的大小判断孤岛包括：计算所有编号为正的三角形网格的面积，并将相同编号的三角形面积累加到以编号归类的面积和的集合中，面积和与编号形成一一对应关系，找出三角形面积和小于给定阈值对应的编号，所述编号对应的区域为检测出的孤岛。
[0074] 通过将集成电路版图转变为可网格划分的形式，然后对其进行网格划分，并对划分的网格进行变换处理为生成以版图多边形的边界为约束的统一版图的约束三角形网格，提取覆铜区域内的三角形网格并根据邻居搜索的方法将其编号，并基于覆铜区域的网格的面积和来判断孔是否为孤岛；不仅避免如果不检测孤岛直接生产影响板的可靠性，还能避免集成电路版图的孤岛数量多，密集不易识别，靠人工去查找孤岛费时费力。
[0075] 如图6所示，作为本实施例的第二方面还提供了一种用于集成电路版图检测孤岛的系统，包括版图转换模块1、约束三角形生成模块2、覆铜区域识别模块3和孤岛判断模块4；其中，所述版图转换模块1用于将集成电路版图中的定义为孔的部分和覆铜的部分转换为版图多边形并进行布尔操作，形成统一的版图多边形；所述约束三角形生成模块2用于基于统一的版图多边形及其边，对所述统一的版图多边形进行网格剖分并进行边交换，生成以所述统一的版图多边形的边为约束的约束三角形网格；所述覆铜区域识别模块3用于基于约束三角形网格查找覆铜区域中的三角形网格并根据邻居搜索的方法将其编号；所述孤岛判断模块4用于基于相同编号的三角形网格的面积和的大小判断孤岛。
[0076] 所述版图转换模块1包括孔转换单元、覆铜转换单元、第三新的覆铜多边形布尔操作单元、第一新的覆铜多边形布尔操作单元和统一的版图多边形布尔操作单元；所述孔转换单元用于对集成电路版图中定义为孔的部分转换为挖空的多边形；其中，将孔的部分中由过孔引起的隔离垫片转换为第一挖空的多边形，当所述由过孔引起的隔离垫片的形状在集成电路的版图中定义为圆时，所述第一挖空的多边形为正多边形，当所述由过孔引起的隔离垫片的形状在集成电路的版图中定义为椭圆时，按椭圆在极坐标下等弧度取离散点，所述第一挖空的多边形为由离散点依次连成的多边形，当所述由过孔引起的隔离垫片的形状在集成电路的版图中定义为多边形时，所述第一挖空的多边形为版图中定义的多边形；将孔的部分中由集成电路版图中定义为覆铜的部分内的挖空圆、挖空椭圆和挖空多边形转换为第二挖空的多边形，当所述定义为覆铜的部分内的挖空圆时，所述第二挖空的多边形为正多边形，当所述定义为覆铜的部分内的挖空椭圆时，按椭圆在极坐标下等弧度取离散点，所述第二挖空的多边形为由离散点依次连成的多边形，当所述定义为覆铜的部分内的挖空多边形时，所述第二挖空的多边形为版图中定义的多边形；所述覆铜转换单元用于对集成电路版图中定义为覆铜的部分转换为覆铜的多边形；其中，将覆铜的部分中的走线按起始点、终止点和宽度转换为第一覆铜的多边形，所述第一覆铜的多边形为矩形，将覆铜的部分中由过孔引起的焊盘转换为第二覆铜的多边形，所述第二覆铜多边形在由所述隔离垫片转换为的挖空多边形内，当所述焊盘的形状在集成电路的版图中定义为圆时，所述第二覆铜的多边形为正多边形，当所述焊盘的形状在集成电路的版图中定义为椭圆时，按椭圆在极坐标下等弧度取离散点，所述第二覆铜的多边形为由离散点依次连成的多边形，当所述焊盘的形状在集成电路的版图中定义为多边形时，所述第二覆铜的多边形为版图中定义的多边形，将覆铜的其他部分转换为第三覆铜的多边形，当覆铜的其他部分定义为圆时，所述第三覆铜的多边形为正多边形，当覆铜的其他部分定义为椭圆时，按椭圆在极坐标下等弧度取离散点，所述第三覆铜的多边形为由离散点依次连成的多边形，当覆铜的其他部分定义为多边形时，所述第三覆铜的多边形为版图中定义的多边形；
[0077] 第三新的覆铜多边形布尔操作单元用于将所述第一覆铜的多边形和第三覆铜的多边形进行布尔或操作，形成第三新的覆铜多边形；所述第一新的覆铜多边形布尔操作单元用于将所述第三新的覆铜多边形分别和所述第一挖空的多边形、所述第二挖空的多边形进行布尔差操作，形成第一新的覆铜多边形；所述统一的版图多边形布尔操作单元用于将所述第一新的覆铜多边形和所述第二覆铜的多边形进行布尔或操作，形成统一的版图多边形。
[0078] 所述约束三角形生成模块2包括第一单元、第二单元、第三单元、第四单元、第五单元和第六单元；其中，所述第一单元用于依据Delaunay剖分准则对所述统一的版图多边形的顶点进行网格剖分，形成网格剖分；所述第二单元用于收集网格剖分中所有不是两个三角形公共边的多边形的边，按边长排序形成集合Lost；所述第三单元用于从所述集合Lost中取出边长最长的边并将其从所述集合Lost中移除；所述第四单元从所述边长最长的边的一个顶点出发，搜索包含所述顶点且其他两个顶点位于边两侧的三角形，交换所述三角形与其邻居三角形的公共边，得到两个新的三角形，其中，所述邻居三角形为与该三角形有公共边的三角形；所述第五单元用于重复所述第三单元执行的内容直到所述边长最长的边为两个邻居三角形的公共边；所述第六单元用于判断所述集合Lost是否为空集，若否，则返回所述第三单元，若是，则生成所述统一的版图多边形中以所述统一的版图多边形的边为约束的约束三角形网格。
[0079] 所述覆铜区域识别模块3包括第一识别单元、第二识别单元、第三识别单元和第四识别单元；其中第一识别单元用于初始设置所有三角形的编号为未编号；设置当前覆铜区域的三角形填充编号为fp=1；设置当前待处理的覆铜多边形为第q=1个覆铜多边形；设置当前外围覆铜网格单元集合Frontp为空；所述第二识别单元用于对第q个覆铜多边形，从多边形的任意边e出发，找到这个边关联的左三角形t1，若所述左三角形t1的编号为未编号，设置三角形t1的编号为fp，将其加入到集合Frontp中，所述多边形任意边e的左三角形为包含该边e且三角形边e的方向与多边形边e的方向相同的三角形；所述第三识别单元用于从所述集合Frontp取出一个三角形t并将其从所述集合Frontp中移除，若所述三角形t的三个邻居三角形中的任何一个或多个邻居三角形的编号为未编号，且公共边不为任何多边形的边，则将所述三角形t的该一个或多个邻居三角形加入所述集合Frontp中，并将新加入所述集合Frontp的三角形的编号为fp，其中，所述公共边指与所述三角形t相邻的三角形与所述三角形t的公共边；所述第四识别单元用于判断所述集合Frontp是否为空集，若否，返回第三识别单元，若是，设置fp=fp+1，q=q+1，返回第二识别单元，直到处理完成所有统一的版图多边形中的覆铜多边形。
[0080] 所述基于相同编号的三角形网格的面积和的大小判断孤岛包括：计算所有编号为正的三角形网格的面积，并将相同编号的三角形面积累加到以编号归类的面积和的集合中，面积和与编号形成一一对应关系，找出三角形面积和小于给定阈值对应的编号，所述编号对应的区域为检测出的孤岛。
[0081] 最后说明的是，以上实施例仅用以说明本申请的技术方案而非限制，尽管参照较佳实施例对本申请进行了详细说明，本领域的普通技术人员应当理解，可以对本申请的技术方案进行修改或者等同替换，而不脱离本申请技术方案的宗旨和范围，其均应涵盖在本申请的权利要求范围当中。
