一种基于轮廓走线求解PCB平面图形布尔并外轮廓的方法

技术领域

本发明属于平面图形布尔运算技术领域，具体指一种基于轮廓走线求解 PCB平面图形布尔并外轮廓的方法。

背景技术

平面几何的布尔运算是计算几何中的基本问题，目前有许多针对多边形的布尔运算库。对平面图形的布尔运算主要包括两个步骤：1)求取多边形的交点以及交点相关的图形信息，2)通过逻辑规则求布尔运算结果。当面对求解大数量的平面几何问题时，存在计算量较大的情况，且运算库本身占用空间较多，这对于一些嵌入式设备来说难以接受。

PCB(Printed Circuit Board)设计是现代电路设计的重要一环，其中包括了大量的基础元器件。在PCB板的生产过程中，对裸板的检测是生产过程中的一个关键环节，对比是一种常见的检测方法。由于在设计时，元器件图形的数据储存是离散的，而实际应用中需要的是这些离散图形组成的外轮廓，因此需要一个对二维图形的布尔并算法来提取图形轮廓信息。同时在设计和检板操作时，外轮廓需要即时清晰的反应给设计者，这要求了算法的效率。

集成电路的组件构成和链接方式具有特殊性，因此采用一种基于轮廓走线的PCB特化算法能减少计算的复杂度，提高运行的效率。

发明内容

本发明根据现有技术的不足，提出一种基于轮廓走线求解PCB平面图形布尔并外轮廓的方法，能够优化传统的布尔并运算，提高求解平面几何图形关系的效率。

为了解决上述技术问题，本发明的技术方案为：

一种基于轮廓走线求解PCB平面图形布尔并外轮廓的方法，包括如下步骤：

S1、解析PCB资料，读取所有待处理的平面图形的基本信息，获得其相交情况；

S2、根据读取的信息，进一步计算各图形之间的相交点；

S3、对于不相交的每一组选取其非内部交点；

S4、根据轮廓走线法遍历记录平面图形的外轮廓

所述轮廓走线法为：通过外轮廓和相交点，在不同图形的边上进行跳转，最终回到起始点的轨迹。

作为优选，所述步骤S1中的平面图形的是由若干条线段或圆弧组成的封闭图形。

作为优选，所述平面图形的基本信息包括起点和终点的坐标，正负极性和每条边的方向。

作为优选，当平面图形中存在圆弧时，所述平面图形的基本信息还包括对于圆弧段存在的圆心坐标。

作为优选，所述步骤S1中的相交情况是指与当前边是否与其他图形的边相交，并无实际交点信息。

作为优选，所述步骤S2中的相交点为线段与圆弧的交点、线段与线段的交点，圆弧与圆弧的交点。

作为优选，所述步骤S2中，对于相交点共圆共线情况进行数字标记。

作为优选，所述步骤S3中的非内部交点是指不存在于集合内任意图形内部的交点。

作为优选，所述步骤S4包括如下子步骤：

S4-1、选取任意相交点为起始点，根据该相交点所在得线段或圆弧的方向，开始遍历轮廓，当遇到下一个相交点时，进入判断；

S4-2、根据相交点类型，进行不同平面图形之间的转移，当相交点为普通相交点时，行动准则为从原有平面图形进入相交边所在的平面图形，当相交点为相切点时，如果下一线段或圆弧存在共圆或共线情况，那么当前经数字标记的相交点不做跳转，反之则跳转到相交平面图形，根据上述方法，遍历所有相交点；

S4-3、结束轮廓遍历，判断当前的相交点是否等于初始点时，若为初始点，则遍历结束。

本发明具有以下的特点和有益效果：

在针对PCB组件的构成与连接方式的设计时，对其进行优化，简化数学计算的复杂度，提高了运算效率，运用走线法提取平面几何图形的外轮廓。

附图说明

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

图1位本发明实施例的基于轮廓走线求解PCB图形布尔并外轮廓的方法的步骤流程图。

图2为本发明实施例的基于轮廓走线求解PCB图形布尔并外轮廓的方法的 PCB内平面图形可视图。

图3为本发明实施例的基于轮廓走线求解PCB图形布尔并外轮廓的方法的相交组内信息示意图。

图4为本发明实施例的基于轮廓走线求解PCB图形布尔并外轮廓的方法的交点结果图。

图5为本发明实施例的基于轮廓走线求解PCB图形布尔并外轮廓的方法的算法理论结果图。

图6为本发明实施例的基于轮廓走线求解PCB图形布尔并外轮廓的方法的布尔并结果图。

具体实施方式

需要说明的是，在不冲突的情况下，本发明中的实施例及实施例中的特征可以相互组合。

在本发明的描述中，需要理解的是，术语“中心”、“纵向”、“横向”、“上”、“下”、“前”、“后”、“左”、“右”、“竖直”、“水平”、“顶”、“底”、“内”、“外”等指示的方位或位置关系为基于附图所示的方位或位置关系，仅是为了便于描述本发明和简化描述，而不是指示或暗示所指的装置或元件必须具有特定的方位、以特定的方位构造和操作，因此不能理解为对本发明的限制。此外，术语“第一”、“第二”等仅用于描述目的，而不能理解为指示或暗示相对重要性或者隐含指明所指示的技术特征的数量。由此，限定有“第一”、“第二”等的特征可以明示或者隐含地包括一个或者更多个该特征。在本发明的描述中，除非另有说明，“多个”的含义是两个或两个以上。

