一种自动测试系统设计原理图的自动生成平台及其方法

摘要

本发明是一种自动测试系统设计原理图的自动生成平台及其方法，该平台包括仪器设备资源与连接约束关系的输入模块、数据库模块、数据库管理模块、参数选择和预处理模块、自动布局模块、自动布线模块、绘制结果显示和保存模块。用户通过仪器设备资源与连接约束关系的输入模块输入数据，参数选择和预处理模块根据用户选择的参数对仪器进行分组定级，自动布局模块进行自动布局操作，自动布线模块完成布线操作。本发明方法主要是根据用户对信息类型的选择，提出一种基于最少线交叉的方法完成自动布局，运用朝向目标的线探索布线算法完成各仪器端口之间的连接。本发明可实现仪器模型的快速、高效布局，满足实际应用设计原理图的绘制要求。

说明书

技术领域

本发明属于自动测试技术领域，具体涉及一种自动测试系统设计原理图自动生成的平台及其方法。

背景技术

通常把以计算机为中心，在程控指令的控制下，能自动完成某种测试任务而组合起来的测量仪器和其他设备的有机整体称为自动测试系统(Automatic Test System，简称ATS)。自动测试系统中的各种设备都是可程控的，称为自动测试设备(Automatic TestEquipment，简称ATE)。近几年来，自动测试系统正朝着开放性、通用化、模块化的方向发展。自动测试系统的快速发展，对自动测试系统的自动化设计提出了更高的要求。但作为系统设计的重要组成部分的硬件设计还处于手工设计阶段。其中设计原理图的手工绘制要求绘制者既要对电路全局有概括了解，同时又要对电路图的绘制技巧十分熟悉。另一方面手工绘制易产生错误，给设计工作带来很大困难。手工绘制工作在设计标准化、设计质量、设计效率、设计资料存储、设计更新等方面存在很大的局限性，给设计工作带来工作量大、成本高、效率低等诸多问题。因此，实现设计原理图的自动生成是实现自动测试系统硬件自动化设计的一个关键环节，对于提高自动测试系统硬件设计工作的效率和质量，降低硬件后期维护的难度具有重要意义。

设计原理图的自动生成由两个紧密联系的部分组成，即自动布局和自动布线。自动布局是将测试相关的仪器模型合理的排放在绘制平面上，使得绘制出的图纸满足目标要求，布局效果的好坏直接影响图纸的质量，是设计原理图自动生成的关键部分。目前应用于工业印制电路板领域的自动布局算法已日渐成熟，但是这些方法还很难真正应用于设计原理图自动生成的布局系统中，主要是因为自动测试系统的设计原理图并不将走线长度及布局密度作为主要的考虑因素，而是更注重布局的美观，规则以及良好的可读性。设计原理图的自动布局的原则主要包括：保证图中信号的流向一致，通常为由左至右；保证连接关系紧密的仪器模型绘制位置相近并距离合适，连线交叉次数最少；保证整个布局的均匀，结构清晰；保证为后续的布线工作提供方便。因此需要按照设计原理图绘制的具体要求，设计适合的自动布局算法实现绘制的自动布局。

自动布线是完成具有连接关系的仪器模型的端口之间的布线，直观的描述端口之间的连接关系。设计原理图的自动布线的原则主要包括：保证高的设计成功率，其中主要的是指布线成功率；保证连线准确无误；确保美观性，折角为直角，尽量减少线交叉，布线不一定要求最短；恰当的处理打点问题。所谓打点是指当一个仪器端口同时输出到几个仪器端口时，这条唯一的输出信号线就成了公共信号线，需要在几条输入信号线和这条公共信号线相交的地方打上圆点。打点时既不能错打，也不能漏打。自动布线算法主要分为两类：有网格自动布线算法和无网格自动布线算法。有网格自动布线算法出现的比较早，无网格自动布线算法是在近二十几年内才出现的。有网格自动布线算法要求存储所有网点的信息，因此所需存储量相当可观。网格的缩小导致了PCB上网格点成平方倍的增长，因而存储量和计算时间也以快于平方倍的速度在增长。

发明内容

本发明的目的在于克服目前自动测试系统领域人工绘制设计原理图手段的不足，提出一种自动测试系统设计原理图的自动生成平台及其方法。

一种自动测试系统设计原理图的自动生成平台，包括：仪器设备资源与连接约束关系的输入模块、数据库模块、数据库管理模块、参数选择和预处理模块、自动布局模块、自动布线模块、以及绘制结果显示和保存模块。

所述的仪器设备资源与连接约束关系的输入模块用于将用户输入的数据传送给数据库模块中进行保存，所述的用户输入的数据包括：仪器信息、信号类型、仪器的连接关系、仪器大小范围信息以及仪器包容矩形信息。所述的数据库管理模块用于对数据库模块中存储的数据进行添加、修改和删除操作。所述的参数选择和预处理模块根据用户选择的信号类型，从数据库模块中选取与所选择信号类型相关的仪器信息和仪器的连接关系，根据仪器所属的信号类型，对仪器进行分组，再按照仪器的功能，以仿真仪器、仿真调理仪器、开关仪器、验证调理仪器和验证仪器的顺序，对各组仪器进行定级，以确保图纸中信号走线连接的仪器的类型从左至右依次为仿真仪器、仿真调理仪器、开关仪器、验证调理仪器和验证仪器，并将分组、定级后的数据输出到自动布局模块。所述的自动布局模块根据参数选择和预处理模块输入的数据，采用基于最少线交叉的自动布局方法，从数据库模块中获取相关仪器的数据：仪器的连接关系、仪器的信息、仪器大小范围信息和仪器包容矩形信息，对每组仪器按照级数由低到高的顺序，分别进行相邻两级的仪器模型的自动布局操作，直到完成对各组仪器的布局操作，并将生成的布局结果输出到自动布线模块，所述的最少线交叉的自动布局方法，是在已知仪器间端口连接关系的基础上，通过两级仪器连接的级联关系矩阵，找到线交叉最少时的两级仪器排列情况，确定两级仪器的行布局。所述的自动布线模块根据输入的布局结果，生成待布线网，得到仪器连接路径和路径节点信息并存储到数据库模块中，采用朝向目标的线探索布线方法，完成布线操作，并将完成布线的仪器连接图以及布线失败路径信息作为绘制结果输出给绘制结果显示和保存模块，所述的朝向目标的线探索布线方法，是以带有预定目标的探索线段为基本元素，进行具有方向性和目标性的探索，探索线段以一个端点为起始点，通过不断选择试探点和在横纵向探索方向间的切换，绕过障碍物，到达预定目标。所述绘制结果显示和保存模块将绘制结果显示给用户，并将布线失败路径信息保存到数据库模块中。

