基于GIS技术的双层PCB布线的空间剖分算法  

Spatial subdivision algorithm based on GIS technology for double-layer PCB routing

作　　者：杜晶 张剑 刘明玉 陈大涛 呙维[1] 高飞 赵雨慧 杨坤 Du Jing;Zhang Jian;Liu Mingyu;Chen Datao;Guo Wei;Gao Fei;Zhao Yuhui;Yang Kun(State Key Laboratory of Information Engineering in Surveying,Mapping&Remote Sensing,Wuhan University,Wuhan 430079,China;Fire Rescue Detachment of Jing’an District,Shanghai 200070,China;Huawei Terminal Co.,Ltd,Wuhan 430206,China)

机构地区：[1]武汉大学测绘遥感信息工程国家重点实验室,武汉430079 [2]上海市静安区消防救援支队,上海200070 [3]华为终端有限公司,武汉430206

出　　处：《计算机应用研究》2022年第5期1483-1490,共8页Application Research of Computers

摘　　要：双层印制电路板(PCB)通常空间结构及布线线形复杂、约束规则众多,而常用PCB空间结构简单、布线线形单一,不能有效利用PCB的空间关系及拓扑信息引导布线规划。为弥补以前工作的不足,提出一种基于GIS(geographic information system)技术的空间剖分算法,首先利用空间距离与几何要素拓扑关系进行分组预处理,然后引入矢栅一体化模型构建复杂空间及属性约束下的网络模型,基于该网络模型提取区域基准线并利用空间缓冲区技术得到空间剖分结果,从而引导布线规划。实验结果表明,该算法能够在满足所有设计规则的情况下实现100%的布线连通率,同时有效利用布线空间资源;提出的算法布线线形接近人工布线,对于实现复杂场景与多约束下的双层PCB自动化布线具有实际意义。Double-layer printed circuit board(PCB)usually has the complex spatial structure and the routing pattern,and many constraint rules.However,in the past researches,the spatial structure of PCB is simple and the routing pattern is single,and the spatial relationship and topological information of PCB can not be effectively used to guide the routing.In order to make up for the shortcomings of the previous work,this paper proposed a spatial subdivision algorithm based on geographic information system(GIS)technology.Firstly,it used the spatial distance and the topological relationship of the geometric elements for group preprocessing.Then it introduced the vector and grid model to construct the network model under the complex space and attribute constraints.Based on the network model,it extracted the regional reference line,and used the spatial buffer technology to obtain the spatial subdivision result for guiding the routing.Experimental results show that the proposed algorithm can achieve 100%routing connectivity under the condition that all design rules are met,and effectively utilize routing space resources.The routing shape of the proposed algorithm is close to manual routing,which is of practical significance to realize the automatic routing of double-layer PCB under complex scenes and multi-constraints.

关 键 词：空间剖分 中心线提取 贴边线提取 双层PCB布线 

分 类 号：TP391.72[自动化与计算机技术—计算机应用技术]