C++实现矩形排样优化：从算法原理到工业级应用实践

1. 项目概述：从“能排”到“排得好”的跨越

矩形排样，听起来像是个简单的几何拼图，但当你真正面对一堆尺寸各异的矩形零件，需要把它们塞进一块固定大小的板材里，并且要求材料利用率最高、切割路径最短时，问题立刻就变得复杂起来。这不仅仅是“放得下”，更是“如何放得最省、最快、最好”。我最初接触这个问题，是在一个定制家具厂的项目里，看着老师傅凭经验在板材上画线，边角料堆积如山，我就知道这里面有巨大的优化空间。后来，从钣金加工、服装裁剪到集成电路布局，矩形排样（或称二维矩形装箱问题）都是一个核心的、能直接产生经济效益的优化课题。

用C++来实现这个解决方案，几乎是工业级应用的自然选择。C++在性能上的优势，使得它能够处理成千上万个矩形零件的排样计算，在合理的时间内找到近似最优解。这不像Python写个脚本跑个demo，C++的解决方案是奔着7x24小时稳定运行、嵌入到实际生产CAM（计算机辅助制造）系统中去的。今天，我就把自己在多个项目中打磨过的一套C++矩形排样解决方案的核心思路、关键算法和那些踩过坑才得来的经验，系统地梳理出来。无论你是正在学习算法优化的大学生，还是需要解决实际生产中材料优化问题的工程师，这篇文章都能给你提供一个从理论到实践的完整参考框架。

2. 核心算法选型与思路拆解

矩形排样问题在学术上被归类为NP-hard问题，这意味着当矩形数量较多时，找到绝对的最优解在计算上是不可行的。因此，所有实用的解决方案都是启发式算法，旨在用可接受的时间找到一个“足够好”的解。我们的核心思路是模拟一个最符合人类直觉且易于计算机实现的放置过程：从左到右、从下到上，寻找最低可放置点。但这只是骨架，真正的优化艺术藏在细节里。

2.1 主流算法策略对比

在动手写代码前，我们必须明确要采用哪种策略。常见的策略主要有以下几种：

1. 最低水平线算法（Bottom-Left, BL）：这是最朴素也是很多改进算法的基础。它的规则很简单：始终将下一个矩形放置在当前所有已放置矩形所形成的轮廓线（我们称之为“天际线”或“轮廓线”）中，高度最低的那个位置，如果有多处高度相同，则选择最左边的那一处。这个算法实现简单，速度快，但容易在顶部留下许多难以利用的狭长空间。

2. 最佳适应度算法（Best-Fit）：这种算法不仅仅看高度，还会评估矩形放入某个空缺后，其与相邻矩形的贴合程度，或者评估放入后剩余空间的“浪费”程度。例如，优先选择放入后能使得轮廓线更加平整（即剩余空间更规整）的位置。这通常能得到比BL更好的利用率，但计算量会增大。

3. 启发式搜索算法（如遗传算法、模拟退火、禁忌搜索）：这类算法不直接定义放置规则，而是将一种排样顺序或排样方案编码为一个“个体”或“状态”，通过模拟自然进化或物理退火过程，不断迭代产生新的方案，并保留更好的方案。这类算法潜力最大，有可能找到非常优秀的解，但计算时间最长，参数调优复杂。

对于大多数需要平衡性能与效果的工业场景，基于最低水平线并加以改进的启发式算法是一个黄金起点。我们的C++实现也将以此为核心。

2.2 我们的核心算法框架设计

我们设计的算法框架可以概括为“预排序 + 多规则放置 + 轮廓线管理”。

• 预排序：矩形的放入顺序极大地影响最终结果。我们不会随机放入。常见的排序规则有：

  • 面积降序（先大后小）
  • 周长降序
  • 最长边降序
  • 宽度降序
  • 随机排序（用于某些元启发式算法中增加多样性） 在实际操作中，按面积或最长边降序排列往往能取得不错的基础效果，因为先处理大件可以为小件填充缝隙创造条件。

• 多规则放置：这是对基础BL算法的增强。我们不仅寻找最低点，还为每一个可放置的“最低点”定义一个评估函数。例如：

  • 规则A（最低高度优先）：经典BL规则。
  • 规则B（最小浪费面积优先）：计算矩形放入后，其顶部和右侧新产生的“空洞”面积之和，选择总和最小的位置。
  • 规则C（贴合度优先）：评估矩形放入后，其左边和底边与已有矩形或板材边界的接触长度，选择接触总长度最大的位置，这有利于稳定性（在物理切割中很重要）。 我们的算法可以依次尝试这些规则，并为每个矩形选择能产生最佳评估值的位置。