应用上述自动生成平台的自动测试系统设计原理图的自动生成方法，具体包括以下步骤：

步骤一、用户通过仪器设备资源与连接约束关系的输入模块将仪器信息、信号类型、仪器的连接关系、仪器大小范围信息以及仪器包容矩形信息输入，并存储在数据库模块中；对数据库模块中存储的数据，用户通过数据库管理模块进行添加，修改和删除操作。

步骤二、用户通过参数选择和预处理模块，根据绘制的需要选择信号类型，然后参数选择和预处理模块从数据库模块中选取与所选择信号类型相关的仪器设备信息和仪器设备的连接关系，根据仪器所属的不同信号类型，对仪器进行分组，再按照仪器的不同功能，以仿真仪器、仿真调理仪器、开关仪器、验证调理仪器和验证仪器的顺序，对各组仪器进行定级，以确保图纸中信号走线连接的仪器类型从左至右依次为仿真仪器、仿真调理仪器、开关仪器、验证调理仪器和验证仪器，最后参数选择和预处理模块将分组、定级后的数据输出到自动布局模块。

步骤三、自动布局模块将分组、定级后的数据，根据基于最少线交叉的自动布局方法，从数据库模块中获取相关仪器的仪器信息、信号类型、仪器的连接关系、仪器大小范围信息以及仪器包容矩形信息，对每组仪器按照级数由低到高的顺序，分别进行相邻两级的仪器模型的自动布局操作，直到完成对各组仪器的布局操作，最后自动布局模块将布局结果输出给自动布线模块。

步骤四、自动布线模块根据输入的布局结果生成待布线网，然后采用朝向目标的线探索布线方法，完成布线操作并将完成布线的仪器连接图以及布线失败路径信息作为绘制结果输出给绘制结果显示和保存模块。所述的待布线网的生成具体是：读取布局结果，选择相邻两级仪器中端口数目较大的一级仪器作为布线的起点，并对该级仪器的每一个仪器，按照仪器中心端口开始向两端扩散布线的原则确定仪器端口布线的顺序，生成仪器端口连接的路径信息，再结合仪器包容矩形坐标表中保存的仪器的绘制坐标信息，得到待布线的端口对的坐标信息，将得到的连接路径和路径节点信息存储在数据库模块中。

步骤五、用户通过绘制结果显示和保存模块查看绘制结果，绘制结果显示和保存模块将布线失败路径信息保存到数据库模块中。

步骤三中所述的基于最少线交叉的自动布局方法，是在已知仪器间端口连接关系的基础上，通过两级仪器连接的级联关系矩阵，找到线交叉最少时的两级仪器排列情况，确定两级仪器的行布局。步骤四中所述的朝向目标的线探索布线方法是以带有预定目标的探索线段为基本元素，进行具有方向性和目标性的探索，探索线段以一个端点为起始点，通过不断选择试探点和在横纵向探索方向间的切换，绕过障碍物，到达预定目标。

本发明的优点和积极效果在于：(1)建立了自动测试系统仪器设备资源、信号类型和仪器间连接关系的数据库管理系统，便于系统的维护；(2)基于最少线交叉的自动布局方法所实现的布局效果满足设计原理图的绘制要求，实现了美观、快速的自动布局；(3)结合朝向目标的线探索思想、待布线网布线顺序的确定和布线后期优化的自动布线方法准确、高效的实现了仪器间端口的连接；(4)搭建了一个统一的设计原理图自动生成的平台，便于平台在不同自动测试系统中的应用，有利于平台性能的提升。

附图说明

图1是本发明自动测试系统设计原理图自动生成平台的结构示意图；

图2是本发明自动测试系统设计原理图的自动生成方法的步骤流程图；

图3是本发明自动生成方法中的基于最少线交叉的自动布局方法的流程图；

图4是本发明自动生成方法中的基于朝向目标的线探索自动布线方法的流程图。

图中：

1.仪器设备资源与连接约束关系的输入模块          2.数据库模块

3.数据库管理模块      4.参数选择和预处理模块    5.自动布局模块

6.自动布线模块        7.绘制结果显示和保存模块

具体实施方式

下面将结合附图和实施例对本发明作进一步的详细说明。

本发明是一种自动测试系统设计原理图的自动生成平台，如图1所示，包括仪器设备资源与连接约束关系的输入模块1、数据库模块2、数据库管理模块3、参数选择和预处理模块4、自动布局模块5、自动布线模块6以及绘制结果显示和保存模块7。

