企业官网建设流程全解析

1. 项目概述：从“乱放”到“最优排布”的工程实践

二维矩形排样，听起来是个学术名词，但它的核心问题我们生活中随处可见。想象一下，你是一个家具厂的切割工，面对一堆大小不一的矩形木板（原料大板），如何切割才能浪费最少？或者你是一个物流仓库的管理员，如何把一批尺寸各异的货箱尽可能紧密地装进一个标准集装箱里？再或者，你是一个PCB（印刷电路板）的工程师，如何在有限的板子上排列出最多的芯片，以降低成本？这些问题的本质，都是二维矩形排样。

在数学建模和工业工程领域，这被称为“二维矩形排样问题”或“二维下料问题”。它的目标非常明确：在给定的一个或多个大矩形板材（容器）内，放置一系列已知尺寸的小矩形（物品），使得所有物品都能被容纳，并且通常追求某个指标的最优化——最常见的就是“材料利用率”最高，即所有小矩形总面积占所用大矩形总面积的比例最大，从而让废料最少。

手动去排？当物品数量超过十个，人脑基本就难以找到最优解了。这时候就需要算法和代码来帮忙。MATLAB，作为科学计算和算法原型的利器，因其强大的矩阵运算能力和丰富的可视化工具，成为实现这类组合优化算法的绝佳平台。我这次要分享的，就是一套用MATLAB从零开始实现的二维矩形排样代码。这不是一个简单的“玩具”代码，而是融入了实际工程中常用的启发式策略，能够处理数十甚至上百个矩形件的排样，并给出可视化的排样图，让你直观地看到算法是如何“思考”和“摆放”的。

这套代码适合谁呢？如果你是数学建模的参赛队员，正在备战国赛、美赛或亚太杯，其中常有涉及资源优化、物流调度的问题，排样算法是一个强有力的模型工具。如果你是机械、材料、电子相关专业的学生或工程师，需要解决实际的下料、布局问题，这套代码可以作为一个可靠的起点。即使你只是对优化算法感兴趣，想看看代码如何解决这样一个经典的NP-Hard难题，这里也有清晰的思路和实现细节等你探索。

2. 核心算法思路：如何教会计算机“摆放”

二维矩形排样问题在计算复杂性上属于NP-Hard问题，这意味着随着矩形数量的增加，找到绝对最优解所需的时间会呈指数级增长。因此，我们退而求其次，追求在合理时间内找到一个“足够好”的、高利用率的可行解。业界和学术界提出了多种启发式算法，其中“最低水平线算法”及其变种因其简单、高效且效果不错，成为了最常用的方法之一。我们代码的核心就基于此。

2.1 算法骨架：最低水平线算法（Bottom-Left Fill）

这个算法的思想非常直观，模拟了一个人从容器左下角开始，尽可能向左、向下放置物品的过程。你可以把它想象成往一个箱子里放书，总是先把书推到箱子的最左边和最底下。

算法的核心流程如下：

1. 初始化：将容器（大矩形）的顶部轮廓线初始化为一条从容器左下角到右下角的水平线，其高度为0。我们用一个列表来记录当前轮廓线，它由一系列（x坐标， 高度）的点构成。
2. 矩形排序：将所有待排放的矩形按照某种规则排序（如高度递减、面积递减、周长递减等）。排序策略直接影响最终效果，通常优先放置大的、难以安排的矩形。
3. 迭代放置： a. 从排序好的矩形列表中取出下一个矩形。 b. 在当前轮廓线上，从左到右扫描，寻找一个可以放置该矩形的位置。这个位置需要满足两个条件：第一，矩形放置后其右边界不超过容器宽度；第二，矩形放置的底部（即轮廓线在该段的最高点）加上矩形高度不超过容器高度。 c. 在所有可放置的位置中，选择一个使得矩形放置后其顶部轮廓线最低的位置。这就是“最低水平线”的含义——总是把新矩形放在当前“坑”最深的地方，以保持整体轮廓的平整，为后续矩形留出空间。 d. 放置矩形，并更新容器的顶部轮廓线。放置后，原来平坦的轮廓线会被抬升，形成新的、更复杂的轮廓。
4. 循环：重复步骤3，直到所有矩形放置完毕或无法再放置任何矩形。

这个算法的优势在于它只维护一条动态变化的轮廓线，计算复杂度相对较低。但它也有缺点，比如可能产生“碎片”——即一些太小而无法利用的零散空间。

2.2 我们的增强策略：多规则排序与放置点选择

在基础的最低水平线算法上，我结合实践做了几点关键增强，这也是代码实用性的核心。

首先，是矩形的排序规则。单一规则往往有局限性。我的代码实现了多种排序规则，并允许在运行时指定或组合尝试：

• 按高度降序：优先放置高的矩形，可以有效减少在垂直方向上产生的“峡谷”，是效果最稳定、最常用的规则之一。
• 按面积降序：优先放置大矩形，直观上有利于先解决“难题”。
• 按宽度降序：有时对宽容器有效。
• 综合评分：例如(高度 + 宽度) / 2的降序，作为一种折中策略。 在实际运行时，我常常会尝试2-3种不同的排序规则，然后选择材料利用率最高的那个结果。代码中可以通过一个循环轻松实现这一点。