• 轮廓线管理：这是算法效率的关键。我们不会在每次放置时都扫描整个板材的二维矩阵（那太慢了）。我们用一组水平线段（每个线段有左端点x、右端点x和高度y）来动态表示当前板材的占用轮廓。放置矩形时，只需在这个线段集合中寻找合适的空隙，并在放置后更新受影响的线段即可。数据结构上，使用std::vector<std::tuple<int, int, int>>（左， 右， 高）来维护就非常高效。

注意：排序规则没有绝对的最优。一个经验法则是，对于矩形尺寸差异巨大的情况，按面积降序效果好；对于尺寸较为均匀的情况，按最长边降序可能更优。最好的方式是在你的实际数据上做一个小规模的对比测试。

3. 关键数据结构与核心代码解析

有了清晰的思路，我们来看看如何用C++将其实现。我们将代码模块化，使其清晰且易于扩展。

3.1 数据结构定义

首先，定义我们需要的核心结构体。

// rect_packing.h #ifndef RECT_PACKING_H #define RECT_PACKING_H #include <vector> #include <tuple> // 矩形定义 struct Rect { int id; // 矩形唯一标识 int width; // 宽 int height; // 高 int x; // 放置后的左下角x坐标 int y; // 放置后的左下角y坐标 bool rotated; // 是否被旋转（宽高互换） Rect(int i, int w, int h) : id(i), width(w), height(h), x(0), y(0), rotated(false) {} }; // 轮廓线段定义： (left_x, right_x, height_y) using SkylineSegment = std::tuple<int, int, int>; // 排样器类 class RectPacker { public: RectPacker(int sheetWidth, int sheetHeight); bool addRect(Rect& rect); // 尝试添加一个矩形，返回是否成功 void pack(std::vector<Rect>& rects); // 对一组矩形进行排样 double getUtilization() const; // 获取当前材料利用率 void visualize() const; // 简单控制台可视化（可选） private: int sheetWidth_, sheetHeight_; std::vector<SkylineSegment> skyline_; // 当前轮廓线 std::vector<Rect> packedRects_; // 已放置的矩形 int usedArea_; // 已使用面积 // 内部核心函数 std::vector<std::pair<int, int>> findValidPositions(const Rect& rect); int evaluatePosition(const SkylineSegment& seg, int placeX, const Rect& rect, int rule); void updateSkyline(int insertX, const Rect& rect); void sortRects(std::vector<Rect>& rects, const std::string& rule); }; #endif // RECT_PACKING_H

这里的关键是skyline_，它动态记录了板材的占用情况。findValidPositions函数会扫描skyline_，找出所有可以放置当前矩形的潜在X坐标（矩形的左边线位置）。

3.2 核心算法实现：放置与评估

让我们深入addRect这个最核心的函数。

// rect_packing.cpp (部分核心代码) bool RectPacker::addRect(Rect& rect) { if (skyline_.empty()) { // 第一个矩形，放在左下角(0,0) if (rect.width <= sheetWidth_ && rect.height <= sheetHeight_) { rect.x = 0; rect.y = 0; packedRects_.push_back(rect); usedArea_ += rect.width * rect.height; // 初始化轮廓线：矩形占据的区域 skyline_.push_back({0, rect.width, rect.height}); // 加上板材剩余顶部的线段 if (rect.width < sheetWidth_) { skyline_.push_back({rect.width, sheetWidth_, 0}); } return true; } // 尝试旋转 if (rect.height <= sheetWidth_ && rect.width <= sheetHeight_) { std::swap(rect.width, rect.height); rect.rotated = true; return addRect(rect); // 递归调用，此时skyline仍为空 } return false; } // 为当前矩形寻找所有可能的放置位置 auto candidatePositions = findValidPositions(rect); if (candidatePositions.empty()) { // 如果原方向找不到，尝试旋转矩形 std::swap(rect.width, rect.height); rect.rotated = !rect.rotated; candidatePositions = findValidPositions(rect); if (candidatePositions.empty()) { // 旋转后也放不下，恢复原状并返回失败 std::swap(rect.width, rect.height); rect.rotated = !rect.rotated; return false; } } // 评估所有候选位置，选择最佳（这里使用规则B：浪费面积最小） int bestScore = INT_MAX; SkylineSegment bestSeg; int bestX = -1; Rect bestRect = rect; // 记录最佳位置时的矩形状态（可能旋转过） for (const auto& pos : candidatePositions) { int placeX = pos.first; const SkylineSegment& seg = skyline_[pos.second]; int score = evaluatePosition(seg, placeX, rect, 2); // 规则2：浪费面积 if (score < bestScore) { bestScore = score; bestSeg = seg; bestX = placeX; bestRect = rect; // 当前rect可能已被旋转 } } // 放置最佳矩形 bestRect.x = bestX; bestRect.y = std::get<2>(bestSeg); // 放置在轮廓线段的高度上 packedRects_.push_back(bestRect); usedArea_ += bestRect.width * bestRect.height; // 更新轮廓线！这是算法正确性的关键 updateSkyline(bestX, bestRect); // 将成功放置的矩形信息写回原引用 rect = bestRect; return true; }