仪器设备资源与连接约束关系的输入模块1是设计原理图自动生成平台的入口，用户通过仪器设备资源与连接约束关系的输入模块1输入数据，输入数据包括：仪器信息、信号类型、仪器的连接关系、仪器大小范围信息以及仪器包容矩形信息。数据库模块2将仪器设备资源与连接约束关系的输入模块1的输入数据按照设计好的数据库格式存储起来，以关系数据表的形式存在，具体将数据对应保存在仪器信息表、信号类型表、仪器的连接关系表、仪器大小范围信息表以及仪器包容矩形坐标表中。此外，数据库模块2还创建了仪器连接路径表、路径节点坐标信息表和布线失败路径信息表。各数据表将在后面具体给出。数据库模块2为参数选择和预处理模块4、自动布局模块5、绘制结果显示和保存模块7提供信息支持。自动布线模块6、绘制结果显示和保存模块7与数据库模块2相连，为数据库模块2提供数据。数据库管理模块3与数据库模块2连接，用户通过数据库管理模块3可对数据库模块2中存储的数据进行添加、修改和删除等操作。数据库管理模块3的加入为数据库模块2的维护提供了必要的保障。

参数选择和预处理模块4根据用户选择的信号类型，从数据库模块2中选取与所选择信号类型相关的仪器信息和仪器的连接关系，将所选择的仪器根据仪器所属的不同信号类型，对仪器进行分组，再按照仪器的不同功能，以仿真仪器、仿真调理仪器、开关仪器、验证调理仪器和验证仪器的顺序，对各组仪器进行定级，以确保图纸中信号走线连接的仪器类型从左至右依次为仿真仪器、仿真调理仪器、开关仪器、验证调理仪器和验证仪器，并将分组、定级后的结果输出到自动布局模块5。所述的信号类型由用户根据绘制的需要进行选择，可以选择多个信号类型，如直流信号、交流信号、电阻信号。例如，现在用户选择的信号类型为直流信号，那么根据直流信号类型，该类型信号可以由D/A板卡产生，由数字万用表验证，从数据库模块2中选择D/A板卡、数字万用表等的仪器信息和仪器的连接关系。因为选择的信号类型只是一种，所以只有一组，对这一组仪器按照仪器的功能，以仿真仪器PXI-6723、仿真调理器SAM、开关仪器PXI-2575、验证调理仪器VAM、数字万用表PXI-4070的顺序进行定级。其中PXI-6723是NI(National Instrument)仪器公司D/A的一种型号、SAM(Simulation Adjusting Module)是仿真调理模块的缩写，PXI-2575是NI公司开关的一种型号、VAM(Verification Adjusting Module)是验证调理模块的缩写，PXI-4070是NI公司万用表的一种型号，这些型号是本发明实施例所采用的，用户可以根据信号需求进行具体仪器的选择。

自动布局模块5根据参数选择和预处理模块4输入的结果，从数据库模块2中获取相关仪器的数据，采用本发明提出的基于最少线交叉的自动布局方法，对每组仪器按照级数由低到高的顺序，分别进行相邻两级的仪器模型的自动布局操作，直到完成对各组仪器的布局操作，生成的布局结果输出到自动布线模块6中。在布局过程中，从数据库模块2中获取的相关仪器的数据包括：仪器的连接关系、仪器的信息、仪器大小范围信息和仪器包容矩形信息。所述的最少线交叉的自动布局方法，是以两级连接的线交叉最少作为主要布局目标，在已知仪器间端口连接关系的基础上，通过两级仪器连接的级联关系矩阵，分析两级仪器不同排列的线交叉情况，找到线交叉最少时的两级仪器排列情况，确定两级仪器的行布局。

自动布线模块6连接绘制结果显示和保存模块7，根据输入的布局结果生成待布线网，生成仪器连接路径和路径节点信息，并将仪器连接路径和路径节点信息存储到数据库模块2中对应的仪器连接路径表和路径节点坐标信息表中，并采用朝向目标的线探索布线方法，完成布线操作，将布线完成得到的绘制结果输出给绘制结果显示和保存模块7。所述的绘制结果包括完成布线的仪器连接图以及布线失败路径信息。自动布局模块5和自动布线模块6是整个平台的核心模块，这两个模块的性能是整个平台性能的体现。所述的待布线网的生成是指分析已完成布局的各级仪器信息，读取待布线的两级仪器的信息，选择其中端口数目较大的一级仪器作为布线的起点，对该级仪器中的每一个仪器，按照该仪器中心端口开始向两端扩散布线的原则确定仪器端口布线的顺序，生成仪器端口连接的路径信息，存放在仪器连接路径表中，再结合仪器包容矩形坐标表中保存的仪器的绘制坐标信息，计算出待布线的端口对的坐标信息，保存在路径节点坐标信息表中。所述的朝向目标的线探索布线方法，是以带有预定目标或终点的探索线段为基本元素，进行具有方向性和目标性的探索，通过不断选择试探点和在横纵向探索方向间的切换，绕过障碍物，到达预定目标或终点。探索线段以一个端点为起始点，另一个端点为目标点，探索线段由起始点发出，除一些特殊情况外，始终朝着目标点前进，除了一些特殊情况，探索基本上在以两个端点所确定的矩形框内进行。

绘制结果显示和保存模块7将得到的绘制结果显示给用户，并将布局失败路径信息保存在数据库模块2中的布线失败路径信息表中。

数据库模块2中存储的各关系数据表，具体如下面表1～表8所示。其中表1～表5用于存储仪器设备资源与连接约束关系的输入模块1中输入的数据。自动布线模块6生成连接路径和路径节点信息存储在表6与表7中，绘制结果显示和保存模块7将布局失败路径信息存储到表8中。

表1仪器信息表

  字段  类型  描述  InstruName  VARCHAR  仪器名称  InstruFuncID  CHAR(1)  仪器功能ID  PortType  CHAR(1)  端口类型  PortID  INTEGER  端口序号  PortName  VARCHAR  端口名称  PortPinName  VARCHAR  端口引脚名称

