一种带挖孔多边形分割方法、系统及计算机程序产品与流程

摘要: 本发明涉及数据处理,尤其涉及一种带挖孔多边形分割方法、系统及计算机程序产品。背景技术:1、集成电路版图通常采用多边形对不同层中的图形区域进行描述。在实际集成电路...
一种带挖孔多边形分割方法、系统及计算机程序产品与流程

本发明涉及数据处理,尤其涉及一种带挖孔多边形分割方法、系统及计算机程序产品。

背景技术:

1、集成电路版图通常采用多边形对不同层中的图形区域进行描述。在实际集成电路版图中,为表示挖孔、避让区域或者内部空白区域,一个多边形内部可能设置一个或多个挖孔,从而形成带挖孔多边形。对于图形数据系统(graphic data system,gds)格式等集成电路版图数据格式,在进行数据转换或者后续处理时,通常需要将带挖孔多边形分割为多个不带挖孔的独立多边形,以满足相应的数据组织和存储要求。

2、现有技术在对带挖孔多边形进行分割时,通常需要根据挖孔边界与外围路径之间的位置关系确定切割位置,对挖孔路径与外围路径进行连接或者分裂。当待处理的带挖孔多边形包含较多路径结点和多个挖孔时,每次确定切割位置均可能需要在所述外围路径和各所述挖孔路径对应的路径线段中进行搜索;同时,随着切割过程不断进行,路径连接关系持续发生变化,使后续切割处理所涉及的路径线段数量增加。尤其对于大规模集成电路版图数据,上述处理方式会产生较大的计算量,导致带挖孔多边形的分割效率较低。

3、因此,如何降低带挖孔多边形分割过程中的计算量,提高大规模带挖孔多边形的分割效率,成为亟需解决的技术问题。

技术实现思路

1、本发明旨在提供一种带挖孔多边形分割方法、系统及计算机程序产品。

2、为提高带挖孔多边形分割过程中的处理效率,本发明技术方案是:

3、第一方面,一种带挖孔多边形分割方法,包括以下步骤:确定挖孔路径的第一极值点和第二极值点;以带挖孔多边形的外接矩形的横向延伸方向为x轴方向,以与所述x轴方向垂直的方向为y轴方向,沿x轴方向按预设间隔对所述带挖孔多边形进行竖直区间划分,将外围路径的路径线段和所述挖孔路径的路径线段确定为待搜索路径线段,并将所述待搜索路径线段、所述第一极值点和所述第二极值点分配至对应的竖直区间;并行处理各所述竖直区间,针对分配至各竖直区间的第一极值点,从所述第一极值点沿y轴正方向发射垂直射线,确定所述垂直射线与对应竖直区间内的待搜索路径线段之间的交点,将距离所述第一极值点最近的交点确定为第一切割点,调整所述第一极值点和所述第一切割点的连接关系;针对分配至各竖直区间的第二极值点,从所述第二极值点沿y轴负方向发射垂直射线,确定所述垂直射线与对应竖直区间内的待搜索路径线段之间的交点,将距离所述第二极值点最近的交点确定为第二切割点,调整所述第二极值点和所述第二切割点的连接关系,得到各不带挖孔的闭合路径。通过上述技术方案,可以通过竖直区间划分缩小第一极值点和第二极值点确定切割点时的路径线段搜索范围,利用各竖直区间的并行处理降低带挖孔多边形分割过程中的计算量,提高大规模多边形的处理效率。

4、可选地,所述确定所述挖孔路径的第一极值点和第二极值点,包括:遍历所述挖孔路径的各路径结点,根据各所述路径结点的y坐标确定所述挖孔路径在y轴方向上的上侧极值位置和下侧极值位置;将位于所述上侧极值位置的路径结点确定为所述挖孔路径的第一极值点,将位于所述下侧极值位置的路径结点确定为所述挖孔路径的第二极值点;当所述上侧极值位置或所述下侧极值位置由水平路径段形成时,将所述水平路径段中x坐标最大的路径结点确定为所述第一极值点或所述第二极值点。通过上述技术方案,可以为每一挖孔路径确定唯一的第一极值点和第二极值点,避免同一水平极值位置上的多个路径结点重复参与后续切割,提高第二极值点确定及切割处理的确定性。

5、可选地,所述调整所述第一极值点和所述第一切割点的连接关系,包括:确定所述第一切割点所在的目标路径线段;在所述第一切割点处插入成对的切割结点,将所述第一极值点分裂为两个子结点,调整所述切割结点和所述子结点之间的连接关系,使所述第一极值点所在的挖孔路径与所述第一切割点所在的目标路径线段所属的路径建立连接。通过上述技术方案,可以利用第一极值点与第一切割点之间的路径重连,将原本相互独立的挖孔路径与其他路径建立连接,为后续路径分裂形成不带挖孔的闭合路径提供基础。