findValidPositions函数遍历轮廓线，找出所有宽度足够放置当前矩形的线段区间，并返回(放置X坐标, 线段索引)的列表。evaluatePosition函数则根据选定的规则计算在该位置放置的“代价”或“收益”。updateSkyline函数最为精细，它需要处理矩形覆盖线段时可能出现的分割、合并和提升操作。

3.3 轮廓线更新详解

updateSkyline是算法中最容易出错的部分。假设我们在轮廓线段(L, R, H)的X位置放置了一个宽W高H_rect的矩形。

1. 定位：找到skyline_中所有与区间[X, X+W)有交集的线段。
2. 分割与提升：
   • 对于完全被矩形覆盖的线段（L >= X && R <= X+W），将其高度提升至H + H_rect。
   • 对于部分被覆盖的线段（例如左端露出或右端露出），需要将其分裂成两段：未被覆盖的部分保持原高度，被覆盖的部分提升高度。
3. 合并：更新后，需要扫描skyline_，将相邻的、高度相同的线段合并为一条，以保持数据结构的简洁和高效。

这个过程的正确实现直接决定了排样结果的正确性和算法效率。一个健壮的实现需要仔细处理所有边界情况。

4. 高级优化策略与参数调优

基础算法跑通后，我们可以引入更高级的策略来进一步提升材料利用率。

4.1 多规则竞争与自适应选择

与其固定使用一种评估规则（如最小浪费面积），不如让多种规则“竞争”。我们可以为每个矩形，用不同的规则（如规则A、B、C）分别计算最佳放置位置，然后从这些规则产生的候选位置中，再选出一个全局最优的（例如，选择最终轮廓线最高点最低的那个位置）。这相当于一个简单的局部搜索，能有效跳出单一规则的局部最优。

// 在addRect函数内部的候选位置评估部分可以修改为： std::vector<std::tuple<int, int, int, Rect>> allCandidates; // (score, x, segIndex, rect) for (int rule = 1; rule <= 3; ++rule) { // 为每种规则找最佳位置（这里简化，实际需对每个规则运行findValidPositions和evaluate） // ... 计算得到 (bestScoreForRule, bestXForRule, bestSegForRule, bestRectForRule) allCandidates.emplace_back(bestScoreForRule, bestXForRule, bestSegForRule, bestRectForRule); } // 从allCandidates中选择最终胜出者（可以按score，也可以按放置后的预估轮廓线高度）

4.2 间隙填充与后处理优化

即使采用优秀算法，排样后仍可能产生一些小的空隙。我们可以增加一个“后处理”阶段：

1. 滑动：尝试将已放置的矩形在其局部空间内向左、向下移动，看是否能填补一些缝隙。
2. 交换：尝试交换两个已放置矩形的位置，看是否能改善整体布局。
3. 间隙填充：在主要排样结束后，专门用一个循环来处理那些之前因为尺寸稍大而未能放入的矩形，或者将大矩形分割后产生的小块，尝试填入剩余的空隙。这通常需要维护一个“空闲矩形”列表，并对其按面积降序进行填充。

4.3 排序规则的组合与搜索

矩形的放入顺序是影响结果的超级参数。我们可以不只用一种排序规则，而是尝试多种规则（面积降序、宽度降序、随机等），分别运行整个排样算法，然后选择利用率最高的那次结果。对于时间不敏感的场景，甚至可以结合元启发式算法（如遗传算法）来搜索更优的矩形序列。在遗传算法中，一个“染色体”就是矩形ID的一种排列顺序，适应度函数就是按此顺序用我们的排样器得到的材料利用率。

5. 性能考量与工程化实践

将算法用于实际生产，必须考虑性能和稳定性。

5.1 时间复杂度与优化

我们的基础算法，每次放置一个矩形，都需要扫描当前的轮廓线（平均长度为O(sqrt(N))）来寻找位置，并可能更新多条线段。因此，放置N个矩形的复杂度大致在O(N^1.5)量级。对于N<1000的情况，完全可以在毫秒到秒级完成。如果矩形数量上万，就需要考虑更高效的数据结构来管理轮廓线，例如使用区间树或线段树，可以将查找和更新操作优化到O(log N)。

5.2 内存与代码健壮性