表2信号类型表

  字段  类型  描述  SigTypeName  VARCHAR(21)  信号类型  SigTypeNum  INTEGER  信号类型序号

表3仪器的连接关系表

  字段  类型  描述  ConnectPathID  INTEGER  连接通路ID  SigTypeNum  INTEGER  信号类型ID  SigName  VARCHAR(100)  信号名称  Simul_InstruName  VARCHAR(100)  仿真仪器名称  Simul_InstruID  INTEGER  仿真仪器编号  Simul_InputID  INTEGER  仿真输入端口ID  Simul_InputName  VARCHAR(100)  仿真输入端口名称  Simul_InputPin  VARCHAR(100)  仿真输入端口接线引脚  Simul_OutputID  INTEGER  仿真输出端口ID  Simul_OutputName  VARCHAR(100)  仿真输出端口名称  Simul_OutputPin  VARCHAR(100)  仿真输出端口接线引脚  SimulAdjust_InstruName  VARCHAR(100)  仿真调理仪器名称  SimulAdjust_InstruID  INTEGER  仿真调理仪器编号  SimulAdjust_InputID  INTEGER  仿真调理输入端口ID  SimulAdjust_InputName  VARCHAR(100)  仿真调理输入端口名称  SimulvAdjust_InputPin  VARCHAR(100)  仿真调理输入端口接线引脚  SimulAdjust_OutputID  INTEGER  仿真调理输出端口ID  SimulAdjust_OutputName  VARCHAR(100)  仿真调理输出端口名称

  SimulAdjust_OutputPin  VARCHAR(100)  仿真调理输出端口接线引脚  Switch_InstruName  VARCHAR(100)  开关仪器名称  Switch_InstruID  INTEGER  开关仪器编号  Switch_InputID  INTEGER  开关输入端口ID  Switch_InputName  VARCHAR(100)  开关输入端口名称  Switch_InputPin  VARCHAR(100)  开关输入端口接线引脚  Switch_OutputID  INTEGER  开关输出端口ID  Switch_OutputName  VARCHAR(100)  开关输出端口名称  Switch_OutputPin  VARCHAR(100)  开关输出端口接线引脚  CheckAdjust_InstruName  VARCHAR(100)  验证调理仪器名称  CheckAdjust_InstruID  INTEGER  验证调理仪器编号  CheckAdjust_InputID  INTEGER  验证调理输入端口ID  CheckAdjust_InputName  VARCHAR(100)  验证调理输入端口名称  CheckAdjust_InputPin  VARCHAR(100)  验证调理输入端口接线引脚  CheckAdjust_OutputID  INTEGER  验证调理输出端口ID  CheckAdjust_OutputName  VARCHAR(100)  验证调理输出端口名称  CheckAdjust_OutputPin  VARCHAR(100)  验证调理输出端口接线引脚  Check_InstruName  VARCHAR(100)  验证仪器名称  Check_InstruID  INTEGER  验证仪器编号  Check_InputID  INTEGER  验证输入端口ID  Check_InputName  VARCHAR(100)  验证输入端口名称  Check_InputPin  VARCHAR(100)  验证输入端口接线引脚  Check_OutputID  INTEGER  验证输出端口ID  Check_OutputName  VARCHAR(100)  验证输出端口名称

  Check_OutputPin  VARCHAR(100)  验证输出端口接线引脚

表4仪器大小范围信息表

  字段  类型  描述  InstruName  VARCHAR  仪器型号  Length  INTEGER  仪器内矩形框长度  Width  INTEGER  仪器内矩形框宽度  Pin-Length  INTEGER  仪器引脚长度  Rect_Length  INTEGER  包容矩形长度  Rect_Width  INTEGER  包容矩形宽度

表5仪器包容矩形坐标表

  字段  类型  描述  InstruName  VARCHAR  仪器名称  SigTypeNum  INTEGER  信号类型编号  TL_x  INTEGER  左上横坐标  TL_y  INTEGER  左上纵坐标  BR_x  INTEGER  右下横坐标  BR_y  INTEGER  右下纵坐标

表6仪器连接路径表

  字段  类型  描述  PathID  INTEGER  路径序号  SigTypeNum  INTEGER  信号类型  InstruName_S  VARCHAR  起点仪器名称

  PortType_S  CHAR  起点端口类型  PortID_S  INTEGER  起点端口序号  InstruName_E  VARCHAR  终点仪器名称  PortType_E  CHAR  终点端口类型  PortID_E  INTEGER  终点端口序号

表7路径节点坐标信息表

  字段  类型  描述  PathID  INTEGER  路径编号  Start_x  INTEGER  起点横坐标  Start_y  INTEGER  起点纵坐标  End_x  INTEGER  终点横坐标  End_y  INTEGER  终点纵坐标

表8布线失败路径信息表

  字段  类型  描述  IndexNum  INTEGER  编号  Start_x  INTEGER  起点横坐标  Start_y  INTEGER  起点纵坐标  End_x  INTEGER  终点横坐标  End_y  INTEGER  终点纵坐标

上面每个表中都列举了该表中包含的字段，并给出了各字段的数据类型以及表示的含义描述。表1仪器信息表的主键是InstruName字段，其他字段为对仪器信息属性的描述。表2信号类型表的主键是SigTypeNum字段，SigTypeName字段是对信号类型的中文名称。表3仪器的连接关系表的主键是ConnectPathID字段，表3中的SigTypeNum字段是对应与表2中的信号类型表的主键SigTypeNum的外键，表3中的其他字段是对一条信号通路所涉及的各类仪器信息属性的描述。表4仪器大小范围信息表的主键是InstruName字段，其他字段是对仪器模型绘制大小属性的描述。表5仪器包容矩形坐标表的复合主键是InstruName字段和SigTypeNum字段，其他字段是对仪器模型绘制坐标属性的描述。表6仪器连接路径表的复合主键是PathID字段和SigTypeNum字段，其他字段是对仪器连接路径起点和终点属性的描述。表7路径节点坐标信息表的主键是PathID字段，其他字段是对路径起点和终点坐标属性的属性。表8布线失败路径信息表的主键是IndexNum字段，其他字段是对布线失败路径的坐标属性的描述。