在本发明的描述中，需要说明的是，除非另有明确的规定和限定，术语“安装”、“相连”、“连接”应做广义理解，例如，可以是固定连接，也可以是可拆卸连接，或一体地连接；可以是机械连接，也可以是电连接；可以是直接相连，也可以通过中间媒介间接相连，可以是两个元件内部的连通。对于本领域的普通技术人员而言，可以通过具体情况理解上述术语在本发明中的具体含义。

本发明提供了一种基于轮廓走线求解PCB平面图形布尔并外轮廓的方法，如图1所示，包括如下步骤：

S1、解析PCB资料，读取所有待处理的平面图形的基本信息，获得其相交情况，其中，平面图形的是由若干条线段或圆弧组成的封闭图形，平面图形的基本信息包括起点和终点的坐标，正负极性和每条边的方向，相交情况是指当前边是否与其他图形的边相交，并无实际交点信息；

当平面图形中存在圆弧时，所述平面图形的基本信息还包括对于圆弧段存在的圆心坐标，

可以理解的，在PCB的设计中，平面图形不仅通过线段实现，在线路变向时，还可通过圆弧实现。

S2、根据读取的信息，进一步计算各图形之间的相交点，其中相交点为线段与圆弧的交点、线段与线段的交点，圆弧与圆弧的交点，对于相交点共圆共线情况进行数字标记；

S3、对于不相交的每一组选取其非内部交点，其中非内部交点是指不存在于集合内任意图形内部的交点；

S4、根据轮廓走线法遍历记录平面图形的外轮廓，

其中，轮廓走线法为：通过外轮廓和相交点，在不同图形的边上进行跳转，最终回到起始点的轨迹。

具体的，包括如下子步骤：

S4-1、选取任意相交点为起始点，根据该相交点所在得线段或圆弧的方向，开始遍历轮廓，当遇到下一个相交点时，进入判断；

S4-2、根据相交点类型，进行不同平面图形之间的转移，当相交点为普通相交点时，行动准则为从原有平面图形进入相交边所在的平面图形，当相交点为相切点时，如果下一线段或圆弧存在共圆或共线情况，那么当前经数字标记的相交点不做跳转，反之则跳转到相交平面图形，根据上述方法，遍历所有相交点；

S4-3、结束轮廓遍历，判断当前的相交点是否等于初始点时，若为初始点，则遍历结束。

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合上述技术方案及附图和实施例，对本发明进行进一步详细说明。

以图2为例，具体实施例包括以下步骤：

S1、解析PCB资料，读取所有待处理的平面图形基本信息，获得其相交情况。

具体的，对于每一个PCB平面图形，称之为Feature，它们由若干条线段或圆弧组成，每一条边称之为Segment，其可视化参见图3。图3中共有1个相交组，组内有4个Feature，每个Feature由4条Segment构成。对于每条Segment，读取其起始点坐标、圆心坐标、正负极性和方向。运用扫描线算法获得不同 Feature内Segment之间的相交情况。

S2、根据读取的基本信息获得相交情况，并求解各Feature之间的实际相交点并记录。

本实施例中实际存在交点共有8个。计算交点时先计算Segment所在的直线与圆的交点，再判断交点是否在对应的Segment上。线段与线段交点有 p1,p2,p5,p6。线段与圆弧的交点有p3,p4,p7,p8,皆为相切点。圆弧S3-2与S2-4共圆，S3-4与S4-2共圆，做标记。图4显示了例子中的所有的相交点。

S3、在相交组内选取一个非内部交点。随机挑取相交点p1，采用射线法判断可得p1在除自身Feature1，2以外所有Feature的外部。

S4、利用改进的轮廓走线算法，以S3求得的交点为起始点，求得PCB元器件的布尔并外轮廓轨迹。

具体的：

S4-1、以p1为起始点，根据Segment1-4方向，逆时针开始遍历轮廓，当遇到相交点时，进入判断。

S4-2、根据相交点类型，进行不同Feature之间的转移。当相交点为p1,p2,p5,p6等普通相交点时，行动准则为从原有Feature进入相交边所在的 Feature。当相交点为p3,p4,p7,p8等相切点时，如果下一Segment存在共圆或共线情况，那么当前相交点不做跳转，反之则跳转到相交Feature。根据上述方法，遍历在p1,p2,p3,p5,p6,p8时跳转。算法理论结果如图5所示

S4-3、结束轮廓遍历。判断当前的相交点是否等于初始点时，若为初始点，则遍历结束。记录遍历的轨迹为外轮廓。图6为布尔并轮廓可视图。

以上结合附图对本发明的实施方式作了详细说明，但本发明不限于所描述的实施方式。对于本领域的技术人员而言，在不脱离本发明原理和精神的情况下，对这些实施方式包括部件进行多种变化、修改、替换和变型，仍落入本发明的保护范围内。