• 输入验证：务必检查矩形尺寸是否大于板材尺寸，以及宽高是否为正值。
• 旋转策略：是否允许旋转？是90度旋转还是任意角度？我们的代码实现了90度旋转，这在木材、钣金切割中很常见。如果允许任意角度，问题将变得极其复杂（从矩形排样变为多边形排样）。
• 板材尺寸：我们的实现假设板材是固定尺寸的。可以扩展为支持多张板材，当一张板放不下时，自动启用新板。
• 切割工艺约束：实际切割中，刀具是有直径的，矩形之间需要预留“切割缝”（kerf）。这很容易实现，在判断矩形是否可放置和计算轮廓线时，将每个矩形的实际占用区域在四周都加上缝宽的一半即可。
• 可视化与调试：实现一个简单的ASCII字符或SVG图形输出函数visualize()，对于调试算法逻辑、向非技术人员展示结果至关重要。

5.3 集成到生产流程

一个完整的排样系统通常包括以下模块：

1. 数据接口：从CAD文件（如DXF）、ERP系统或简单CSV中读取零件清单和板材信息。
2. 排样核心：即我们上面实现的C++算法库。
3. 结果输出：生成包含每个零件坐标、旋转状态的报告文件，以及供数控切割机使用的G代码或NC代码。
4. 用户界面：提供图形化界面，允许用户调整参数（如是否旋转、排序规则）、手动微调布局、查看利用率报告。

6. 常见问题与实战排坑指南

在实际开发和项目落地中，我遇到了不少典型问题，这里分享给大家。

6.1 算法逻辑类问题

问题1：矩形被放置到已有矩形内部，发生重叠。

• 排查：99%的原因是updateSkyline函数逻辑有bug。重点检查当新矩形覆盖多个轮廓线段时，对线段的分割、删除和新增逻辑是否正确。特别是线段交界处的处理。
• 调试技巧：编写一个checkOverlap()函数，在所有矩形放置后，两两检查是否有重叠。一旦发现重叠，立即打印出错误时的板材状态、轮廓线和相关矩形信息，并配合可视化，能快速定位bug。

问题2：材料利用率不稳定，有时很高，有时很低。

• 排查：首先确认矩形的放入顺序是否固定。如果使用了随机数，请确保种子固定以便复现。然后检查评估函数evaluatePosition，不同的规则对结果影响很大。
• 解决：采用“多规则竞争+多排序规则尝试”的策略。运行算法多次（例如，尝试5种排序规则），取最佳结果。对于关键生产任务，这是值得的。

问题3：允许旋转后，结果反而变差了。

• 排查：检查旋转逻辑。是在寻找位置之前就尝试旋转，还是在原方向找不到位置后才旋转？前者是“主动旋转”，搜索空间更大；后者是“被动旋转”，可能错过一些机会。
• 建议：实现两种策略。对于每个矩形，先以其原始方向寻找最佳位置并评分，再以旋转后的方向寻找最佳位置并评分，最后选择两个方向中评分更好的那个进行放置。这虽然增加了计算量，但效果更好。

6.2 工程实践类问题

问题4：处理大量矩形（如>5000个）时程序运行缓慢。

• 优化：
  1. 轮廓线数据结构：将std::vector<SkylineSegment>替换为更高效的结构，如std::list（便于中间插入删除）或自定义的区间树。
  2. 评估函数简化：如果使用复杂的评估函数，考虑能否用近似计算或查找表替代。
  3. 并行化：如果采用“多排序规则尝试”策略，每次尝试都是独立的，可以很容易地用多线程并行执行。
  4. 提前终止：当轮廓线高度已经超过板材高度，且剩余未放矩形面积之和大于剩余空白区域面积时，可以提前判定当前排序规则无法得到更好解，直接终止。

问题5：生成的切割路径（G代码）效率低。

• 说明：排样优化了材料，但切割路径优化了时间。两者有时目标冲突。
• 建议：在排样评估函数中，可以加入一个简单的路径代价估计项。例如，优先选择放置后距离上一个切割完的矩形较近的位置（模拟“切割头移动距离最短”）。这需要将排样问题与旅行商问题（TSP）进行一定程度的结合，更为复杂，但对于激光切割等移动时间占主导的工艺非常有效。

问题6：如何应对异形件（非矩形）？

• 方案：这是矩形排样的自然延伸。常用方法是：
  1. 包络矩形：用最小的外接矩形来近似异形件。简单但浪费材料。
  2. 嵌套排样：这是更专业的领域。需要将异形件多边形化，采用“靠接”算法（如No-Fit Polygon, NFP）来判断两个多边形是否重叠以及最佳靠接位置。这完全是一个新的、更复杂的算法领域，通常需要专门的商业软件。

最后，我个人的体会是，矩形排样是一个将优美算法与现实约束相结合的绝佳领域。从最初一个简单的vector和循环，到后来引入复杂的数据结构和启发式规则，每一次优化带来的利用率提升，都对应着真金白银的材料节省。这套C++代码框架是一个坚实的起点，你可以根据自己行业的具体特点（如必须考虑纹理方向、需要共边切割等）对其进行定制和强化。记住，没有“放之四海而皆准”的最优参数，最好的参数永远来自于对你自身生产数据的反复测试和调优。