本发明提出的自动测试系统设计原理图的自动生成方法，如图2所示，包括：

步骤一、用户通过仪器设备资源与连接约束关系的输入模块输入数据。

用户通过仪器设备资源与连接约束关系的输入模块1输入数据，输入的数据包括：仪器信息、信号类型、仪器的连接关系、仪器绘制大小信息以及仪器包容矩形坐标信息。仪器设备与连接约束关系的输入模块1将输入的数据保存到数据库模块2中。其中，对于数据库模块2中存储的数据，用户通过数据库管理模块3进行添加，修改和删除等操作。

步骤二、用户根据绘制的需要选择信号类型，参数选择和预处理模块4根据选择的信号类型对仪器进行分组、定级。

参数选择和预处理模块4从数据库模块2中选取与所选择信号类型相关的仪器信息和仪器的连接关系，根据仪器所属的不同信号类型，对仪器进行分组，再按照仪器的不同功能，以仿真仪器、仿真调理仪器、开关仪器、验证调理仪器和验证仪器的顺序，对各组仪器进行定级，以确保图纸中信号走线连接的仪器的类型从左至右依次为仿真仪器、仿真调理仪器、开关仪器、验证调理仪器和验证仪器。最后参数选择和预处理模块4将分组、定级好的数据发送给自动布局模块5。

步骤三、自动布局模块进行相邻两级的仪器模型的自动布局操作，直到完成对各组仪器的布局操作。

自动布局模块5将分组、定级后的数据，根据基于最少线交叉的自动布局方法，对每组仪器按照级数由低到高的顺序，分别进行相邻两级的仪器模型的自动布局操作，直到完成对各组仪器的布局操作。最后自动布局模块5将布局结果输出给自动布线模块6。

步骤四、自动布线模块据布局结果，生成待布线网，完成布线操作并输出绘制结果。

自动布线模块6根据输入的布局结果生成待布线网，采用朝向目标的线探索布线方法，完成布线操作并输出绘制结果到绘制结果显示和保存模块7中。自动布线模块6在待布线网生成过程中，生成仪器连接路径和路径节点信息并存储到数据库模块2中。所述的绘制结果包括完成布线的仪器连接图以及布线失败路径信息。

步骤五、用户通过绘制结果显示和保存模块将绘制结果显示出来并保存。

用户通过绘制结果显示和保存模块7查看绘制结果，绘制结果显示和保存模块7将布线失败路径信息保存到数据库模块2中。

本发明的步骤三中所述的基于最少线交叉的自动布局方法，如图3所示，包括以下7个步骤：

第1步：初始化，具体包括下面四步。

步骤1.1：对于待布局的两级仪器，取其中仪器数目少的一级为级联关系矩阵的行仪器，另一级为列仪器。级联关系矩阵描述的是在当前仪器排列顺序下，各行、列仪器的连接关系，定义为：A＝(a_ij)_m×n，其中m为行仪器的数目，n为列仪器的数目，a_ij表示的是第i个行仪器和第j个列仪器之间的端口连接数目。

步骤1.2：根据行、列仪器的仪器信息和初始排列顺序，生成仪器展开维数矩阵P，得到行仪器展开维数矩阵P_r和列仪器展开维数矩阵P_c。仪器展开维数矩阵P保存的是在初始排列顺序下，行仪器或列仪器的端口数目，定义为：P＝(p_i)_1×k，其中k为行仪器数目m或者列仪器数目n，p_i为第i个行仪器或者列仪器的端口数目。仪器展开维数矩阵具体分为行仪器展开维数矩阵P_r和列仪器展开维数矩阵P_c。P_r用来描述各行仪器的展开维数，P_c用来描述各列仪器的展开维数。

步骤1.3：根据仪器端口连接关系、初始排列顺序、行仪器展开维数矩阵P_r和列仪器展开维数矩阵P_c生成初始级联关系矩阵A_d；

初始级联关系矩阵A_d描述的是在当前仪器排列顺序下，各互联端口的位置关系，定义为：A_d＝(a_ij)_m×n，其中m、n分别为待排序的两级仪器中行仪器的数目以及列仪器的数目，a_ij为二维不定长矩阵，描述的是第i个行仪器与第j个列仪器的端口连接关系。例如，若第i个行仪器的第k个端口与第j个列仪器的第l个端口之间存在连接，则将a_ij[k][l]设为1表示；否则，若无连接关系，a_ij[k][l]设置为0。

步骤1.4：定义m个行仪器的初始排列为1～N_r，n个列仪器的初始排列为1～N_c，这两个排列都为自然数索引的递增排列，其中N_r为第m个行仪器，N_c为第n个列仪器。行仪器的当前排列R_c是这m个自然数组成的序列的某一可能的排列情况，列仪器的当前排列C_c是这n个自然数组成的序列的某一可能的排列情况。

第2步：更新仪器行、列排放顺序；按照字典序法，生成一个新的行仪器的排列和新的列仪器的排列作为当前行仪器排列R_c和当前列仪器的排列C_c。字典序法是按照字典排序的思想，逐一产生一个序列所有的排列情况的一种排列生成方法，对于给定的字符集中的字符规定了一个先后关系，在此基础上规定两个全排列的先后顺序是通过从左到右逐个比较对应字符的先后顺序来决定的。

第3步：求解当前级联关系矩阵；

