面向PCB图元的通用几何凸包轮廓生成方法及设备与流程
本发明涉及印制电路板,具体涉及一种面向pcb图元的通用几何凸包轮廓生成方法及设备。
背景技术:
1、在pcb(印制电路板)绘图与几何处理场景中,常见需求包括:对铜皮/禁布区/开窗区域/丝印图形/机械层轮廓等由多图元叠加形成的复杂形状,生成一个外层轮廓,用于显示、裁剪、drc(设计规则检查)、区域运算、导出等。
2、现有技术通常采用以下路径来生成外层轮廓。
3、1.离散采样+凸包:对圆弧/椭圆弧进行高密度采样,再对所有点做凸包(如andrew(单调链)算法、graham(graham扫描)算法),但是,采样点数随精度激增,性能不稳定;并且仅得到点集凸包边界,难以还原轮廓中应保留的弧段信息。
4、2.基于包围盒的粗筛+精确相交:用图元aabb(轴对齐包围盒)做候选相交筛选,再做线段-弧/弧-弧求交,但是,当弧仅少量采样(如仅端点/少点)时,aabb候选筛选可能遗漏“中间穿越”的相交对象;同时,弧/椭圆弧带旋转时求交实现复杂,工程上易出现漏检、误判或数值不稳定。
5、3.多边形布尔运算/偏移库:将所有图元转换为多边形后做并集,再求外边界,但是,对弧/椭圆弧需离散近似;对大量图元开销大;对精度与鲁棒性要求高,且实现依赖重型几何库。
技术实现思路
1、本发明针对现有pcb绘图中生成外层轮廓时存在的问题,提供了一种面向pcb图元的通用几何凸包轮廓生成方法及设备,实现了复杂场景下外层轮廓的稳定提取,完整保留了弧段边界信息,提升了相交检测的完整性与处理效率,增强了算法数值鲁棒性,输出符合实际应用要求的高质量闭合外轮廓。
2、本发明通过下述技术方案实现。
3、第一方面,提供了一种面向pcb图元的通用几何凸包轮廓生成方法,所述方法包括:
4、将各类pcb图元拆解为线段集合与弧集合,并采集所述线段集合中各线段的两个端点以及所述弧集合中各弧对应的椭圆的长轴和短轴的四个端点,作为用于计算凸包的凸包点集;
5、以所述弧集合中的各弧所在的椭圆的各长轴中最长的长轴为基准,确定网格尺寸,并基于所述网格尺寸绘制网格单元;
6、针对所述弧集合中的各弧,将其包围盒覆盖的网格单元,注册到网格索引;
7、利用所述凸包点集,采用andrew算法,计算顺时针凸包点序列;
8、针对所述凸包点序列中的凸包相邻点对形成的各候选边,遍历所述各候选边经过的网格单元,检索与所述各候选边分别相交或相切的弧,并基于所述相交或相切的弧和所述各候选边,构建凸包轮廓。
9、在一些实施例中,所述方法还包括:对所述弧集合中的跨象限弧进行角度归一化,其中,采用下式进行所述角度归一化:
10、anglenorm = std::fmod(angle + 2π, 2π);
11、其中,anglenorm表示归一化角度;angle表示原始角度;std::fmod( )表示求余函数。
12、在一些实施例中,所述网格尺寸为:
13、cellsize = h a_max;
14、其中,cellsize表示网格尺寸;a_max表示所述弧集合中的各弧对应的椭圆的各长轴中最长的长轴;h表示系数,并且h>1。
15、在一些实施例中,针对所述弧集合中的各弧,将其包围盒覆盖的网格单元,注册到网格索引,包括:
16、针对所述弧集合中的每个弧,计算轴对齐包围盒aabb,将所述aabb覆盖的所有网格单元进行标记,并注册每个弧的网格索引。
17、在一些实施例中,利用所述凸包点集,采用andrew算法,计算顺时针凸包点序列,包括:
18、对所述凸包点集去重后,利用andrew单调链算法求凸包,以得到凸包点序列,其中,对共线点保留共线点,并将输出方向统一为顺时针。
19、在一些实施例中,针对所述凸包点序列中的凸包相邻点对形成的各候选边,遍历所述各候选边经过的网格单元,检索与所述各候选边分别相交或相切的弧,并基于所述相交或相切的弧,构建凸包轮廓,包括:
20、针对所述凸包点序列中的凸包相邻点对形成的各候选边,采用数字微分分析dda遍历所述各候选边经过的网格单元,汇总每个候选边在其路径上预期相交或相切的弧候选容器,并将各候选边的端点所属弧加入所述弧候选容器;
21、基于所述各候选边和对应的弧候选容器,利用所述各候选边的参数方程和对应的弧所在的标准椭圆方程,判断所述各候选边与对应的弧候选容器中的各弧对应的椭圆是否相交或相切;
22、基于相交或相切的结果,利用弧或直线段,构建凸包轮廓。
23、在一些实施例中,基于所述各候选边和对应的弧候选容器,利用所述各候选边的参数方程和对应的弧所在的标准椭圆方程,判断所述各候选边与对应的弧候选容器中的各弧对应的椭圆是否相交或相切,包括:
24、将所述各候选边的端点,通过平移和旋转,变换至对应的弧候选容器中的各弧对应的椭圆的本地坐标系;
25、将所述各候选边的参数方程,代入对应的弧候选容器中的各弧对应的标准椭圆方程,并进行求解,得到判别式:
26、;
27、其中,;表示候选边的两个端点;、为标准椭圆方程的系数;
28、在时,候选边与椭圆无交点;在时,候选边与椭圆相切,有一个交点;在时,候选边与椭圆相交,有两个交点,为正预设值。
29、在一些实施例中,基于相交或相切的结果,利用弧或直线段,构建凸包轮廓,包括:
30、在候选边与椭圆无交点或在候选边与椭圆相切的情况下,基于所述候选边,构建线段凸包轮廓;
31、在候选边与椭圆相交的情况下,将距所述候选边的起点最近的交点作为最近交点,基于所述最近交点与对应弧上的采集点之间的弧段构建弧段凸包轮廓,基于所述候选边的远离对应弧的一端的端点与所述最近交点之间的直线段构建线段凸包轮廓。
32、在一些实施例中,所述方法还包括:通过下式计算构建所述凸包轮廓的时间复杂度:
33、o(m + k);
34、其中,o( )表示复杂度函数;m表示凸包边数;k表示实际参与检测的候选弧数量;
35、当两个采集点的x坐标和y坐标的差值小于预设值的情况下,视为同一点,进行点合并;并且在计算顺时针凸包点序列的过程中,保留共线上的所有凸包点;
36、将所述凸包轮廓的最后一段连接到第一段起点;所述凸包轮廓的相邻弧段不强制合并。
37、第二方面,提供了一种面向pcb图元的通用几何凸包轮廓生成设备,所述设备包括:
38、至少一个处理器;
39、至少一个存储器,所述至少一个存储器被耦合到所述至少一个处理器并且存储用于由所述至少一个处理器执行的指令,所述指令在由所述至少一个处理器执行时实现以上任一项所述的方法。
40、本发明与现有技术相比,具有如下的优点和有益效果:
41、在本发明中,统一表达并处理线段、折线、多边形、矩形/旋转矩形及圆弧、椭圆弧等多类型图元,基于空间网格索引与dda遍历获取可靠候选并执行精确求交与弧度范围判断,从而在构建外轮廓时可直接保留圆弧/椭圆弧段输出,减少离散折线带来的误差与数据量;同时通过仅对实际穿越区域内候选弧段计算、配合网格尺度调节提升大规模处理效率与可扩展性,并借助角度归一化、eps阈值与相切/点等价处理增强数值鲁棒性,最终输出闭合、方向一致的轮廓边段序列,便于渲染及后续几何处理与工程检查应用。
版权声明:本站专利文献数据主要来源于国家知识产权局等公开渠道,由 技术新讯 进行整理汇编。页面设计及数据汇编的著作权归本站所有。全部内容仅供个人学习、科研评估与技术交流参考,严禁用于任何商业用途(包括但不限于直接生产制造、技术转让、倒卖数据等)。
免责条款:专利技术具有时效性,本站不对资料的绝对准确性、完整性和可实施性提供任何明示或暗示的担保。因参考本站内容造成的直接或间接损失,本站不承担相关法律责任。若您认为本站内容有侵权问题,请及时提供权属证明与我们联系,本站将在核实后依法处理。反馈意见:yyfuon@163.com