从碰撞检测到布局优化：异形嵌套排料算法核心解析

简介一款面向制造业排料与计算机辅助制造加工场景的异形嵌套排料算法源码包适合算法学习者、结构工程师与工艺规划人员参考。压缩包体积约5KB包含三个文件以网页文件作为交互主入口配在线代码运行配置与版本管理忽略文件便于快速启动和二次调试。内容覆盖经典启发式与元启发式两条路线从贪婪、动态规划到遗传、模拟退火、粒子群和蚁群算法并对最低水平线、旋转嵌套等几何策略做了直观演示。读者可结合算法选择指南理解不同排料方法在材料利用率、计算复杂度和加工约束上的权衡尤其能通过遗传算法可视化案例观察异形零件在有限板幅内的迭代收敛过程。压缩包结构精简适合作为理解排料算法原理、借鉴NX中异形排料验证思路或编写自定义排料脚本的入门素材。已有124人浏览学习适合需要快速建立排料算法整体认知的开发者。 干排料这行的朋友应该都有体会一群形状乱七八糟的零件往一块板材上摆怎么摆最省料这事儿看着像拼积木真做起来能让人掉不少头发。我最早接触这个需求是帮一个钣金加工厂做切割排版优化他们原来靠老师傅手动在CAD里排一个复杂订单能磨一整天材料利用率还不稳定。后来我调研了一圈决定自己写一套异形嵌套排料算法也就是题目说的这个事儿把“怎么把不规则零件尽可能紧凑地摆进板材”用代码实现了。这篇博文就围绕这个算法和代码聊聊我是怎么设计、怎么实现、以及实际运行中踩过的那些坑。这套算法解决的不只是“能摆下”的问题而是“摆得有多省”。同一种结果好的嵌套方案能省下百分之十几的材料对大批量生产的工厂来说这直接就是利润。所以这篇文章的核心不是贴一段能跑的代码就完事而是把背后的几何判定、布局策略、性能优化这些关键环节逐个拆开适合正在做排料需求、对计算几何感兴趣、或者被不规则零件套料问题折磨过的开发者和工程师参考。1. 先把问题说清楚异形嵌套到底在解决什么1.1 从“拼乐高”说起什么是异形嵌套我习惯把这个问题和“拼乐高积木往盒子里装”类比。常规矩形排料相当于所有积木都是方块只要一行行铺就行。异形嵌套就难在这个“异形”上——零件可能是不规则多边形可能带圆弧可能中间还有孔洞。嵌套的意思是要让这些不规则的形状互相咬合把空白区域压到最小。这个问题的专业叫法是“二维不规则排料问题”也叫Nesting Problem。它比矩形排料难在两点第一判定两个不规则零件是否重叠本身就是个计算几何问题第二在“不重叠”的前提下找到最优排列位置搜索空间大得吓人。这属于NP难问题意思是零件数量稍微多一点想用穷举方式找到理论最优解计算量会爆炸到完全不可接受。实际工作中异形嵌套最常见的应用场景有三类钣金切割激光切割、等离子切割、皮革/布料裁剪以及包装行业里的二维装箱。在这些场景里材料成本占比很高排料方案的优化空间直接对应真金白银。举个直观例子一块2000mm×1000mm的钢板上要切几十个形状各异的零件如果排料方案差可能切完这批料还剩大块废料但废料因为形状碎了一地根本没法再利用。好的嵌套算法就是把那些“犄角旮旯”的空间都塞满。1.2 先搞清楚目标省料、省时、省人工学术界研究排料问题喜欢盯着“材料利用率”这一个指标但工程上绝不只这一个目标。我做完第一版之后才意识到实际工厂关心的东西要复杂得多。首先是材料利用率也就是零件总面积占板材总面积的比例这当然是核心指标。但第二个指标是计算时间工厂不可能等一个算法跑几个小时才出方案。第三个是“可切割性”——排出来的方案切割头要走的路不能太离谱如果为了省料把零件摆得极分散切割头空走行程大增反而拖慢整机效率。再有一个容易被忽略的点某些零件有纹理方向要求比如布料的方向、木纹方向不能随意旋转。这就等于给算法加了约束。所以做排料算法前最先要做的事不是写代码而是把需求约束一条条列清楚——可旋转角度范围是多少、最小间距留多少切割缝宽、有没有固定位置优先级。这些约束直接影响后面的算法设计。我第一次做的时候没考虑切割缝宽结果排出的方案能看着完美拉到车间根本没法切零件间距为零一刀下去全连上了。2. 算法核心没有这两个模块排料无从谈起2.1 几何判定是不可绕开的地基排料算法的地基不是“怎么排”而是“怎么判断两个零件撞没撞上”。这个问题听上去简单用多边形来表示零件轮廓后变成“两个多边形是否相交”。如果零件允许旋转还要在任意角度下都能快速判断。我最初用的方案是分离轴定理SATSeparating Axis Theorem。它的原理听着也不难两个凸多边形不相交当且仅当存在一条轴使得两个多边形在这条轴上的投影互不重叠。这条轴只需要取每个多边形的每条边的法线方向。找到这样一条轴就能判定不相交提前退出。但SAT有个硬伤它只适用于凸多边形。实际零件基本都是凹多边形。处理凹多边形可以用凹多边形分解把一个凹多边形切成多个凸多边形然后每个凸小块两两做SAT。这个方法在零件形状比较规整时效率还不错但遇到特别复杂的轮廓切割出来的凸小块数量很多计算量直线上升。另一个常用方案是NFPNo-Fit Polygon临界多边形这是排料算法领域更“正宗”的技术路线。它的思路是固定参考多边形A让多边形B绕着A走一圈记录B上某个参考点的轨迹这个轨迹围成的区域就是B不能进入的禁区。有了NFP判断两个零件有没有重叠只需要看点在不在这块禁区内就行了。它的优势是位置搜索阶段可以大幅度简化——先判断候选位置是否落在禁区里省掉大量逐点测试。代价是NFP本身的计算比较复杂尤其是两个凹多边形求NFP代码量不小容易出现数值边界问题。我自己在工程里实际采用的是“混合策略”预计算阶段把所有凹多边形用耳切法分解成凸小块实时判定时先用包围盒AABB粗筛再用SAT对分解后的凸小块做精确检测。这套方案在很多论文里也被验证是工程上兼顾效率和代码复杂度的选择。2.2 布局策略贪心搜索与元启发式有了几何判定下一个核心问题就是零件的摆放位置怎么选。这也是最终排料效果差异最大的环节。业界和学术界最常用的基础策略是BL算法Bottom-Left思路简单粗暴把待排零件按某种顺序一个一个放到板材左下角然后在不重叠的前提下尽量往下、往左移动直到动不了为止。这个算法很直觉也很容易写我第一版就是用它跑通的。但它的效果强依赖零件放入顺序顺序差时利用率会很惨。解决顺序依赖的办法有两个方向。一是排序启发式按面积从大到小、按宽度从大到小、按周长复杂度排序等先排大件、后排小件让大件占好位置小件见缝插针。实测下来按面积降序是最稳的基线方案复杂程度明显好过随机顺序。二是元启发式优化把初始布局作为起点用模拟退火或遗传算法去迭代修改顺序和旋转角度接受更优的方案。模拟退火的思路很像炼钢时“退火”的过程温度高的时候允许接受差解避免陷入局部最优温度慢慢降低逐步收敛到好解。我在第二版里加入了模拟退火做局部优化目标函数就是材料利用率加一个“排列紧凑度”的惩罚项。实测下来优化后平均还能再提高3~6个百分点的利用率。不过要提醒的是元启发式是把双刃剑计算时间成倍增加。工程上一般有两种模式快速模式只用贪心排序和精细模式贪心模拟退火让用户按订单紧急程度自己选。3. 代码架构这套排料算法是怎么一点一点搭起来的3.1 数据结构和整体流程排料算法的代码不能一股脑塞在几个函数里我建议至少分成四个模块几何内核处理多边形数据、碰撞检测、布局引擎决定摆放位置和顺序、优化器跑模拟退火等搜索策略、可视化模块方便调试和输出方案预览。在Python里我会用numpy存多边形的顶点坐标用shapely这样的库做一部分辅助几何运算但核心碰撞检测还是自己实现因为引第三方库会有一些额外开销尤其是批量计算时自己写精简版反而更快、更容易控制精度。一个典型排料请求的数据格式大概长这样parts [ {id: 1, polygon: [(0, 0), (10, 0), (10, 3), (5, 6), (0, 3)], angle_step: 90}, {id: 2, polygon: [(0, 0), (8, 0), (8, 4), (2, 4), (0, 8)], angle_step: 45}, # ... ] sheet {width: 2000.0, height: 1000.0} kerf 1.5 # 切割缝宽其中angle_step表示这个零件允许旋转的角度步长90就是只能转四个方向45是每45度一个方向0表示不旋转。板材尺寸和切割缝宽是全局参数。整体流程是一个循环取零件 - 生成候选位置 - 碰撞检测 - 选最优位置 - 固定位置 - 下一个零件。候选位置的生成不是凭空来的实战中我用的方法是“贴靠法”新零件的候选位置来自已放零件的轮廓点和角落点在这些位置逐个测试是否重叠再按BL法则筛选出最优的那个。这样能很快收敛到紧凑的布局。3.2 碰撞检测核心代码从包围盒到精确判定这里给一段简化但可运行的碰撞检测核心代码大家可以直接抄作业改造import numpy as np def convex_polygons(poly): 将多边形分解为凸多边形列表此处示意简化 # 实际可用耳切法返回凸多边形顶点列表 return [poly] def aabb(poly): arr np.array(poly) return (arr[:, 0].min(), arr[:, 1].min(), arr[:, 0].max(), arr[:, 1].max()) def aabb_overlap(a, b): return not (a[2] b[0] or b[2] a[0] or a[3] b[1] or b[3] a[1]) def polygons_overlap(poly_a, poly_b): # 第一步AABB快速排斥 if not aabb_overlap(aabb(poly_a), aabb(poly_b)): return False # 第二步凸分解后逐个SAT检测 for ca in convex_polygons(poly_a): for cb in convex_polygons(poly_b): if sat_overlap(ca, cb): return True return False def sat_overlap(convex_a, convex_b): 分离轴定理判定两个凸多边形是否相交 axes get_axes(convex_a) get_axes(convex_b) for axis in axes: proj_a project(convex_a, axis) proj_b project(convex_b, axis) if proj_a[1] proj_b[0] or proj_b[1] proj_a[0]: return False # 找到一条分离轴一定不相交 return True # 所有轴都重叠发生碰撞 def get_axes(poly): axes [] n len(poly) for i in range(n): p1 np.array(poly[i]) p2 np.array(poly[(i 1) % n]) edge p2 - p1 axes.append(np.array([-edge[1], edge[0]])) # 法线 return axes def project(poly, axis): dots [np.dot(np.array(p), axis) for p in poly] return (min(dots), max(dots))这段代码的逻辑分两层先用AABB判断“可能重叠吗”只有可能重叠才走精确判定。这样做性能收益很大因为大部分候选位置和已放零件在包围盒阶段就被排除了精测的计算量被砍掉一大部分。sat_overlap里只要找到一个分离轴就返回False不用把所有轴全部算完这也是常规优化手段。3.3 BL布局实现最简单的套路但很关键下面是BL布局的核心思路我用的是按面积降序排列后逐一填入的方式def bottom_left_place(parts, sheet_width, sheet_height): placed [] parts.sort(keylambda p: polygon_area(p[polygon]), reverseTrue) for part in parts: best_pos None best_cost float(inf) candidates generate_candidates(part, placed, sheet_width, sheet_height) for pos in candidates: if pos[0] 0 or pos[1] 0: continue if pos[0] part_width(part) sheet_width: continue if pos[1] part_height(part) sheet_height: continue if not any(polygons_overlap(translate(part[polygon], pos), p[polygon]) for p in placed): # cost函数x越小越靠左、y越小越靠下符合BL偏好 cost pos[0] * 1.0 pos[1] * 1.2 if cost best_cost: best_cost cost best_pos pos if best_pos is None: print(f零件 {part[id]} 在剩余空间内放不下) continue placed.append({id: part[id], polygon: translate(part[polygon], best_pos), pos: best_pos}) return placed这段代码里有个细节值得展开cost函数里x的权重和y的权重不同我让y的权重稍微大一点1.2意思是优先让零件往下靠。为什么因为左下角优先的直觉是“先向下再向左”但在实际程序里如果从搜索的候选点集合本身已经足够密集用加权cost来平衡上下左右往往比严格的“先下后左”更容易找到好位置。当然这个权重不能拍脑袋要根据板材比例和零件形状微调。generate_candidates这个函数是BL算法里决定上限的地方。最简单的实现是从左下角开始以某个步长网格扫描整块板材但这样既慢又不准。我采用的候选点来源有两个已放置零件的右上角点和右下角点以及已放置零件边界的延伸点。通俗讲就是把新零件“贴”在已放零件的边缘试位这样排出来的布局天然紧密不需要大范围扫描。4. 工程优化跑得动才是硬道理4.1 性能瓶颈与BVH加速算法写出来能跑是一回事跑得快是另一回事。我第一版在零件数量到100个以上时每一次摆放都要和之前所有已放零件做碰撞检测候选位置又多整体耗时按指数往上走。后来我做了**BVH包围体层次结构**加速。这个优化的核心思想和快递分拣很像把空间划分成区域每个区域建立一层包围盒索引。要判断新零件跟谁碰撞先查它在哪个区域只跟该区域附近的零件做精确判定其他区域直接跳过。我用的是AABB级别的BVH也就是先把每个已放零件的包围盒放进树结构里新增零件时从根节点往下遍历剪掉不可能重叠的分支。做了BVH优化之后100个零件的排料计算从几分钟降到了几秒这个差距在交互式调整参数的场景里是决定性的。说实话没做优化前我根本不敢把参数面板里的“板材尺寸”滑块拖来拖去因为拖一次要等半天。4.2 参数调优与数值稳定性排料算法里有一个很微妙但非常关键的参数——间距kerf。切割缝宽必须考虑进去否则排出的方案没法加工。在代码里我处理切割缝宽的方法不是把多边形膨胀因为膨胀复杂形状很容易出错而是把所有零件先“缩小”到间距的一半去做排料排完之后在切割路径上再补偿回来。这个思路虽然有点绕但实际效果很稳不容易出几何异常。数值稳定性也是一个容易翻车的地方。我遇到过两个比较经典的bug一是SAT投影计算时浮点误差导致两个刚好贴在一起的零件被判成重叠。解决办法是给重叠判断加一个极小容差epsilon 1e-6换句话说允许微小的数值误差存在。二是凸多边形分解时如果多边形顶点有重复点耳切法会死循环。这个是在预处理阶段加一步“顶点去重”顺手把面积接近零的退化多边形过滤掉。优化参数速查表参数建议值说明SAT epsilon1e-6碰撞判定容差过小容易误判过大会漏判切割缝宽补偿kerf / 2排料时零件缩小半个缝宽避免干涉模拟退火初温1000越高越容易跳出局部最优但耗时越长退火降温系数0.98控制收敛速度一般取0.95~0.995候选点数量上限500防止候选点过多导致单步计算过慢角度旋转步长45或90越小搜索空间越大但料率可能更好5. 常见问题与排查实录5.1 现象、原因与解法速查很多人在实现排料算法时遇到的问题其实都差不多我把最常碰到的几个写出来遇到类似情况可以直接照方抓药。问题一零件明明有空间放程序却说放不下。这个大概率出在候选点生成上——只在已放零件的边上生成候选点漏掉了板材左下角的空余区域。解决办法是候选点集合里始终加入板材原点附近的一个扫描点集尤其是在刚开始排料、已放零件很少的时候。问题二排出的方案里两个零件之间的间距小于设定值。这是容差和缝宽处理没生效。检查一下是不是把kerf直接加在零件多边形上而不是用“先缩小后排料再补偿”的方案。直接膨胀多边形很容易导致顶点大量交叉碰撞判断结果就乱了。**问题三模拟退火过程中方案越优化时间越跑越长。**这个正常现象因为迭代中每次都要重新评估整个布局。我的优化技巧是只对局部变化的区域做增量碰撞检测而不是每次全量重算。具体做法是把整个布局分为网格区域只对受影响网格的零件重新检测。问题四某几个零件旋转时碰撞检测结果与肉眼判断不一致。九成原因是凹多边形没有正确分解成凸多边形SAT结果失真。排查方法很简单把所有零件输入可视化调试工具把凸分解结果画出来看看分解得到的凸小块有没有重叠或漏区。问题五板材利用率计算出来比实际高很多工厂反馈对不上。这个往往是因为零件之间的“可见间隙”没有被准确统计。我后来把所有零件间距小于0.3mm的间隙也纳入“不可用面积”再和工厂实测数据对比误差就控制到百分之一以内了。5.2 三个值得说道的实操心得写这个算法的过程中有几个“吃一堑长一智”的经历单拎出来分享一下。**心得一可视化调试工具一定要提前做不要拖到后期。**我第一版写完碰撞检测后直接开始调BL布局结果连续几天都被BUG折磨得头皮发麻。后来痛定思痛花了一天时间写了个简单的matplotlib可视化脚本把每个零件、包围盒、候选点、碰撞判定结果都画出来很多问题一眼就能定位。做算法开发看不见中间过程等于盲人摸象。**心得二不要迷信论文里的最优参数自己的数据才是标准。**很多论文会给出模拟退火最佳初温、最佳降温系数但这些值跟零件数量、形状复杂程度、板材比例强相关。我的做法是先跑一组小样本参数扫描选一个在可接受时间内的最优组合再根据实际生产数据微调。脱离具体数据谈参数都是耍流氓。**心得三尽量保留一个“人工微调”的输出接口。**这个想法来自实际工厂场景算法算出的最优方案可能因为某个零件有表面划痕需要避开等原因需要人工调位。我在输出环节加了一个简单的JSON方案导出包含零件位置、旋转角度、所属板材编号车间师傅拿到后可以在不看代码的情况下做局部微调然后在设备端重新生成切割文件。这个接口看起来不起眼却让整个系统的落地顺畅了很多。6. 扩展思路下一步可以往哪些方向走6.1 从二维到“2.5维”带排料间隙的切割路径联动很多读者可能以为排料只到“怎么摆”就结束了但实际车间里排料之后紧接着是切割路径规划。切割头从一个零件切到下一个零件时路径的跳转距离如果过长会显著增加切割时间。目前我在做的一个扩展是排料输出时同时输出一个“切割顺序建议”让相邻切割的零件在位置上尽量接近减少空走行程。这一步优化在生产节拍紧张的车间里效果很明显同等排料利用率下整机切割时间能缩短8%左右。6.2 机器学习辅助用历史排料方案做初始化纯启发式优化的问题在于每个订单都要从零开始搜即使两天前的订单和今天的非常相似。我现在在尝试的做法是把历史已确认的排料方案作为训练数据用一个简单的监督学习模型学习“什么样的零件组合容易被嵌套在一起”然后在新订单进来时先基于历史知识生成初版布局再用模拟退火精修。初步实验中这种”热启动“方式把普通订单的优化迭代时间压缩了接近一半而且材料利用率还有小幅提升。6.3 真三维嵌套未来可能的方向二维异形嵌套成熟之后我身边有不少做增材制造3D打印的朋友开始问能不能做三维嵌套。三维的情况复杂得多——不光要判断两个三维网格是否相交还要处理支撑结构、打印方向、悬垂角度等约束。目前工业界还没有特别成熟的通用三维嵌套商用方案更多还是停留在半自动或者人工辅助。如果你有这方面的项目背景这倒是个很有意思的蓝海方向但短期内做工程落地我还是建议先把二维方案做到极致。本文还有配套的精品资源点击获取