根据初始级联关系矩阵A_d，行仪器展开维数矩阵P_r，列仪器展开维数矩阵P_c，当前行仪器的排列R_c和当前列仪器的排列C_c，求解当前级联关系矩阵A_c。当前级联关系矩阵A_c是通过对初始级联关系矩阵A_d中的元素按照当前的行列仪器排列顺序，进行相对应的平移位置变换得到的。当前仪器行、列排列的第i个行仪器的第k个端口和第j个列仪器的第l个端口的连接关系对应为当前级联关系矩阵A_c中元素A_c[k][l]：

A_c[k][l]＝A_d[k-a₁+a₃][l-b₁+b₃]，a₁≤k≤a₂，b₁≤l≤b₂

其中是第i个行仪器对应于A_c中的起始行标，是第i个行仪器对应于A_c中的终止行标，R_c[x]表示当前行仪器排列中的第x个行仪器，P_r[R_c[x]]表示当前行仪器排列中的第x个行仪器的端口数目；是第j个列仪器对应于A_c中的起始列标，是第j个列仪器对应于A_c中的终止列标，C_c[x]表示当前列仪器排列中的第x个列仪器，P_c[C_c[x]]当前列仪器排列中的第x个列仪器的端口数目；是初始级联关系矩阵A_d中第i个行仪器与第j个列仪器端口连接的起始行标；是初始级联关系矩阵A_d中第i个行仪器与第j个列仪器端口连接的起始列标；k-a₁+a₃，l-b₁+b₃实现了对应元素从A_d到A_c的搬移。

第4步：计算线交叉数目；根据当前级联关系矩阵A_c，计算线交叉数目N。

$N=\underset{1\le i\le m}{\Sigma }\underset{0\le j\le n-1}{\Sigma }{a}_{\mathrm{ij}}·\left(\underset{1\le k<i}{\Sigma }\underset{j<l<n}{\Sigma }\right)a_{\text{kl}}$

其中，m为行仪器的数目，n为列仪器的数目，a_ij表示的是第i个行仪器和第j个列仪器之间的端口连接数目，a_kl表示的是第k个行仪器和第l个列仪器之间的端口连接数目。

第5步：更新记录；判断当前得到的线交叉数目是否为已有排列中线交叉数目的最小值，如果是，则记录当前的行、列排放顺序；如果不是，则不记录当前的行、列排放顺序。继续下一步。

第6步：判断是否进行了所有可能排列的线交叉计算；判断是否已对所有的可能存在的行、列排列情况进行了分析计算，如果是，则转第7步，否则转到第2步。

第7步：输出最少线交叉的排列；返回线交叉最少时的两级仪器的排列顺序，完成两级仪器的自动布局。

步骤四中所述的朝向目标的线探索布线方法是一种无网格布线方法，在探索的过程中，针对目标，采用合理的数据结构，可以缩小查找线段的范围，缩短布线时间，同时只需要存储过孔、焊盘、已布连线等数据，存贮量大大减少。

步骤四中待布线网生成是指根据已完成布局的各级仪器信息，分别读取待布线的两级仪器的信息，选择其中端口数目较大的一级仪器作为布线的起点，对于该级仪器的具体每一个仪器来说，按照其中心端口开始向两端扩散布线的原则确定仪器端口布线的顺序，生成仪器端口连接的路径信息，存放在仪器连接路径表中，再结合仪器包容矩形坐标表中保存的仪器的绘制坐标信息，计算出待布线的端口对的坐标信息，保存在路径节点坐标信息表中。点对布线是依次顺序完成路径节点坐标信息表中保存的端口段之间的布线，由起点坐标ptStart开始绘制到达终点坐标ptEnd的连线。在绘制连线之前首先需要完成打点的操作。对已存在相同起点或终点的连线，选择距离起点或终点位置最近的已布连线的折点作为新的布线起点。根据调整后的起点或终点，进行自动布线。

本发明的点对布线采用一种朝向目标的线探索自动布线方法，如图4所示，包括：

第1步：初始化参数设置及确定初始探索方向。

布线起点为ptStart，终点为ptEnd，方法入口将当前点ptCur置为起点即ptCur＝ptStart，所有引用变量赋初值，探索方向nD＝1，探索步进值nStep＝1，并对最小允许线间距离Delta赋值，Delta需要根据经验设定，本发明选取5-8之间的数值。确定首次探索的方向nD的初值，比较|ptCur.x-ptEnd.x|和|ptCur.y-ptEnd.y|的大小，其中ptEnd为终点，如果|ptCur.x-ptEnd.x|＞|ptCur.y-ptEnd.y|，则探索方向为水平方向nD＝0，将进行水平方向的探索，反之则为垂直方向nD＝1，进行垂直方向的探索。

第2步：试探点产生。

若为横向探索，则将试探点的横坐标赋值为探索终点的横坐标，试探点的纵坐标赋值为当前点的纵坐标，即ptTry.x＝ptEnd.x，ptTry.y＝ptCur.y，比较ptTry.x和ptCur.x，若ptTry.x＞ptCur.x则为水平向右探索，否则为水平向左探索；若为纵向探索，则将试探点的横坐标赋值为当前点的横坐标，试探点的纵坐标赋值为探索终点的纵坐标，即ptTry.x＝ptCur.x，ptTry.y＝ptEnd.y，比较ptTry.y和ptCur.y，若ptTry.y＞ptCur.y，则为垂直向下探索，否则为垂直向上探索。

第3步：试探点调整。

试探点的调整是对点ptTry进行初步的障碍检查，并对位置作相应的调整，主要检查该点是否处在已有线段或自己的前部分探索路径上，如果是，该点将被放弃，并同时以该点为中心左右步进Delta的整数倍，寻找新的试探点ptTry覆盖被放弃的试探点，具体的试探方法是：ptTemp＝ptTry；(ptTry＝ptTemp-nD＊(int)nStep＊nDelta；nD＊＝-1；nStep+＝0.5；)，反复执行括号内语句并最终找到合适的不处于任何一条已有线段上的点ptTry，其中ptTemp为中间量。