6、可选地,所述调整所述第二极值点和所述第二切割点的连接关系,得到各不带挖孔的闭合路径,包括:确定所述第二切割点所在的目标路径线段;在所述第二切割点处插入成对的切割结点,将所述第二极值点分裂为两个子结点,调整所述切割结点和所述子结点之间的连接关系,使连接后的路径在所述第二极值点与所述第二切割点之间发生分裂,形成不带挖孔的闭合路径。通过上述技术方案,可以在第一极值点连接形成的整体路径基础上,通过第二极值点切割将所述整体路径逐步分裂为多个不带挖孔的闭合路径,实现带挖孔多边形的有效分割。

7、可选地,所述带挖孔多边形分割方法,调整所述第一极值点和所述第一切割点的连接关系,或调整所述第二极值点和所述第二切割点的连接关系之前,还包括:将对应同一目标路径线段的第一极值点或第二极值点进行关联存储;根据所述目标路径线段的路径方向,对第一极值点或第二极值点进行排序,按照排序结果依次执行路径连接或路径分裂。通过上述技术方案,可以将对应同一目标路径线段的第一极值点或第二极值点集中处理,避免切割过程中频繁更新和扩展待搜索路径线段集合,从而降低路径搜索及切割处理的复杂度。

8、可选地,所述沿x轴方向按预设间隔对所述带挖孔多边形进行竖直区间划分,包括:根据所述带挖孔多边形的外接矩形以及路径结点数量确定竖直区间数量,沿x轴方向进行竖直区间划分;其中,各所述竖直区间采用左闭右开的区间形式,且各所述竖直区间共同覆盖所述外围路径。通过上述技术方案,可以根据路径结点数量合理确定竖直区间数量,在降低分区管理开销的同时提高并行处理能力,从而兼顾分区效率和整体处理效率。

9、可选地,所述沿x轴方向按预设间隔对所述带挖孔多边形进行竖直区间划分之前,还包括:对所述外围路径和所述挖孔路径的各路径结点坐标进行缩放变换,使各所述路径结点的x坐标具有第一奇偶性;相应地,将相邻所述竖直区间之间的分区边界的x坐标设置为具有第二奇偶性,以使各所述分区边界的x坐标与各所述路径结点、所述第一极值点和所述第二极值点的x坐标相互错位,从而避免所述第一极值点和所述第二极值点落在分区边界上。通过上述技术方案,可以利用坐标缩放形成的奇偶错位,确保路径特征点不会落入分区边界而导致区间归属不明确,减少后续切割处理中的判断复杂度。

10、可选地,所述外围路径和所述挖孔路径采用相反的遍历方向;根据所述外围路径与所述挖孔路径相反的路径方向调整切割位置处路径结点的连接关系,使切割后的路径按照统一的方向关系建立连接。通过上述技术方案,可以利用外围路径与挖孔路径相反的遍历方向,使切割后的路径以统一方式连接,保证切割结果的正确性与一致性。

11、可选地,所述带挖孔多边形分割方法,包括:获取带挖孔多边形的外围路径和挖孔路径,对所述外围路径和所述挖孔路径进行预处理;根据所述闭合路径生成不带挖孔多边形,对顶点数量超出预设限制的不带挖孔多边形进行进一步分割,得到符合目标格式要求的多边形。

12、可选地,所述带挖孔多边形分割方法,将所述待搜索路径线段分配至对应的竖直区间,包括:对于跨越至少两个所述竖直区间的路径线段,确定所述路径线段与所述竖直区间的分区边界之间的交点;在所述交点处插入中转点,根据所述中转点将所述路径线段划分为分别位于对应竖直区间的路径子段,将各所述路径子段分配至对应的竖直区间;其中,所述中转点用于保持所述路径线段的路径连接关系,在根据所述闭合路径生成不带挖孔多边形时不作为所述不带挖孔多边形的路径结点。通过上述技术方案,可以在保持原路径连续性的同时,将跨越多个竖直区间的路径线段拆分至对应区间,为各竖直区间独立并行处理提供基础,且不会额外增加最终多边形的有效路径结点。