其次，是放置点的选择策略。基础算法只选择“最低水平线”的位置。但有时“最低”的位置可能不是“最好”的。例如，有两个高度相同的“坑”，一个很宽，一个很窄。把矩形放在宽坑里，可能会浪费旁边的空间；放在窄坑里，可能更贴合。因此，我在代码中加入了一个可选的“最佳匹配”评估。在找到所有可行的最低水平线位置后，不是简单地选择第一个，而是计算每个位置放置后，新矩形与相邻轮廓线形成的“空洞”大小（即浪费的潜在空间），选择空洞最小的那个位置。这个策略稍微增加了计算量，但有时能提升1%-3%的利用率，对于工业场景，这意味著可观的成本节约。

注意：排序规则是影响排样结果的最关键因素，没有之一。不同的规则会导致利用率差异巨大。对于一批特定的矩形数据，没有永远最好的规则。因此，在实际应用中，将多种排序规则作为“候选策略”并行运行，最后取最优解，是一个非常重要的工程实践。

3. 代码结构与关键模块解析

下面，我们来拆解MATLAB代码的核心模块。整个项目主要包含以下几个函数文件：

1. main.m：主脚本，负责读取数据、设置参数、调用算法并可视化结果。
2. load_rectangles.m：数据加载函数，可以从文本文件或Excel表格中读取矩形尺寸。
3. sort_rectangles.m：矩形排序函数，根据指定规则对矩形列表进行排序。
4. bottom_left_fill.m：核心算法函数，实现增强版的最低水平线排样。
5. 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(s+1, 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_x+w] 区间内，底部是否平整（即所有轮廓线高度都 <= 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; end

check_fit和update_skyline是两个需要精心实现的子函数。

• check_fit: 需要遍历skyline，判断在区间[cand_x, cand_x+w]内，所有轮廓线的高度是否都不大于cand_y。如果不是，说明矩形底部有“凸起”，无法平稳放置。
• update_skyline: 这是算法中最繁琐的部分。在位置(best_x, best_y+h)插入一条新的水平线段。这需要处理多种情况：新线段可能与原有线段重叠、相交、分割原有线段。正确的更新是保证算法后续迭代正确的基石。通常的做法是，先将新线段的起点和终点插入轮廓线点序列，然后重新计算整个轮廓线的高度（取每个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_width+1]); ylim([-1, plate_height+1]); 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);

参数调优经验：

1. 容器尺寸的设定：如果容器尺寸是固定的（如标准板材），那就直接输入。但有时我们可以决定容器尺寸。一个常见策略是固定宽度（如卷材宽度），优化高度（使所需板材长度最短）。这时，可以将算法包装在一个循环里，尝试不同的容器高度，直到能放下所有矩形，并找到最小高度。
2. 排序规则的组合与创新：除了单一属性排序，可以尝试更复杂的规则。例如，“先按面积降序，面积相同的按长边降序”。甚至可以采用“动态排序”，在放置过程中，根据当前轮廓线的形状，选择最能“填补缺口”的矩形。这属于更高级的启发式策略。
3. 旋转矩形的支持：在实际生产中，矩形物品通常可以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(k+1:end,:)]），这在MATLAB中对于大型数组效率不高。可以考虑使用更高效的数据结构，如“平衡二叉搜索树”来管理轮廓线段，但实现复杂。一个折中的方法是，在轮廓线点不多时用数组，并预分配足够大的空间。
• 优化2：向量化扫描。在扫描轮廓线寻找放置点时，避免在for s = 1:size(skyline,1)-1循环内进行复杂的计算。可以尝试将轮廓线信息向量化，一次性计算所有线段的可行性。但这受限于算法逻辑，不一定容易实现。
• 优化3：减少重复计算。check_fit函数会被频繁调用，确保其内部逻辑简洁。例如，可以预先计算轮廓线在每个x整数坐标上的高度图（如果容器宽度是整数），这样检查就变成了O(1)的查表操作。

重要提示：对于数学建模竞赛或学术研究，矩形数量通常在几十到几百个，基础的实现完全够用，优先保证正确性和可读性。对于工业级应用（成千上万个零件），则需要考虑上述性能优化，甚至用C++等语言重写核心算法，MATLAB作为调用和可视化前端。

5.3 结果不理想（利用率低）

如果尝试了多种排序规则，利用率仍然不高，可能的原因和应对策略：

进阶方向：当基础算法无法满足需求时，可以考虑混合策略。例如，用最低水平线算法快速生成一个初始解，然后用局部搜索（如交换两个矩形的位置、旋转某个矩形）进行迭代改进，这就是一个简单的“迭代改善”启发式。或者，将问题建模为整数规划，调用MATLAB的优化工具箱（如intlinprog）求解，虽然对于大规模问题较慢，但对于小规模问题能得到最优解，用于验证启发式算法的质量。

最后，我想强调的是，二维排样没有“银弹”。这套基于最低水平线的MATLAB代码，提供了一个强大、灵活且可视化的起点。通过调整排序规则、引入旋转、甚至结合多种算法策略，你可以将它适配到各种具体的应用场景中。真正的技巧在于，根据你手中那批矩形数据的特性（尺寸分布、大小差异等），通过实验找到最适合的参数组合。这本身就是一个有趣的优化过程。代码的价值不仅在于运行出结果，更在于它为你提供了一个可以任意拆解、修改和试验的沙盒，让你能深入理解这个经典优化问题的脉络。