第4步：试探线避线障。

根据ptCur和ptTry的坐标产生探索线段Lt，将当前探索线段Lt与已有线段集合逐条比较，主要检查Lt是否与已有线段集合中的某条线段完全重合或部分重合，具体方法是从已绘制线段ptrArray集合类中的索引为零元素(直线段)开始，逐一提取已有直线段L，将直线度L与当前探索线段Lt进行比较，下面分为水平方向探索和垂直方向探索两种情况说明。

步骤4.1：水平探索的情况。

设已有直线段L两端点分别P1，P2，若P1.x＝P2.x；则L为垂直直线段，不予考虑，若P1.y＝P2.y，则L为水平直线段，需要与当前探索线段Lt进行位置分析，从而判断是否为其线障碍，首先根据二者的垂直坐标是否相等进行预判断，即若ptCur.y≠P1.y，直线段L与探索线段Lt将永远不会出现水平重合关系，可以提前排除该直线段，继续取下一条线段进行比较，相反，若ptCur.y＝P1.y，直线段L与探索线段Lt就有可能出现重合的机会，需要继续以下判断。判断是否当前点的横坐标小于直线段任一端点的横坐标，且该直线段端点的横坐标小于试探点的横坐标：ptCur.x＜P1.x(P2.x)＜＝ptTry.x？，条件成立时，直线段L是线障碍，反之被排除。直线段L为线障碍时，根据P1.x和P2.x的大小改变ptTry的位置从而避开线障碍得到新的试探点ptTry。

步骤4.1.1：水平向右探索情况。

若P1.x＜P2.x，则新的试探点ptTry.x＝P1.x-Delta，ptTry.y保持不变；反之则新的试探点ptTry.x＝P2.x-Delta，ptTry.y保持不变。同时需要对新的试探点ptTry进行类似试探点调整中的预检查，具体方法是：设置ptTry.x＝P1(P2).x-n＊Delta，如果当前的ptTry.x＜ptCur.x，那么代表向右探索失败，那么更新当前点ptCur.x＝ptCur.x-Delta，并转到步骤4.1.2；如果当前的ptTry.x＞＝ptCur.x，那么判断ptTry是否为线段Lt上的点，如果不是，那么ptTry即为合适的试探点，如果是则转到第3步，调整试探点。

步骤4.1.2：水平向左探索情况。

若P1.x＜P2.x，则新的试探点为：ptTry.x＝P1.x+Delta，ptTry.y保持不变；反之新的试探点为：ptTry.x＝P2.x+Delta，ptTry.y保持不变；同时需要对新的位置ptTry进行试探点调整中的预检查，具体方法是：设置ptTry.x＝P1(P2).x+n＊Delta，如果当前的ptTry.x＞ptCur.x，那么代表向左探索失败，那么更新当前点ptCur.x＝ptCur.x+Delta，并转到步骤4.1.1执行；如果当前的ptTry.x＜＝ptCur.x，那么判断当前ptTry是否为线段Lt上的点，如果不是，那么当前ptTry即为合适的试探点，如果是则转到第3步，调整试探点。

步骤4.2：垂直方向探索情况。

设已有直线段L两端点分别为P1、P2，若P1.y＝P2.y，则L为水平直线段，不予考虑，若P1.x＝P2.x，则L为垂直直线段，需要与当前探索线段Lt进行位置分析，从而判断是否为其线障碍，首先可以根据二者的水平坐标是否相等进行预判断，即若ptCur.x≠P1.x，直线段L与探索线段Lt将永远不会出现垂直重合关系，可以提前排除该直线段，继续取下一条线段进行比较，相反，若ptCur.x＝P1.x，直线段L与探索线段Lt就有可能出现重合的机会，需要继续以下判断。判断是否当前点的纵坐标小于直线段任一端点的纵坐标，且该直线段端点的纵坐标小于试探点的横坐标：ptCur.y＜P1.y(P2.y)＜＝ptTry.y？，条件成立时，直线段L是线障碍，反之直线段L被排除，取下一条已有线段进行比较；当直线段L为线障碍时，根据P1.y和P2.y的大小改变试探点ptTry的位置从而避开线障碍从而得到新的试探点ptTry。

步骤4.2.1：垂直向下探索情况。

若P1.y＜P2.y，则新的试探点为：ptTry.y＝P1.y-Delta，ptTry.x保持不变；反之新的试探点为：ptTry.y＝P2.y-Delta，ptTry.x保持不变。同时需要对新的试探点ptTry进行类似试探点调整中的预检查，具体方法是：设置ptTry.y＝P1(P2).y-n＊Delta，如果当前的ptTry.y＞ptCur.y，那么代表向下探索失败，更新当前点ptCur.y＝ptCur.y-Delta，并转到步骤4.2.2；如果当前的ptTry.y＜＝ptCur.y，那么判断ptTry是否为线段Lt上的点，如果不是，那么当前ptTry即为合适的试探点，如果是则转到第3步，调整试探点。

步骤4.2.2垂直向上探索情况。

若P1.y＜P2.y，则新的试探点为：ptTry.y＝P1.y+Delta，ptTry.x保持不变；反之新的试探点为：ptTry.y＝P2.y+Delta，ptTry.x保持不变。同时需要对新的试探点ptTry进行类似试探点调整中的预检查，具体方法：设置ptTry.y＝P1(P2).y+n＊Delta，如果当前的ptTry.y＜ptCur.y，那么代表向上探索失败，更新当前点ptCur.y＝ptCur.y+Delta，并转到步骤4.2.1；如果当前的ptTry.y＞＝ptCur.y，那么判断ptTry是否为线段Lt上的点，如果不是，那么当前ptTry即为合适的试探点，如果是则转到第3步，调整试探点。

