1. 项目概述从“乱放”到“最优排布”的工程实践二维矩形排样听起来是个学术名词但它的核心问题我们生活中随处可见。想象一下你是一个家具厂的切割工面对一堆大小不一的矩形木板原料大板如何切割才能浪费最少或者你是一个物流仓库的管理员如何把一批尺寸各异的货箱尽可能紧密地装进一个标准集装箱里再或者你是一个PCB印刷电路板的工程师如何在有限的板子上排列出最多的芯片以降低成本这些问题的本质都是二维矩形排样。在数学建模和工业工程领域这被称为“二维矩形排样问题”或“二维下料问题”。它的目标非常明确在给定的一个或多个大矩形板材容器内放置一系列已知尺寸的小矩形物品使得所有物品都能被容纳并且通常追求某个指标的最优化——最常见的就是“材料利用率”最高即所有小矩形总面积占所用大矩形总面积的比例最大从而让废料最少。手动去排当物品数量超过十个人脑基本就难以找到最优解了。这时候就需要算法和代码来帮忙。MATLAB作为科学计算和算法原型的利器因其强大的矩阵运算能力和丰富的可视化工具成为实现这类组合优化算法的绝佳平台。我这次要分享的就是一套用MATLAB从零开始实现的二维矩形排样代码。这不是一个简单的“玩具”代码而是融入了实际工程中常用的启发式策略能够处理数十甚至上百个矩形件的排样并给出可视化的排样图让你直观地看到算法是如何“思考”和“摆放”的。这套代码适合谁呢如果你是数学建模的参赛队员正在备战国赛、美赛或亚太杯其中常有涉及资源优化、物流调度的问题排样算法是一个强有力的模型工具。如果你是机械、材料、电子相关专业的学生或工程师需要解决实际的下料、布局问题这套代码可以作为一个可靠的起点。即使你只是对优化算法感兴趣想看看代码如何解决这样一个经典的NP-Hard难题这里也有清晰的思路和实现细节等你探索。2. 核心算法思路如何教会计算机“摆放”二维矩形排样问题在计算复杂性上属于NP-Hard问题这意味着随着矩形数量的增加找到绝对最优解所需的时间会呈指数级增长。因此我们退而求其次追求在合理时间内找到一个“足够好”的、高利用率的可行解。业界和学术界提出了多种启发式算法其中“最低水平线算法”及其变种因其简单、高效且效果不错成为了最常用的方法之一。我们代码的核心就基于此。2.1 算法骨架最低水平线算法Bottom-Left Fill这个算法的思想非常直观模拟了一个人从容器左下角开始尽可能向左、向下放置物品的过程。你可以把它想象成往一个箱子里放书总是先把书推到箱子的最左边和最底下。算法的核心流程如下初始化将容器大矩形的顶部轮廓线初始化为一条从容器左下角到右下角的水平线其高度为0。我们用一个列表来记录当前轮廓线它由一系列x坐标 高度的点构成。矩形排序将所有待排放的矩形按照某种规则排序如高度递减、面积递减、周长递减等。排序策略直接影响最终效果通常优先放置大的、难以安排的矩形。迭代放置 a. 从排序好的矩形列表中取出下一个矩形。 b. 在当前轮廓线上从左到右扫描寻找一个可以放置该矩形的位置。这个位置需要满足两个条件第一矩形放置后其右边界不超过容器宽度第二矩形放置的底部即轮廓线在该段的最高点加上矩形高度不超过容器高度。 c. 在所有可放置的位置中选择一个使得矩形放置后其顶部轮廓线最低的位置。这就是“最低水平线”的含义——总是把新矩形放在当前“坑”最深的地方以保持整体轮廓的平整为后续矩形留出空间。 d. 放置矩形并更新容器的顶部轮廓线。放置后原来平坦的轮廓线会被抬升形成新的、更复杂的轮廓。循环重复步骤3直到所有矩形放置完毕或无法再放置任何矩形。这个算法的优势在于它只维护一条动态变化的轮廓线计算复杂度相对较低。但它也有缺点比如可能产生“碎片”——即一些太小而无法利用的零散空间。2.2 我们的增强策略多规则排序与放置点选择在基础的最低水平线算法上我结合实践做了几点关键增强这也是代码实用性的核心。首先是矩形的排序规则。单一规则往往有局限性。我的代码实现了多种排序规则并允许在运行时指定或组合尝试按高度降序优先放置高的矩形可以有效减少在垂直方向上产生的“峡谷”是效果最稳定、最常用的规则之一。按面积降序优先放置大矩形直观上有利于先解决“难题”。按宽度降序有时对宽容器有效。综合评分例如(高度 宽度) / 2的降序作为一种折中策略。 在实际运行时我常常会尝试2-3种不同的排序规则然后选择材料利用率最高的那个结果。代码中可以通过一个循环轻松实现这一点。其次是放置点的选择策略。基础算法只选择“最低水平线”的位置。但有时“最低”的位置可能不是“最好”的。例如有两个高度相同的“坑”一个很宽一个很窄。把矩形放在宽坑里可能会浪费旁边的空间放在窄坑里可能更贴合。因此我在代码中加入了一个可选的“最佳匹配”评估。在找到所有可行的最低水平线位置后不是简单地选择第一个而是计算每个位置放置后新矩形与相邻轮廓线形成的“空洞”大小即浪费的潜在空间选择空洞最小的那个位置。这个策略稍微增加了计算量但有时能提升1%-3%的利用率对于工业场景这意味著可观的成本节约。注意排序规则是影响排样结果的最关键因素没有之一。不同的规则会导致利用率差异巨大。对于一批特定的矩形数据没有永远最好的规则。因此在实际应用中将多种排序规则作为“候选策略”并行运行最后取最优解是一个非常重要的工程实践。3. 代码结构与关键模块解析下面我们来拆解MATLAB代码的核心模块。整个项目主要包含以下几个函数文件main.m主脚本负责读取数据、设置参数、调用算法并可视化结果。load_rectangles.m数据加载函数可以从文本文件或Excel表格中读取矩形尺寸。sort_rectangles.m矩形排序函数根据指定规则对矩形列表进行排序。bottom_left_fill.m核心算法函数实现增强版的最低水平线排样。plot_packing.m可视化函数绘制最终的排样图。3.1 数据输入与预处理 (load_rectangles.m)数据格式通常是一个 Nx2 的矩阵每一行代表一个矩形第一列是宽度w第二列是高度h。容器尺寸plate_width,plate_height作为参数输入。function rect_list load_rectangles(filename) % 从文件加载矩形尺寸 % 假设文件是纯文本每行是 宽度 高度 data load(filename); rect_list data; % 或者根据格式进行解析 end在实际项目中数据可能来自CAD图纸或生产订单系统。这个函数需要根据实际数据源格式进行定制比如处理Excel的xlsread或readtable。3.2 核心算法实现 (bottom_left_fill.m)这是代码的“心脏”。我详细解释一下其内部数据结构与关键步骤。数据结构设计rectangles: 排序后的矩形列表每个矩形是[id, w, h]id用于追踪。plate_width,plate_height: 容器宽高。skyline: 轮廓线。我使用一个Mx2的数组表示skyline(:,1)是x坐标分段起点skyline(:,2)是该段的高度。初始状态为[0, 0; plate_width, 0]。placed_rects: 记录已放置矩形的位置信息每个元素是[id, x, y, w, h]。关键步骤伪代码与MATLAB实现思路function [placed_rects, utilization] bottom_left_fill(rectangles, plate_width, plate_height, sort_rule) % 初始化 skyline [0, 0; plate_width, 0]; placed_rects []; for i 1:size(rectangles, 1) rect rectangles(i, :); % [id, w, h] best_x -1; best_y -1; best_fit_score inf; % 用于最佳匹配评估 % 步骤1: 扫描轮廓线寻找候选位置 for s 1:size(skyline, 1)-1 seg_start_x skyline(s, 1); seg_end_x skyline(s1, 1); seg_height skyline(s, 2); % 候选放置的x坐标就是当前线段的起点 cand_x seg_start_x; % 放置后的y坐标就是当前线段的高度 cand_y seg_height; % 检查放置是否可行右边界和上边界不超出容器 if cand_x rect(2) plate_width cand_y rect(3) plate_height % 检查在 [cand_x, cand_xw] 区间内底部是否平整即所有轮廓线高度都 cand_y % 这是一个关键检查防止矩形悬空 if check_fit(skyline, cand_x, rect(2), cand_y) % 计算匹配分数例如放置后顶部轮廓线的平整度或空间浪费 fit_score evaluate_fit(skyline, cand_x, rect(2), cand_y, seg_height); if fit_score best_fit_score best_fit_score fit_score; best_x cand_x; best_y cand_y; end end end end % 步骤2: 如果找到位置放置矩形并更新轮廓线 if best_x 0 % 记录放置信息 placed_rects [placed_rects; rect(1), best_x, best_y, rect(2), rect(3)]; % 更新轮廓线 skyline skyline update_skyline(skyline, best_x, rect(2), best_y rect(3)); else % 如果没找到位置可以跳过此矩形记录为未放置 warning(矩形 ID %d (%.1fx%.1f) 无法放置。, rect(1), rect(2), rect(3)); end end % 计算材料利用率 total_area sum(placed_rects(:,4) .* placed_rects(:,5)); plate_area plate_width * plate_height; utilization total_area / plate_area; endcheck_fit和update_skyline是两个需要精心实现的子函数。check_fit: 需要遍历skyline判断在区间[cand_x, cand_xw]内所有轮廓线的高度是否都不大于cand_y。如果不是说明矩形底部有“凸起”无法平稳放置。update_skyline: 这是算法中最繁琐的部分。在位置(best_x, best_yh)插入一条新的水平线段。这需要处理多种情况新线段可能与原有线段重叠、相交、分割原有线段。正确的更新是保证算法后续迭代正确的基石。通常的做法是先将新线段的起点和终点插入轮廓线点序列然后重新计算整个轮廓线的高度取每个x点上所有线段高度的最大值。实操心得update_skyline函数的实现很容易出BUG。一个有效的调试方法是在每次更新轮廓线后立即用plot函数将其绘制出来与矩形放置图叠加肉眼观察轮廓线变化是否符合预期。MATLAB的即时可视化能力在这里是巨大的优势。3.3 可视化输出 (plot_packing.m)“一图胜千言”尤其是对于布局问题。可视化模块不仅用于展示最终结果更是调试和验证算法的重要工具。function plot_packing(placed_rects, plate_width, plate_height, utilization) figure(Position, [100, 100, 800, 600]); hold on; % 绘制容器边框 rectangle(Position, [0, 0, plate_width, plate_height], EdgeColor, k, LineWidth, 2); % 绘制每个矩形 colors lines(size(placed_rects, 1)); % 使用不同的颜色 for i 1:size(placed_rects, 1) rect placed_rects(i, :); id rect(1); x rect(2); y rect(3); w rect(4); h rect(5); % 绘制矩形填充 rectangle(Position, [x, y, w, h], FaceColor, colors(i, :), EdgeColor, k, LineWidth, 1); % 在矩形中心添加文本标签ID和尺寸 text(x w/2, y h/2, sprintf(%d\n%.0fx%.0f, id, w, h), ... HorizontalAlignment, center, VerticalAlignment, middle, ... FontSize, 8, Color, white); end hold off; axis equal; xlim([-1, plate_width1]); ylim([-1, plate_height1]); grid on; title(sprintf(二维矩形排样结果 - 材料利用率: %.2f%%, utilization*100)); xlabel(宽度); ylabel(高度); end这个绘图函数会生成一个带网格的图每个矩形用不同颜色填充并标注其ID和尺寸。材料利用率会显示在标题中。通过观察图形你可以直观判断算法是否紧凑是否存在明显的空间浪费。4. 完整工作流与参数调优实战有了以上模块我们就可以串联起一个完整的工作流。在main.m脚本中流程如下%% 1. 参数设置 plate_width 100; % 容器宽度 plate_height 50; % 容器高度 data_file rect_data.txt; % 矩形数据文件 sort_rules {height, area, width}; % 要尝试的排序规则列表 %% 2. 加载数据 rect_list_raw load_rectangles(data_file); % 为每个矩形添加ID rect_list_raw [(1:size(rect_list_raw,1)), rect_list_raw]; best_utilization 0; best_placed_rects []; best_rule ; %% 3. 多规则尝试 for i 1:length(sort_rules) rule sort_rules{i}; fprintf(尝试排序规则: %s\n, rule); % 排序 sorted_rects sort_rectangles(rect_list_raw, rule); % 执行排样算法 [placed_rects, utilization] bottom_left_fill(sorted_rects, plate_width, plate_height, rule); fprintf( 材料利用率: %.2f%%\n, utilization*100); % 记录最佳结果 if utilization best_utilization best_utilization utilization; best_placed_rects placed_rects; best_rule rule; end end %% 4. 输出与可视化最佳结果 fprintf(\n最佳排序规则: %s\n, best_rule); fprintf(最高材料利用率: %.2f%%\n, best_utilization*100); plot_packing(best_placed_rects, plate_width, plate_height, best_utilization); %% 5. (可选) 输出排样坐标文件用于生产 output_file packing_result.csv; writematrix(best_placed_rects, output_file);参数调优经验容器尺寸的设定如果容器尺寸是固定的如标准板材那就直接输入。但有时我们可以决定容器尺寸。一个常见策略是固定宽度如卷材宽度优化高度使所需板材长度最短。这时可以将算法包装在一个循环里尝试不同的容器高度直到能放下所有矩形并找到最小高度。排序规则的组合与创新除了单一属性排序可以尝试更复杂的规则。例如“先按面积降序面积相同的按长边降序”。甚至可以采用“动态排序”在放置过程中根据当前轮廓线的形状选择最能“填补缺口”的矩形。这属于更高级的启发式策略。旋转矩形的支持在实际生产中矩形物品通常可以90度旋转。支持旋转能显著提高利用率。修改起来也简单在尝试放置一个矩形时同时尝试其原始方向(w, h)和旋转后的方向(h, w)选择那个能放置且可能带来更好匹配度的方向。这会使搜索空间翻倍但效果提升明显。5. 常见问题、调试技巧与性能优化在实际编码和运行中你肯定会遇到各种问题。下面是我踩过的一些坑和解决方法。5.1 算法逻辑问题问题1矩形重叠。这是最严重的BUG。可视化后如果看到矩形交叉一定是轮廓线更新逻辑update_skyline或放置可行性检查check_fit有误。排查在update_skyline函数内部添加详细打印输出更新前后的轮廓线坐标。放置每个矩形后立即调用一个validate_packing函数检查所有已放置矩形两两之间是否重叠以及是否超出容器边界。这个验证函数虽然计算量大O(n²)但在调试阶段极其重要。根源通常是处理轮廓线分段合并时对边界情况如新线段恰好与旧线段端点重合考虑不周。问题2算法“卡住”过早结束。明明还有空间但算法却报告无法放置下一个矩形。排查检查check_fit函数。可能是条件过于严格。确保它只检查矩形底部所在区间的轮廓线高度而不是整个x跨度下的最大高度。有时轮廓线是锯齿状的矩形底部只能与局部最低点对齐。可视化调试在无法放置时将当前的轮廓线和待放置的矩形画出来。你能一眼看出为什么算法认为放不下是检查逻辑错误还是确实空间碎片化了。5.2 MATLAB实现性能问题当矩形数量很多比如1000时基础的双重循环遍历矩形 * 扫描轮廓线可能会变慢。优化1轮廓线数据结构。用数组存储轮廓线每次更新都涉及数组元素的插入和删除skyline [skyline(1:k,:); new_point; skyline(k1:end,:)]这在MATLAB中对于大型数组效率不高。可以考虑使用更高效的数据结构如“平衡二叉搜索树”来管理轮廓线段但实现复杂。一个折中的方法是在轮廓线点不多时用数组并预分配足够大的空间。优化2向量化扫描。在扫描轮廓线寻找放置点时避免在for s 1:size(skyline,1)-1循环内进行复杂的计算。可以尝试将轮廓线信息向量化一次性计算所有线段的可行性。但这受限于算法逻辑不一定容易实现。优化3减少重复计算。check_fit函数会被频繁调用确保其内部逻辑简洁。例如可以预先计算轮廓线在每个x整数坐标上的高度图如果容器宽度是整数这样检查就变成了O(1)的查表操作。重要提示对于数学建模竞赛或学术研究矩形数量通常在几十到几百个基础的实现完全够用优先保证正确性和可读性。对于工业级应用成千上万个零件则需要考虑上述性能优化甚至用C等语言重写核心算法MATLAB作为调用和可视化前端。5.3 结果不理想利用率低如果尝试了多种排序规则利用率仍然不高可能的原因和应对策略问题现象可能原因解决思路顶部留下大面积空白排序规则导致先放了太多矮胖矩形剩下高瘦矩形无处可放。尝试“高度降序”规则优先解决垂直方向的空间占用。右侧留下细长空白算法总是从左向右放可能不适用于所有情况。1. 尝试“宽度降序”规则。2. 引入“多容器”或“多级排样”思路先排大矩形剩下的零料集中再排一次。空间碎片化严重最低水平线算法本身的缺陷。1. 在放置选择时不仅看“最低”还看“最匹配”即evaluate_fit函数。2. 采用更高级的算法如“最大剩余矩形”算法或“模拟退火”、“遗传算法”等元启发式算法。进阶方向当基础算法无法满足需求时可以考虑混合策略。例如用最低水平线算法快速生成一个初始解然后用局部搜索如交换两个矩形的位置、旋转某个矩形进行迭代改进这就是一个简单的“迭代改善”启发式。或者将问题建模为整数规划调用MATLAB的优化工具箱如intlinprog求解虽然对于大规模问题较慢但对于小规模问题能得到最优解用于验证启发式算法的质量。最后我想强调的是二维排样没有“银弹”。这套基于最低水平线的MATLAB代码提供了一个强大、灵活且可视化的起点。通过调整排序规则、引入旋转、甚至结合多种算法策略你可以将它适配到各种具体的应用场景中。真正的技巧在于根据你手中那批矩形数据的特性尺寸分布、大小差异等通过实验找到最适合的参数组合。这本身就是一个有趣的优化过程。代码的价值不仅在于运行出结果更在于它为你提供了一个可以任意拆解、修改和试验的沙盒让你能深入理解这个经典优化问题的脉络。
1. 项目概述从“乱放”到“最优排布”的工程实践二维矩形排样听起来是个学术名词但它的核心问题我们生活中随处可见。想象一下你是一个家具厂的切割工面对一堆大小不一的矩形木板原料大板如何切割才能浪费最少或者你是一个物流仓库的管理员如何把一批尺寸各异的货箱尽可能紧密地装进一个标准集装箱里再或者你是一个PCB印刷电路板的工程师如何在有限的板子上排列出最多的芯片以降低成本这些问题的本质都是二维矩形排样。在数学建模和工业工程领域这被称为“二维矩形排样问题”或“二维下料问题”。它的目标非常明确在给定的一个或多个大矩形板材容器内放置一系列已知尺寸的小矩形物品使得所有物品都能被容纳并且通常追求某个指标的最优化——最常见的就是“材料利用率”最高即所有小矩形总面积占所用大矩形总面积的比例最大从而让废料最少。手动去排当物品数量超过十个人脑基本就难以找到最优解了。这时候就需要算法和代码来帮忙。MATLAB作为科学计算和算法原型的利器因其强大的矩阵运算能力和丰富的可视化工具成为实现这类组合优化算法的绝佳平台。我这次要分享的就是一套用MATLAB从零开始实现的二维矩形排样代码。这不是一个简单的“玩具”代码而是融入了实际工程中常用的启发式策略能够处理数十甚至上百个矩形件的排样并给出可视化的排样图让你直观地看到算法是如何“思考”和“摆放”的。这套代码适合谁呢如果你是数学建模的参赛队员正在备战国赛、美赛或亚太杯其中常有涉及资源优化、物流调度的问题排样算法是一个强有力的模型工具。如果你是机械、材料、电子相关专业的学生或工程师需要解决实际的下料、布局问题这套代码可以作为一个可靠的起点。即使你只是对优化算法感兴趣想看看代码如何解决这样一个经典的NP-Hard难题这里也有清晰的思路和实现细节等你探索。2. 核心算法思路如何教会计算机“摆放”二维矩形排样问题在计算复杂性上属于NP-Hard问题这意味着随着矩形数量的增加找到绝对最优解所需的时间会呈指数级增长。因此我们退而求其次追求在合理时间内找到一个“足够好”的、高利用率的可行解。业界和学术界提出了多种启发式算法其中“最低水平线算法”及其变种因其简单、高效且效果不错成为了最常用的方法之一。我们代码的核心就基于此。2.1 算法骨架最低水平线算法Bottom-Left Fill这个算法的思想非常直观模拟了一个人从容器左下角开始尽可能向左、向下放置物品的过程。你可以把它想象成往一个箱子里放书总是先把书推到箱子的最左边和最底下。算法的核心流程如下初始化将容器大矩形的顶部轮廓线初始化为一条从容器左下角到右下角的水平线其高度为0。我们用一个列表来记录当前轮廓线它由一系列x坐标 高度的点构成。矩形排序将所有待排放的矩形按照某种规则排序如高度递减、面积递减、周长递减等。排序策略直接影响最终效果通常优先放置大的、难以安排的矩形。迭代放置 a. 从排序好的矩形列表中取出下一个矩形。 b. 在当前轮廓线上从左到右扫描寻找一个可以放置该矩形的位置。这个位置需要满足两个条件第一矩形放置后其右边界不超过容器宽度第二矩形放置的底部即轮廓线在该段的最高点加上矩形高度不超过容器高度。 c. 在所有可放置的位置中选择一个使得矩形放置后其顶部轮廓线最低的位置。这就是“最低水平线”的含义——总是把新矩形放在当前“坑”最深的地方以保持整体轮廓的平整为后续矩形留出空间。 d. 放置矩形并更新容器的顶部轮廓线。放置后原来平坦的轮廓线会被抬升形成新的、更复杂的轮廓。循环重复步骤3直到所有矩形放置完毕或无法再放置任何矩形。这个算法的优势在于它只维护一条动态变化的轮廓线计算复杂度相对较低。但它也有缺点比如可能产生“碎片”——即一些太小而无法利用的零散空间。2.2 我们的增强策略多规则排序与放置点选择在基础的最低水平线算法上我结合实践做了几点关键增强这也是代码实用性的核心。首先是矩形的排序规则。单一规则往往有局限性。我的代码实现了多种排序规则并允许在运行时指定或组合尝试按高度降序优先放置高的矩形可以有效减少在垂直方向上产生的“峡谷”是效果最稳定、最常用的规则之一。按面积降序优先放置大矩形直观上有利于先解决“难题”。按宽度降序有时对宽容器有效。综合评分例如(高度 宽度) / 2的降序作为一种折中策略。 在实际运行时我常常会尝试2-3种不同的排序规则然后选择材料利用率最高的那个结果。代码中可以通过一个循环轻松实现这一点。其次是放置点的选择策略。基础算法只选择“最低水平线”的位置。但有时“最低”的位置可能不是“最好”的。例如有两个高度相同的“坑”一个很宽一个很窄。把矩形放在宽坑里可能会浪费旁边的空间放在窄坑里可能更贴合。因此我在代码中加入了一个可选的“最佳匹配”评估。在找到所有可行的最低水平线位置后不是简单地选择第一个而是计算每个位置放置后新矩形与相邻轮廓线形成的“空洞”大小即浪费的潜在空间选择空洞最小的那个位置。这个策略稍微增加了计算量但有时能提升1%-3%的利用率对于工业场景这意味著可观的成本节约。注意排序规则是影响排样结果的最关键因素没有之一。不同的规则会导致利用率差异巨大。对于一批特定的矩形数据没有永远最好的规则。因此在实际应用中将多种排序规则作为“候选策略”并行运行最后取最优解是一个非常重要的工程实践。3. 代码结构与关键模块解析下面我们来拆解MATLAB代码的核心模块。整个项目主要包含以下几个函数文件main.m主脚本负责读取数据、设置参数、调用算法并可视化结果。load_rectangles.m数据加载函数可以从文本文件或Excel表格中读取矩形尺寸。sort_rectangles.m矩形排序函数根据指定规则对矩形列表进行排序。bottom_left_fill.m核心算法函数实现增强版的最低水平线排样。plot_packing.m可视化函数绘制最终的排样图。3.1 数据输入与预处理 (load_rectangles.m)数据格式通常是一个 Nx2 的矩阵每一行代表一个矩形第一列是宽度w第二列是高度h。容器尺寸plate_width,plate_height作为参数输入。function rect_list load_rectangles(filename) % 从文件加载矩形尺寸 % 假设文件是纯文本每行是 宽度 高度 data load(filename); rect_list data; % 或者根据格式进行解析 end在实际项目中数据可能来自CAD图纸或生产订单系统。这个函数需要根据实际数据源格式进行定制比如处理Excel的xlsread或readtable。3.2 核心算法实现 (bottom_left_fill.m)这是代码的“心脏”。我详细解释一下其内部数据结构与关键步骤。数据结构设计rectangles: 排序后的矩形列表每个矩形是[id, w, h]id用于追踪。plate_width,plate_height: 容器宽高。skyline: 轮廓线。我使用一个Mx2的数组表示skyline(:,1)是x坐标分段起点skyline(:,2)是该段的高度。初始状态为[0, 0; plate_width, 0]。placed_rects: 记录已放置矩形的位置信息每个元素是[id, x, y, w, h]。关键步骤伪代码与MATLAB实现思路function [placed_rects, utilization] bottom_left_fill(rectangles, plate_width, plate_height, sort_rule) % 初始化 skyline [0, 0; plate_width, 0]; placed_rects []; for i 1:size(rectangles, 1) rect rectangles(i, :); % [id, w, h] best_x -1; best_y -1; best_fit_score inf; % 用于最佳匹配评估 % 步骤1: 扫描轮廓线寻找候选位置 for s 1:size(skyline, 1)-1 seg_start_x skyline(s, 1); seg_end_x skyline(s1, 1); seg_height skyline(s, 2); % 候选放置的x坐标就是当前线段的起点 cand_x seg_start_x; % 放置后的y坐标就是当前线段的高度 cand_y seg_height; % 检查放置是否可行右边界和上边界不超出容器 if cand_x rect(2) plate_width cand_y rect(3) plate_height % 检查在 [cand_x, cand_xw] 区间内底部是否平整即所有轮廓线高度都 cand_y % 这是一个关键检查防止矩形悬空 if check_fit(skyline, cand_x, rect(2), cand_y) % 计算匹配分数例如放置后顶部轮廓线的平整度或空间浪费 fit_score evaluate_fit(skyline, cand_x, rect(2), cand_y, seg_height); if fit_score best_fit_score best_fit_score fit_score; best_x cand_x; best_y cand_y; end end end end % 步骤2: 如果找到位置放置矩形并更新轮廓线 if best_x 0 % 记录放置信息 placed_rects [placed_rects; rect(1), best_x, best_y, rect(2), rect(3)]; % 更新轮廓线 skyline skyline update_skyline(skyline, best_x, rect(2), best_y rect(3)); else % 如果没找到位置可以跳过此矩形记录为未放置 warning(矩形 ID %d (%.1fx%.1f) 无法放置。, rect(1), rect(2), rect(3)); end end % 计算材料利用率 total_area sum(placed_rects(:,4) .* placed_rects(:,5)); plate_area plate_width * plate_height; utilization total_area / plate_area; endcheck_fit和update_skyline是两个需要精心实现的子函数。check_fit: 需要遍历skyline判断在区间[cand_x, cand_xw]内所有轮廓线的高度是否都不大于cand_y。如果不是说明矩形底部有“凸起”无法平稳放置。update_skyline: 这是算法中最繁琐的部分。在位置(best_x, best_yh)插入一条新的水平线段。这需要处理多种情况新线段可能与原有线段重叠、相交、分割原有线段。正确的更新是保证算法后续迭代正确的基石。通常的做法是先将新线段的起点和终点插入轮廓线点序列然后重新计算整个轮廓线的高度取每个x点上所有线段高度的最大值。实操心得update_skyline函数的实现很容易出BUG。一个有效的调试方法是在每次更新轮廓线后立即用plot函数将其绘制出来与矩形放置图叠加肉眼观察轮廓线变化是否符合预期。MATLAB的即时可视化能力在这里是巨大的优势。3.3 可视化输出 (plot_packing.m)“一图胜千言”尤其是对于布局问题。可视化模块不仅用于展示最终结果更是调试和验证算法的重要工具。function plot_packing(placed_rects, plate_width, plate_height, utilization) figure(Position, [100, 100, 800, 600]); hold on; % 绘制容器边框 rectangle(Position, [0, 0, plate_width, plate_height], EdgeColor, k, LineWidth, 2); % 绘制每个矩形 colors lines(size(placed_rects, 1)); % 使用不同的颜色 for i 1:size(placed_rects, 1) rect placed_rects(i, :); id rect(1); x rect(2); y rect(3); w rect(4); h rect(5); % 绘制矩形填充 rectangle(Position, [x, y, w, h], FaceColor, colors(i, :), EdgeColor, k, LineWidth, 1); % 在矩形中心添加文本标签ID和尺寸 text(x w/2, y h/2, sprintf(%d\n%.0fx%.0f, id, w, h), ... HorizontalAlignment, center, VerticalAlignment, middle, ... FontSize, 8, Color, white); end hold off; axis equal; xlim([-1, plate_width1]); ylim([-1, plate_height1]); grid on; title(sprintf(二维矩形排样结果 - 材料利用率: %.2f%%, utilization*100)); xlabel(宽度); ylabel(高度); end这个绘图函数会生成一个带网格的图每个矩形用不同颜色填充并标注其ID和尺寸。材料利用率会显示在标题中。通过观察图形你可以直观判断算法是否紧凑是否存在明显的空间浪费。4. 完整工作流与参数调优实战有了以上模块我们就可以串联起一个完整的工作流。在main.m脚本中流程如下%% 1. 参数设置 plate_width 100; % 容器宽度 plate_height 50; % 容器高度 data_file rect_data.txt; % 矩形数据文件 sort_rules {height, area, width}; % 要尝试的排序规则列表 %% 2. 加载数据 rect_list_raw load_rectangles(data_file); % 为每个矩形添加ID rect_list_raw [(1:size(rect_list_raw,1)), rect_list_raw]; best_utilization 0; best_placed_rects []; best_rule ; %% 3. 多规则尝试 for i 1:length(sort_rules) rule sort_rules{i}; fprintf(尝试排序规则: %s\n, rule); % 排序 sorted_rects sort_rectangles(rect_list_raw, rule); % 执行排样算法 [placed_rects, utilization] bottom_left_fill(sorted_rects, plate_width, plate_height, rule); fprintf( 材料利用率: %.2f%%\n, utilization*100); % 记录最佳结果 if utilization best_utilization best_utilization utilization; best_placed_rects placed_rects; best_rule rule; end end %% 4. 输出与可视化最佳结果 fprintf(\n最佳排序规则: %s\n, best_rule); fprintf(最高材料利用率: %.2f%%\n, best_utilization*100); plot_packing(best_placed_rects, plate_width, plate_height, best_utilization); %% 5. (可选) 输出排样坐标文件用于生产 output_file packing_result.csv; writematrix(best_placed_rects, output_file);参数调优经验容器尺寸的设定如果容器尺寸是固定的如标准板材那就直接输入。但有时我们可以决定容器尺寸。一个常见策略是固定宽度如卷材宽度优化高度使所需板材长度最短。这时可以将算法包装在一个循环里尝试不同的容器高度直到能放下所有矩形并找到最小高度。排序规则的组合与创新除了单一属性排序可以尝试更复杂的规则。例如“先按面积降序面积相同的按长边降序”。甚至可以采用“动态排序”在放置过程中根据当前轮廓线的形状选择最能“填补缺口”的矩形。这属于更高级的启发式策略。旋转矩形的支持在实际生产中矩形物品通常可以90度旋转。支持旋转能显著提高利用率。修改起来也简单在尝试放置一个矩形时同时尝试其原始方向(w, h)和旋转后的方向(h, w)选择那个能放置且可能带来更好匹配度的方向。这会使搜索空间翻倍但效果提升明显。5. 常见问题、调试技巧与性能优化在实际编码和运行中你肯定会遇到各种问题。下面是我踩过的一些坑和解决方法。5.1 算法逻辑问题问题1矩形重叠。这是最严重的BUG。可视化后如果看到矩形交叉一定是轮廓线更新逻辑update_skyline或放置可行性检查check_fit有误。排查在update_skyline函数内部添加详细打印输出更新前后的轮廓线坐标。放置每个矩形后立即调用一个validate_packing函数检查所有已放置矩形两两之间是否重叠以及是否超出容器边界。这个验证函数虽然计算量大O(n²)但在调试阶段极其重要。根源通常是处理轮廓线分段合并时对边界情况如新线段恰好与旧线段端点重合考虑不周。问题2算法“卡住”过早结束。明明还有空间但算法却报告无法放置下一个矩形。排查检查check_fit函数。可能是条件过于严格。确保它只检查矩形底部所在区间的轮廓线高度而不是整个x跨度下的最大高度。有时轮廓线是锯齿状的矩形底部只能与局部最低点对齐。可视化调试在无法放置时将当前的轮廓线和待放置的矩形画出来。你能一眼看出为什么算法认为放不下是检查逻辑错误还是确实空间碎片化了。5.2 MATLAB实现性能问题当矩形数量很多比如1000时基础的双重循环遍历矩形 * 扫描轮廓线可能会变慢。优化1轮廓线数据结构。用数组存储轮廓线每次更新都涉及数组元素的插入和删除skyline [skyline(1:k,:); new_point; skyline(k1:end,:)]这在MATLAB中对于大型数组效率不高。可以考虑使用更高效的数据结构如“平衡二叉搜索树”来管理轮廓线段但实现复杂。一个折中的方法是在轮廓线点不多时用数组并预分配足够大的空间。优化2向量化扫描。在扫描轮廓线寻找放置点时避免在for s 1:size(skyline,1)-1循环内进行复杂的计算。可以尝试将轮廓线信息向量化一次性计算所有线段的可行性。但这受限于算法逻辑不一定容易实现。优化3减少重复计算。check_fit函数会被频繁调用确保其内部逻辑简洁。例如可以预先计算轮廓线在每个x整数坐标上的高度图如果容器宽度是整数这样检查就变成了O(1)的查表操作。重要提示对于数学建模竞赛或学术研究矩形数量通常在几十到几百个基础的实现完全够用优先保证正确性和可读性。对于工业级应用成千上万个零件则需要考虑上述性能优化甚至用C等语言重写核心算法MATLAB作为调用和可视化前端。5.3 结果不理想利用率低如果尝试了多种排序规则利用率仍然不高可能的原因和应对策略问题现象可能原因解决思路顶部留下大面积空白排序规则导致先放了太多矮胖矩形剩下高瘦矩形无处可放。尝试“高度降序”规则优先解决垂直方向的空间占用。右侧留下细长空白算法总是从左向右放可能不适用于所有情况。1. 尝试“宽度降序”规则。2. 引入“多容器”或“多级排样”思路先排大矩形剩下的零料集中再排一次。空间碎片化严重最低水平线算法本身的缺陷。1. 在放置选择时不仅看“最低”还看“最匹配”即evaluate_fit函数。2. 采用更高级的算法如“最大剩余矩形”算法或“模拟退火”、“遗传算法”等元启发式算法。进阶方向当基础算法无法满足需求时可以考虑混合策略。例如用最低水平线算法快速生成一个初始解然后用局部搜索如交换两个矩形的位置、旋转某个矩形进行迭代改进这就是一个简单的“迭代改善”启发式。或者将问题建模为整数规划调用MATLAB的优化工具箱如intlinprog求解虽然对于大规模问题较慢但对于小规模问题能得到最优解用于验证启发式算法的质量。最后我想强调的是二维排样没有“银弹”。这套基于最低水平线的MATLAB代码提供了一个强大、灵活且可视化的起点。通过调整排序规则、引入旋转、甚至结合多种算法策略你可以将它适配到各种具体的应用场景中。真正的技巧在于根据你手中那批矩形数据的特性尺寸分布、大小差异等通过实验找到最适合的参数组合。这本身就是一个有趣的优化过程。代码的价值不仅在于运行出结果更在于它为你提供了一个可以任意拆解、修改和试验的沙盒让你能深入理解这个经典优化问题的脉络。
![[光学原理与应用-521]：对光的错误理解与纠偏](http://pic.xiahunao.cn/yaotu/[光学原理与应用-521]：对光的错误理解与纠偏)