13、第二方面,本发明提供一种带挖孔多边形分割系统,包括:极值点确定模块,确定挖孔路径的第一极值点和第二极值点;竖直分区模块,以带挖孔多边形的外接矩形的横向延伸方向为x轴方向,以与所述x轴方向垂直的方向为y轴方向,沿x轴方向按预设间隔对所述带挖孔多边形进行竖直区间划分,将外围路径的路径线段和所述挖孔路径的路径线段确定为待搜索路径线段,并将所述待搜索路径线段、所述第一极值点和所述第二极值点分配至对应的竖直区间;第一极值点连接模块,并行处理各所述竖直区间,针对分配至各竖直区间的第一极值点,从所述第一极值点沿y轴正方向发射垂直射线,确定所述垂直射线与对应竖直区间内的待搜索路径线段之间的交点,将距离所述第一极值点最近的交点确定为第一切割点,调整所述第一极值点和所述第一切割点的连接关系;第二极值点分裂模块,针对分配至各竖直区间的第二极值点,从所述第二极值点沿y轴负方向发射垂直射线,确定所述垂直射线与对应竖直区间内的待搜索路径线段之间的交点,将距离所述第二极值点最近的交点确定为第二切割点,调整所述第二极值点和所述第二切割点的连接关系,得到各不带挖孔的闭合路径。通过上述技术方案,各功能模块能够协同完成带挖孔多边形的分区、并行切割及结果生成,提高大规模版图数据中带挖孔多边形的分割效率。

14、可选地,所述带挖孔多边形分割系统,还包括:路径预处理模块,获取带挖孔多边形的外围路径和挖孔路径,对所述外围路径和所述挖孔路径进行预处理;多边形生成模块,根据所述闭合路径生成不带挖孔多边形,对顶点数量超出预设限制的不带挖孔多边形进行进一步分割,得到符合目标格式要求的多边形。

15、可选地,所述竖直分区模块在沿x轴方向进行竖直区间划分之前,对所述外围路径和所述挖孔路径的各路径结点坐标进行缩放变换,使各所述路径结点的x坐标具有第一奇偶性,并将相邻所述竖直区间之间的分区边界的x坐标设置为具有第二奇偶性,以使各所述分区边界的x坐标与各所述路径结点、所述第一极值点和所述第二极值点的x坐标相互错位。

16、可选地,所述第一极值点连接模块,从各第一极值点沿y轴正方向确定第一切割点,将所述第一切割点所在的路径线段确定为目标路径线段,将对应同一目标路径线段的第一极值点进行关联存储,按照所述目标路径线段的路径方向进行排序;按照排序结果依次在第一切割点处插入成对的切割结点,将第一极值点分裂为两个第一极值点结点,通过调整所述切割结点和所述第一极值点结点之间的前向指针和后向指针,建立所述第一极值点所在的挖孔路径与所述第一切割点所在的路径连接;所述第二极值点分裂模块,从各第二极值点沿y轴负方向确定第二切割点,将所述第二切割点所在的路径线段确定为目标路径线段,将对应同一目标路径线段的第二极值点进行关联存储,按照所述目标路径线段的路径方向进行排序;按照排序结果依次在第二切割点处插入成对的切割结点,将第二极值点分裂为两个第二极值点结点,通过调整所述切割结点和所述第二极值点结点之间的前向指针和后向指针,形成不带挖孔的闭合路径。通过上述技术方案,可以对同一目标路径线段对应的第一极值点和第二极值点进行集中排序处理,通过路径结点指针关系的调整实现路径连接和路径分裂,减少重复搜索及路径结构更新所带来的计算开销。

17、第三方面,本发明提供一种计算机程序产品,包括计算机程序,该计算机程序被处理器执行时实现上述的一种带挖孔多边形分割方法的步骤。通过计算机程序实现上述带挖孔多边形分割过程,在保证分割结果满足目标格式要求的同时提高数据处理效率。

18、本发明通过将路径线段、第一极值点和第二极值点分配至对应的竖直区间,使各竖直区间仅在本区间范围内搜索切割点,缩小了搜索范围;从挖孔路径的第一极值点沿y轴正方向确定第一切割点,调整所述第一极值点所在挖孔路径与所述第一切割点所在路径之间的连接关系,使所述挖孔路径与外围路径或其他挖孔路径建立连接,再从第二极值点沿y轴负方向确定第二切割点,调整所述第二极值点所在挖孔路径与所述第二切割点所在路径之间的连接关系;同时,将对应同一目标路径线段的第一极值点或第二极值点进行关联存储,按照目标路径线段的路径方向排序后依次执行切割,避免每处理一个第一极值点或第二极值点均重新搜索更新路径线段集合,减少重复的路径搜索和切割处理,从而降低带挖孔多边形分割过程中的计算量,提高带挖孔多边形的分割效率。

19、为让发明的上述特征和优点能更明显易懂,下文特举实施例,配合所附图式作详细说明如下。