第5步：试探线避物障。

这一步主要是检查探索线段上是否存在障碍盒，障碍盒是指已完成绘制仪器模型的包容矩形。具体检查方法与线障检查类似，从障碍盒集合的索引为零的元素(障碍矩形)开始，逐一提取每个障碍矩形R。设障碍矩形R左上角为ptTL，右下角为ptBR。

步骤5.1：水平方向探索的情况。

判断探索线段上是否存在该障碍盒，具体通过的判断方法是：如果ptCur.y＞＝ptBR.y&& ptCur.y＜＝ptTL.y同时成立，探索线段上有可能存在该障碍矩阵，反之如果不成立，可以排除此障碍矩阵，如果该障碍矩阵为障碍盒集合ptrObjectArray中最后一个，说明该探索线段试探成功，否则继续取下一个障碍矩阵进行判断。在条件成立时需要进行继续判断，分两种情况进行：水平向右探索和水平向左探索。

步骤5.1.1水平向右探索情况。

进一步判断条件ptTry.x＞＝ptTL.x && ptCur.x＜ptTL.x是否同时成立，如果不成立，也将被排除，如果该障碍矩形为障碍盒集合中最后一个，说明该探索线段试探成功，否则继续取下一个障碍矩形进行判断，条件成立时，此障碍矩形成为探索线段Lt的障碍，需要避障，具体避障方法是，依据障碍矩形R的位置调整ptTry的位置，设置ptTry.x＝ptTL.x-n＊Delta；如果当前的ptTry.x＜ptCur.x，那么代表向右探索失败，更新当前点ptCur.x＝ptCur.x-Delta，并转到步骤5.1.2；如果当前的ptTry.x＞＝ptCur.x，那么判断ptTry是否为线段Lt上的点，如果不是，那么当前点即为合适的试探点ptTry，如果是，转第3步调整试探点。

步骤5.1.2：水平向左探索情况。

判断条件ptTry.x＜＝ptBR.x && ptCur.x＞ptBR.x是否同时成立，如果不成立，则该障碍矩形将被排除，如果该障碍矩形为障碍盒集合中最后一个，说明该探索线段试探成功，否则继续取下一个障碍矩形进行判断，条件成立时，此障碍矩形成为Lt的障碍，需要避障，具体避障方法是，依据障碍矩形R的位置调整ptTry的位置，设置ptTry.x＝ptBR.x+n＊Delta；如果当前的ptTry.x＞ptCur.x，那么代表向左探索失败，更新当前点ptCur.x＝ptCur.x+Delta，并转到步骤5.1.1；如果当前的ptTry.x＜＝ptCur.x，那么判断ptTry是否为线段Lt上的点，如果不是，那么当前点即为合适的试探点ptTry，如果是，则转第3步调整试探点。

步骤5.2：垂直方向探索的情况。如果ptCur.x＞＝ptTL.x && ptCur.x＜＝ptBR.x同时成立，该障碍矩形有可能成为探索线段上的障碍盒，反之如果不成立，可以排除此障碍矩阵，如果该障碍矩阵为障碍盒集合中最后一个，说明该探索线段试探成功，否则继续取下一个障碍矩阵进行判断，条件成立时需要进行继续判断，分两种情况进行：垂直向下探索和垂直向上探索。

步骤5.2.1：垂直向下探索情况。

进一步判断条件ptTry.y＞＝ptBR.y && ptCur.y＜ptBR.y是否同时成立，如果不成立，该障碍矩形被排除，如果该障碍矩形为障碍盒集合中最后一个，说明该探索线段试探成功，否则继续取下一个障碍矩形进行判断，条件成立时，此障碍矩形成为探索线段Lt的障碍，需要避障，具体避障方法是，依据障碍矩形R的位置调整ptTry的位置：设置ptTry.y＝ptBR.y-n＊Delta，如果当前的ptTry.y＞ptCur.y，那么代表向下探索失败，更新当前点ptCur.y＝ptCur.y-Delta，并转到步骤5.2.2；如果当前的ptTry.y＜＝ptCur.y，那么判断当前ptTry是否为线段Lt上的点，如果不是，那么当前ptTry即为合适的试探点，如果是转第3步执行调整试探点。

步骤5.2.2：垂直向上探索情况。

进一步判断条件ptTry.y＜＝ptTL.y && ptCur.y＞ptTL.y是否同时成立，如果不成立，该障碍矩形被排除，如果该障碍矩形为障碍盒集合中最后一个，说明该探索线段试探成功，否则继续取下一个障碍矩形进行判断，条件成立时，此障碍矩形成为探索线段Lt的障碍，需要避障，具体避障方法是，依据障碍矩形R的位置调整ptTry的位置，设置ptTry.y＝ptTL.y+n＊Delta，如果当前的ptTry.y＜ptCur.y，那么代表向上探索失败，更新当前点ptCur.y＝ptCur.y+Delta，并转到步骤5.2.1；如果当前的ptTry.y＞＝ptCur.y，那么判断当前ptTry是否为线段Lt上的点，如果不是，那么当前ptTry即为合适的试探点，如果是则转第3步调整试探点。

第6步：判断是否达到终点。置ptCur＝ptTry，并判断条件ptCur＝ptEnd是否成立，条件成立，说明已经试探到了终点，布线成功，进入第8步，否则进入第7步。

第7步：保存已探索路径。保存当前试探成功的路径到探索路径集合中，转到第2步进行下一次探索。

第8步：绘制布线路径。依次绘制已探索成功的从布线起点到布线终点的各探索路径，完成由起点到终点的连线。