鸭梨公共文档

主题

Nesting Problem | 二维排样问题 ​

1. 概述 ​

二维排样问题（2D Nesting Problem）是计算几何和组合优化领域的经典难题，也被称为下料问题（Cutting Stock Problem）或装箱问题（Bin Packing Problem）。该问题的核心是如何在给定的容器（如矩形面板、布料、钢板等）中高效地放置一组不规则形状的物品，使得材料利用率最大化，废料最小化。

在工业制造中，二维排样问题广泛应用于：

  • 纺织行业：服装裁片在布料上的排版
  • 钣金加工：零件在金属板材上的排样
  • 激光切割：复杂形状在材料上的优化布局
  • 木材加工：家具部件的下料优化
  • 包装行业：产品包装的空间优化

由于不规则形状的几何复杂性和组合爆炸问题，二维排样属于 NP-Hard 问题，难以在多项式时间内求得最优解。因此，实际应用中主要采用启发式算法和智能优化算法来寻求近似最优解。

2. 形状与工艺维度的分类（补充） ​

从形状与工艺约束两个维度看，常见分类如下：

  • 形状类型：
    • 规则形状排样：全部为矩形/圆等规则件
    • 不规则形状排样：任意多边形（含凹多边形、带孔）
    • 混合形状排样：规则与不规则混合
  • 工艺约束：
    • 旋转自由度：连续旋转或离散角度（如每1°/5°/15°/90°），是否允许镜像
    • 刀缝/间隙：通常对零件外扩（offset）一定距离以满足切割间隙
    • 切割受限：是否要求断头切割（Guillotine）、板上禁放区/缺陷避让
    • 材料特性：纹理/经纬方向、最小距边、批次分组等

3. 问题定义与数学描述 ​

3.1 基本定义 ​

二维排样问题可以数学化描述为：给定一组不规则多边形 P={P1,P2,…,Pn}P = \{P_1, P_2, \ldots, P_n\} 和一个或多个容器 CC，寻找每个多边形的位置和旋转角度，使得：

  1. 无重叠约束：任意两个多边形不能相互重叠
  2. 包含约束：所有多边形必须完全包含在容器内部
  3. 目标函数：最大化材料利用率或最小化容器使用数量

3.2 问题分类 ​

根据容器类型和优化目标，二维排样问题可分为以下几类：

3.2.1 二维决策问题（2D Decision Problem） ​

给定一组不规则多边形和一个固定容器，判断是否能够将所有多边形都放置在容器内。

3.2.2 二维背包问题（2D Knapsack Problem） ​

给定一组带权重的不规则多边形和一个固定容器，选择多边形子集放入容器，使得总价值最大化。

3.2.3 二维装箱问题（2D Bin Packing Problem） ​

给定一组不规则多边形和无限个相同的容器，使用最少的容器装下所有多边形。

3.2.4 二维条带填充问题（2D Strip Packing Problem） ​

给定一组不规则多边形和一个宽度固定、长度无限的条带容器，最小化所使用的条带长度。

4. 关键技术挑战 ​

4.1 几何计算复杂性 ​

  • 重叠检测：判断两个不规则多边形是否重叠
  • 靠接计算：确定多边形间的最优相对位置
  • 包含判断：验证多边形是否完全在容器内部

4.2 组合优化难度 ​

  • 搜索空间巨大：nn 个物品的排列组合为 n!n!
  • 连续优化：每个物品的位置和旋转角度都是连续变量
  • 约束处理：需要同时满足几何约束和优化目标

4.3 算法性能要求 ​

  • 实时性：工业应用需要在合理时间内给出解决方案
  • 鲁棒性：算法需要处理各种复杂几何形状
  • 可扩展性：能够处理大规模问题实例

5. 主流算法路线（工程视角，补充） ​

结合工业实践，较为通用的路线包括：

  • 精确建模（ILP/CP）：对矩形或简化模型有效，小规模可取；对异形件+连续旋转往往不可行。
  • NFP 停靠 + 序列优化（主流）：用 No-Fit Polygon 将候选放置位置限制在有限边界点/弧上，再用启发式（如最左最低/最小新增包络）择优；放置顺序与角度由 GA/SA/禁忌搜索等做全局搜索。
  • 栅格/位图方法：将板材离散为网格或距离场，快速碰撞与“下落/充填”；适合实时性强、精度适中场景。
  • 切割受限族（Guillotine/Shelf/Skyline/MaxRects）：若工艺必须断头或仅矩形件，采用这些高效算法；异形件可先用外接矩形/OBB/凸分解近似。
  • 分解与局部细化：凹多边形凸分解或片段化，先粗排（如按外接矩形/宽高比），再用 NFP 微移/旋转微调压缩空隙。

工程要点：NFP/Minkowski 与偏置运算的健壮实现（Clipper/CGAL 等），NFP 缓存与旋转预计算，R-tree 等空间索引加速碰撞检测。

6. 核心几何算法 ​

6.1 No-Fit Polygon（NFP）算法 ​

No-Fit Polygon（临界多边形，NFP）是二维排样问题中最重要的几何工具之一。NFP 定义了两个多边形之间的相对位置关系，是实现高效重叠检测和靠接计算的关键。

6.1.1 NFP 基本概念 ​

给定两个多边形 A（固定多边形）和 B（移动多边形），NFP 是这样一个区域：当多边形 B 的参考点位于 NFP 内部时，A 和 B 发生重叠；当参考点位于 NFP 边界上时，A 和 B 相切但不重叠；当参考点位于 NFP 外部时，A 和 B 分离。

6.1.2 NFP 计算方法 ​

方法一：凸化分解法 ​

  • 将凹多边形分解为若干凸多边形
  • 分别计算凸多边形间的NFP
  • 通过布尔运算合并得到最终NFP
  • 时间复杂度：O(n3)O(n^3)，其中 nn 为多边形顶点数

方法二：移动碰撞法（Sliding Algorithm） ​

  • 让移动多边形 B 沿着固定多边形 A 的边界滑动
  • 记录 B 的参考点轨迹形成 NFP
  • 能处理空腔 NFP 和退化情况
  • 时间复杂度：O((m+n)mn)O((m+n)mn)

方法三：Minkowski 矢量和法 ​

  • 基于 Minkowski 和的数学理论
  • 适用于凸多边形，凹多边形需要特殊处理
  • 使用坡度图解决凹多边形问题
  • 时间复杂度：O(m2n2log⁡(mn))O(m^2 n^2 \log(mn))

方法四：轨迹线法 ​

  • 计算每个顶点相对于另一多边形的轨迹线
  • 从轨迹线集合中提取外围多边形
  • 算法简单，能处理特殊情况
  • 平均时间复杂度：O(mn)O(mn)

6.1.3 NFP 特殊情况 ​

  1. 空腔 NFP：当一个多边形可以部分嵌入另一个多边形的凹槽中
  2. 线性NFP：NFP退化为直线
  3. 点NFP：NFP退化为单点

6.2 Phi-Function 方法 ​

Phi-Function 是另一种处理多边形重叠关系的数学工具，特别适用于将几何约束转化为数学约束。

对于两个多边形 PiP_i 和 PjP_j，Phi-Function 定义为：

  • Φ(Pi,Pj)>0\Phi(P_i, P_j) > 0：多边形分离
  • Φ(Pi,Pj)=0\Phi(P_i, P_j) = 0：多边形相切
  • Φ(Pi,Pj)<0\Phi(P_i, P_j) < 0：多边形重叠

Phi-Function 的优势在于可以将几何问题转化为非线性规划问题，便于使用数学优化方法求解。

6.3 快速重叠检测 ​

层次包围盒法 ​

  1. 粗检测：使用轴对齐包围盒（AABB）进行初步筛选
  2. 精检测：使用方向包围盒（OBB）或凸包进行精确检测
  3. 最终检测：使用精确的多边形重叠算法

分离轴定理（SAT） ​

对于凸多边形，可以使用分离轴定理快速判断是否重叠：

  • 在所有可能的分离轴上投影两个多边形
  • 如果存在某个轴使得投影不重叠，则多边形分离
  • 时间复杂度：O(m+n)O(m+n)

6.4 位图方法 ​

将连续的几何区域离散化为网格：

  • 优点：算法简单，易于实现并行计算
  • 缺点：精度受网格分辨率限制，内存消耗大
  • 应用：适用于实时性要求高但精度要求不严格的场景

7. 典型工程流程（补充） ​

  1. 输入解析：读取 DXF/SVG/多段线，统一单位与精度，修复拓扑（方向、孔、重复点、裂缝）。
  2. 工艺处理：按刀缝/间隙对零件外扩，设定离散旋转角度集合与是否允许镜像；标注禁放区/缺陷区。
  3. 预计算：为各角度生成零件轮廓；按对儿计算 / 缓存 NFP 或 Minkowski 和；建立 R-tree 等空间索引。
  4. 排序与放置：用 GA / SA / TS / 超启发式搜索件序与角度；逐件用 NFP 停靠生成候选点，按评分（最小新增包络、最左最低、路径友好等）择优。
  5. 评价与迭代：材料利用率、是否越界/重叠、拼版张数、切割路径长度/抬刀次数等；至时限或收敛。
  6. 导出：输出排样图与刀路（可进一步做引线/桥接/分区切割等后处理）。

8. 语言生态与库选型（补充） ​

  • C/C++：
    • libnest2d（C++17，LGPL）：完整异形件 nesting 框架，NFP 停靠、离散旋转、间隙等均支持；可配合 Clipper/CGAL。
    • Clipper/Clipper2（BSL）：稳健的多边形布尔/偏置/MinkowskiSum 基元；适合作为几何内核。
    • CGAL：高精度计算几何集合（含 Minkowski 和等），需留意模块许可（GPL/LGPL/商用）。
  • Rust：
    • 现成完整引擎较少；可通过 FFI 绑定 libnest2d，或组合 geo/geo-booleanop/GEOS 绑定 + rstar 空间索引 + Clipper 封装自研。
    • 矩形场景可考虑 guillotiere（不适用于异形件本体）。
  • Python：
    • pynest2d：libnest2d 的 Python 绑定，快速获得可用能力。
    • shapely（GEOS）+ pyclipper：构建布尔/偏置/NFP 基础，灵活自研启发式；配合 svgpathtools/ezdxf 处理 SVG/DXF。
    • rectpack：矩形装箱（非异形件）。
  • Node.js / 浏览器：
    • SVGNest / Deepnest：NFP 停靠 + GA 的经典实现，适合 Web / 可视化原型；注意 GPL 许可与闭源兼容性。
    • polygon-clipping、martinez-polygon-clipping、clipper-lib：多边形布尔 / 偏置基础。

许可合规提示：GPL / AGPL 类项目对闭源商用有强约束；libnest2d 的 LGPL 边界较易合规（动态链接等）；Clipper 为宽松的 BSL 许可。

9. 算法选择与实施建议（补充） ​

  • 规模导向：
    • 小规模（< 50 件）：可尝试精确法/严格的 NFP + 局部搜索，亦可用 GA/SA 获得高质量解。
    • 中等规模（50–500 件）：启发式 + 元启发式（如 NFP 停靠 + GA/SA/TS），设置合理时间预算。
    • 大规模（> 500 件）：高效启发式/栅格近似 + 局部细化，重视缓存与并行。
  • 性能要点：
    • 旋转角度离散化（质量-性能关键权衡），常见 1°/5°/15° 取样；必要时允许镜像。
    • 对零件按面积/凸度/细长比排序以先放“大难件”。
    • NFP / Minkowski 结果缓存、空间索引、并行（多核 / GPU）显著提速。
  • 工艺与可制造性：
    • 外扩（offset）满足刀缝/间隙；最小距边与缺陷避让；纹理/经纬对齐。
    • 切割路径友好：减少抬刀、缩短空程、控制热影响区；必要时将“路径长度/热负载”纳入评分函数。
    • 结果验证：人工抽检关键区域，必要时做加工仿真与回传修正。

10. 研究进展与趋势（补充） ​

  • 机器学习辅助：
    • 深度学习用于位置/评分预测，强化学习学习排样策略；元学习用于跨实例迁移。
  • 多目标优化：
    • 从单一利用率转向帕累托前沿（材料利用率、加工时间、能耗、刀具磨损、热影响等）。
  • 云与实时化：
    • 云端排样服务、在线优化、与 ERP/MES 集成；面对小批量多品种的动态排样与快速重排。

11. 优化算法与求解策略 ​

11.1 构造型启发式算法 ​

11.1.1 左底部排样算法（Bottom-Left Fill） ​

左底部排样是最经典的构造型启发式算法：

  1. 基本思路：按照预定顺序逐个放置多边形，每个多边形尽可能放在左下角位置
  2. 放置规则：
    • 首先尽可能向左移动
    • 在不能再向左的前提下，尽可能向下移动
    • 确保不与已放置的多边形重叠
  3. 时间复杂度：O(n2)O(n^2)，其中 nn 为多边形数量
  4. 优势：简单快速，适合作为其他算法的初始解生成器

11.1.2 No-Fit Polygon 置放算法 ​

基于NFP的构造算法：

  1. 计算NFP：为待放置多边形计算相对于所有已放置多边形的NFP
  2. 求交集：计算所有NFP的交集，得到可行放置区域
  3. 选择位置：在可行区域内选择最优位置（如最左下角）
  4. 优势：精确处理几何约束，避免重叠

11.2 元启发式算法 ​

11.2.1 遗传算法（Genetic Algorithm） ​

编码方案：

  • 序列编码：多边形的放置顺序
  • 位置编码：每个多边形的具体位置和旋转角度
  • 混合编码：结合序列和位置信息

遗传操作：

  • 选择：锦标赛选择、轮盘选择
  • 交叉：顺序交叉（OX）、部分映射交叉（PMX）
  • 变异：位置变异、角度变异、序列变异

适应度函数：

f=α×利用率−β×重叠面积−γ×边界违反f = \alpha \times \text{利用率} - \beta \times \text{重叠面积} - \gamma \times \text{边界违反}

11.2.2 模拟退火算法（Simulated Annealing） ​

算法框架：

  1. 生成初始解
  2. 在当前解的邻域内随机生成新解
  3. 根据 Metropolis 准则决定是否接受新解
  4. 逐步降低温度，减少接受较差解的概率

邻域操作：

  • 序列邻域：交换两个多边形的放置顺序
  • 位置邻域：微调多边形的位置
  • 旋转邻域：改变多边形的旋转角度

冷却策略：

  • 线性冷却：T(k)=T0−k×ΔTT(k) = T_0 - k \times \Delta T
  • 指数冷却：T(k)=T0×αkT(k) = T_0 \times \alpha^k
  • 对数冷却：T(k)=T0log⁡(1+k)T(k) = \dfrac{T_0}{\log(1 + k)}

11.2.3 粒子群优化（Particle Swarm Optimization） ​

粒子表示：每个粒子代表一个排样方案 速度更新：

vi=w×vi+c1×r1×(pbesti−xi)+c2×r2×(gbest−xi)v_i = w \times v_i + c_1 \times r_1 \times (pbest_i - x_i) + c_2 \times r_2 \times (gbest - x_i)

位置更新：

xi=xi+vix_i = x_i + v_i

11.2.4 蚁群优化（Ant Colony Optimization） ​

信息素模型：在多边形序列的边上设置信息素 概率选择：根据信息素浓度和启发式信息选择下一个多边形 信息素更新：根据解的质量更新路径上的信息素

11.3 局部搜索算法 ​

11.3.1 压缩算法（Compaction） ​

水平压缩：

  1. 从右到左逐个移动多边形
  2. 每个多边形尽可能向左移动
  3. 确保不产生重叠

垂直压缩：

  1. 从上到下逐个移动多边形
  2. 每个多边形尽可能向下移动
  3. 更新容器的有效高度

11.3.2 分离算法（Separation） ​

当存在重叠时，通过最小移动距离分离重叠的多边形：

  1. 计算重叠多边形的最小分离向量
  2. 沿分离向量移动其中一个多边形
  3. 重复直到消除所有重叠

11.3.3 快速局部搜索 ​

Beam Search：

  • 在每一步保持k个最优的部分解
  • 扩展所有部分解，选择最优的k个继续
  • 平衡了搜索质量和计算效率

引导式局部搜索：

  • 使用参数化的目标函数避免局部最优
  • 动态调整搜索方向和强度
  • 适用于大规模问题实例

11.4 混合算法 ​

11.4.1 多阶段算法 ​

  1. 初始化阶段：使用构造型算法生成初始解
  2. 改进阶段：使用元启发式算法优化解质量
  3. 局部优化阶段：使用局部搜索算法精细调整

11.4.2 协作进化算法 ​

  • 分解策略：将大问题分解为多个子问题
  • 协作机制：子问题之间通过信息交换协作求解
  • 集成策略：将子问题的解合并为完整解

11.5 现代深度学习方法 ​

11.5.1 强化学习方法 ​

环境建模：

  • 状态：当前排样状态（已放置的多边形配置）
  • 动作：选择下一个要放置的多边形及其位置
  • 奖励：基于材料利用率和约束违反的奖励函数

算法框架：

  • Deep Q-Network（DQN）
  • Policy Gradient Methods
  • Actor-Critic Methods

11.5.2 图神经网络 ​

图表示：

  • 节点：多边形
  • 边：多边形间的空间关系
  • 特征：几何属性、位置信息

应用场景：

  • 多边形序列优化
  • 位置预测
  • 约束处理

12. 工业应用案例 ​

纺织服装行业 ​

应用背景（纺织服装） ​

纺织行业是二维排样技术的最早应用领域之一。服装制造中需要将各种复杂形状的裁片（如袖子、领子、衣身等）高效地排列在布料上，以最大化材料利用率。

技术特点（纺织服装） ​

  • 材料特性：布料具有纹理方向，某些裁片需要按特定方向放置
  • 质量要求：缺陷区域需要避开，布料边缘可能不规整
  • 批量生产：需要同时处理多个尺码的相同款式

算法应用 ​

  • 约束处理：考虑纹理方向约束的NFP计算
  • 多层排样：同时在多层布料上进行排样
  • 实时优化：支持快速修改和重新排样

效果评估 ​

  • 材料利用率：从传统手工排样的75-80%提升到85-90%
  • 排样时间：从几小时缩短到几分钟
  • 人力成本：减少专业排样师的依赖

钣金加工行业 ​

应用背景（钣金加工） ​

钣金加工需要将各种形状的零件排列在金属板材上进行激光切割、等离子切割或冲压加工。

技术挑战 ​

  • 切割路径优化：最小化切割路径总长度
  • 热变形控制：避免局部过热导致的材料变形
  • 工艺约束：考虑切割顺序、桥接等工艺要求

解决方案 ​

text
算法流程：
1. 几何预处理：去除毛刺、合并重复轮廓
2. 约束排样：考虑最小间距、切割方向等约束
3. 路径规划：优化切割顺序和路径
4. 后处理：添加引线、桥接等工艺元素

实际效果 ​

  • 材料节约：钢板利用率提升5-15%
  • 加工效率：切割时间减少20-30%
  • 质量提升：减少热变形和切割缺陷

激光切割行业 ​

技术特点（激光切割） ​

  • 高精度要求：激光切割精度可达±0.1mm
  • 速度优化：切割头移动路径直接影响加工效率
  • 能耗控制：减少空程移动距离

智能排样系统 ​

现代激光切割设备集成的智能排样系统通常包括：

  1. 自动导入：从CAD系统直接导入零件几何
  2. 智能排样：基于遗传算法或模拟退火的自动排样
  3. 路径优化：最短路径问题的近似求解
  4. 实时监控：排样过程的可视化展示

案例分析：汽车零部件制造 ​

某汽车零部件制造商采用先进的排样系统：

  • 处理能力：单次可处理100+个不同零件
  • 排样时间：大型排样任务2-5分钟完成
  • 材料利用率：从82%提升到89%
  • 年节约成本：材料成本降低约200万元

木材家具行业 ​

行业特点 ​

  • 原材料昂贵：实木板材成本高，浪费损失大
  • 形状复杂：家具部件形状不规则，嵌套困难
  • 批量小：个性化定制需求增加

技术应用 ​

  • 木材缺陷检测：结合机器视觉识别木材缺陷区域
  • 纹理匹配：考虑木纹方向和颜色匹配
  • 边料利用：小零件优先使用边角料

经济效益 ​

某家具制造企业实施智能排样后：

  • 材料利用率：从70%提升到83%
  • 设计效率：新产品排样时间从2天缩短到2小时
  • 库存优化：边角料利用率提升40%

包装行业 ​

应用场景 ​

  • 产品包装：最大化包装箱空间利用
  • 物流运输：优化货物在运输容器中的排列
  • 仓储管理：提高仓库空间利用率

技术创新 ​

  • 3D扩展：从2D排样扩展到3D装箱
  • 动态调整：根据实时订单调整排样方案
  • 多目标优化：平衡空间利用率和操作便利性

新兴应用领域 ​

3D打印行业 ​

  • 构建平台优化：最大化单次打印的零件数量
  • 支撑结构优化：减少支撑材料的使用
  • 打印时间优化：通过合理排列减少打印时间

电子制造业 ​

  • PCB板设计：元器件在电路板上的最优排列
  • 芯片封装：最大化芯片在晶圆上的利用率
  • 散热优化：考虑热分布的元器件排列

建筑行业 ​

  • 预制构件：混凝土预制板的优化排样
  • 玻璃幕墙：异形玻璃在原板上的排样
  • 装饰材料：石材、瓷砖等的切割优化

性能评估与比较 ​

评估指标 ​

主要指标 ​

  1. 材料利用率：η = (零件总面积/容器面积) × 100%
  2. 算法运行时间：从输入到输出结果的总时间
  3. 解的质量：与已知最优解或上界的比较

辅助指标 ​

  1. 收敛速度：达到目标质量所需的迭代次数
  2. 稳定性：多次运行结果的一致性
  3. 可扩展性：处理大规模问题的能力

标准测试集 ​

学术测试集 ​

  • Albano数据集：经典的不规则形状测试实例
  • Dagli数据集：包含复杂凹多边形的挑战性实例
  • Marques数据集：工业应用中的真实案例

工业测试集 ​

  • 纺织行业：真实服装裁片数据
  • 钣金行业：机械零件几何数据
  • 家具行业：实木家具部件数据

算法比较 ​

算法类型材料利用率计算时间实现难度适用场景
左底部排样60-75%秒级简单快速预排样
遗传算法80-90%分钟级中等离线优化
模拟退火85-92%分钟级中等高质量要求
NFP+局部搜索88-95%分钟级复杂工业应用
深度学习85-93%秒级*复杂实时应用

*需要预训练时间

开源项目与工具 ​

主要开源项目 ​

SVGnest ​

  • 项目地址：https://github.com/Jack000/SVGnest
  • 开发语言：JavaScript/Node.js
  • 技术特点：
    • 基于Web的可视化界面
    • 支持SVG格式的几何图形
    • 实现了NFP算法和遗传算法优化
    • 支持多种旋转角度设置
  • 应用场景：
    • 激光切割
    • 原型制作
    • 小批量生产
  • 优势：易于使用，跨平台，可视化效果好
  • 局限性：大规模问题性能有限，算法相对简单

许可证提示：SVGnest/Deepnest 多为 GPL-3.0，闭源集成需谨慎评估合规策略。

Sparrow 🪶 ​

  • 项目地址：https://github.com/JeroenGar/sparrow
  • 开发语言：Rust
  • 技术特点：
    • 最先进的二维不规则条带装箱算法
    • 基于jagua-rs碰撞检测引擎
    • 双阶段优化：探索阶段 + 压缩阶段
    • 支持实时可视化监控
  • 性能表现：
    • 在标准测试集上达到业界领先水平
    • 支持SIMD指令集优化
    • 内存效率高，适合大规模问题
  • 学术背景：由KU Leuven大学开发，有严格的理论基础
  • 适用场景：
    • 工业级应用
    • 研究和算法比较
    • 高性能要求的场景

libnest2d ​

  • 项目地址：https://github.com/tamasmeszaros/libnest2d
  • 开发语言：C++
  • 技术特点：
    • 模块化设计，支持多种几何库
    • 支持Clipper和CGAL几何引擎
    • 提供多种排样策略
    • 良好的API设计，易于集成
  • 优势：
    • 高性能的C++实现
    • 灵活的架构设计
    • 适合嵌入到其他应用中
  • 应用实例：
    • PrusaSlicer 3D打印切片软件
    • 多个CAD/CAM软件

Deepnest ​

  • 项目地址：https://github.com/Jack000/Deepnest
  • 开发语言：JavaScript/TypeScript（Electron 桌面应用）
  • 技术特点：NFP 停靠 + 元启发式；桌面可视化，适合学习/对比。
  • 许可：GPL-3.0（注意闭源合规）。

pynest2d / Python 生态补充 ​

  • pynest2d：libnest2d 的 Python 绑定，便于快速接入与流程验证。
  • shapely + pyclipper：稳健布尔/偏置/NFP 组合；配合 svgpathtools/ezdxf 做数据读写。

2D-Bin-Packing ​

  • 项目地址：https://github.com/mses-bly/2D-Bin-Packing
  • 开发语言：Python
  • 技术特点：
    • 多种装箱算法实现
    • 支持底线填充算法（Bottom-Left Fill）
    • 支持最佳适应算法（Best Fit）
    • 可视化展示结果
  • 适用场景：
    • 教学和研究
    • 算法原型验证
    • 简单应用集成

Packaide ​

  • 项目地址：https://github.com/DanielLiamAnderson/Packaide
  • 开发语言：C++
  • 技术特点：
    • 快速且鲁棒的2D排样算法
    • 支持多种文件格式
    • 命令行工具，适合批处理
    • 跨平台支持
  • 特色功能：
    • 支持复杂的凹多边形
    • 高效的NFP计算
    • 优化的内存使用

nest2D ​

专业商业软件 ​

TruNest (Trumpf) ​

  • 应用领域：钣金加工、激光切割
  • 核心技术：
    • 先进的NFP算法
    • 多层排样
    • 切割路径优化
    • 材料库管理

SigmaNest ​

  • 应用领域：工业切割和制造
  • 特色功能：
    • CAD集成
    • 生产调度
    • 材料追踪
    • 成本分析

OptiNest ​

  • 应用领域：纺织、家具、包装
  • 技术优势：
    • 高材料利用率
    • 快速排样
    • 批量处理
    • 自动化集成

算法库和框架 ​

CGAL (Computational Geometry Algorithms Library) ​

  • 项目地址：https://www.cgal.org/
  • 开发语言：C++
  • 相关功能：
    • 多边形布尔运算
    • Minkowski和计算
    • 凸包算法
    • 点在多边形内判断

Clipper Library ​

Boost.Geometry ​

开发工具和辅助软件 ​

几何数据生成器 ​

  • 2DCPackGen：生成标准测试实例
  • Random Polygon Generator：生成随机多边形
  • Industrial Data Converter：转换工业CAD数据

可视化工具（开发与调试） ​

  • SVG Viewer：查看和编辑SVG格式的排样结果
  • OpenGL Renderer：实时3D可视化
  • Web-based Viewer：基于浏览器的在线查看器

性能分析工具 ​

  • Profiler Integration：集成性能分析工具
  • Benchmark Suite：标准性能测试套件
  • Memory Analyzer：内存使用分析

选择指南 ​

研究和学习 ​

推荐：SVGnest, 2D-Bin-Packing 原因：代码清晰，文档完善，易于理解和修改

高性能应用 ​

推荐：Sparrow, libnest2d 原因：算法先进，性能优秀，适合大规模问题

快速原型开发 ​

推荐：nest2D, Packaide 原因：API友好，集成简单，开发效率高

工业应用 ​

推荐：libnest2d + 商业软件 原因：稳定可靠，技术支持完善，功能全面

项目对比分析 ​

项目语言性能易用性文档质量社区活跃度适用场景
SVGnestJS中高好高原型、教学
SparrowRust极高中优秀中研究、工业
libnest2dC++高中好中嵌入式应用
2D-Bin-PackingPython低高一般低学习、验证
PackaideC++高中一般低命令行工具
nest2DKotlin中高一般低Android应用

参考文献 ​

学术论文 ​

经典综述文献 ​

  1. Bennell, J. A., & Oliveira, J. F. (2008). The geometry of nesting problems: A tutorial. European Journal of Operational Research, 184(2), 397-415.

    • 二维排样几何问题的权威教程

  2. Wäscher, G., Haußner, H., & Schumann, H. (2007). An improved typology of cutting and packing problems. European Journal of Operational Research, 183(3), 1109-1130.

    • 切割装箱问题分类的标准参考

  3. Hopper, E., & Turton, B. C. (2001). An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem. European Journal of Operational Research, 128(1), 34-57.

    • 二维装箱元启发式算法的实证研究

NFP算法相关 ​

  1. Adamowicz, M., & Albano, A. (1976). Nesting two-dimensional shapes in rectangular modules. Computer-Aided Design, 8(1), 27-33.

    • NFP概念的最早提出

  2. Burke, E. K., Hellier, R. S. R., Kendall, G., & Whitwell, G. (2007). Complete and robust no-fit polygon generation for the irregular stock cutting problem. European Journal of Operational Research, 179(1), 27-49.

    • 移动碰撞法NFP算法

  3. Bennell, J. A., & Song, X. (2008). A comprehensive and robust procedure for obtaining the nofit polygon using Minkowski sums. Computers & Operations Research, 35(1), 267-281.

    • Minkowski和法NFP算法

  4. Li, H, Huang, Y., & Bennell, J. A. (2009). The irregular nesting problem: a new approach for nofit polygon calculation. Annals of Operations Research, 179(1), 235-252.

    • 轨迹线法NFP算法

优化算法研究 ​

  1. Gomes, A. M., & Oliveira, J. F. (2006). Solving irregular strip packing problems by hybridising simulated annealing and linear programming. European Journal of Operational Research, 171(3), 811-829.

    • 混合算法在条带装箱中的应用

  2. Egeblad, J., Nielsen, B. K., & Odgaard, A. (2007). Fast neighborhood search for two-and three-dimensional nesting problems. European Journal of Operational Research, 183(3), 1249-1266.

    • 快速邻域搜索算法

  3. López-Camacho, E., Terashima-Marín, H., Ross, P., & Valenzuela-Rendón, M. (2013). A unified hyper-heuristic framework for solving bin packing problems. Expert Systems with Applications, 41(15), 6876-6889.

    • 超启发式框架在装箱问题中的应用

最新研究进展 ​

  1. Cherri, L. H., Mundim, L. R., Andretta, M., Toledo, F. M., Oliveira, J. F., & Carravilla, M. A. (2014). Robust mixed-integer linear programming models for the irregular strip packing problem. European Journal of Operational Research, 253(3), 570-583.

    • 混合整数线性规划模型

  2. Zhao, X., Bennell, J. A., Bektaş, T., & Dowsland, K. (2006). A comparative review of 3D container loading algorithms. International Transactions in Operational Research, 23(1-2), 287-320.

    • 三维装箱算法比较研究

  3. Stoyan, Y., Pankratov, A., & Romanova, T. (2016). Cutting and packing problems for irregular objects with continuous rotations: mathematical modelling and non-linear optimization. Journal of the Operational Research Society, 67(5), 786-800.

    • 连续旋转下的非线性优化模型

技术报告与博客 ​

中文技术资源 ​

  • 二维异形件排版算法介绍（一） - 华为云社区

  • 排料问题详解 - zYx.Tom的个人博客

英文技术资源 ​

  • Nesting Optimization Guide - Industrial Engineering Resources
  • 2D Packing Algorithms Handbook - Computational Geometry Portal

开源项目文档 ​

主要开源实现 ​

  1. SVGnest - JavaScript实现的Web排样工具

  2. Sparrow - Rust实现的高性能排样引擎

  3. libnest2d - C++模块化排样库

  4. 2D-Bin-Packing - Python教学实现

  5. Packaide - 快速鲁棒的C++实现

  6. nest2D - Kotlin/Java现代实现

几何算法库 ​

标准测试数据集 ​

学术基准测试集 ​

  • ESICUP - 欧洲切割装箱特别兴趣小组测试数据
  • OR-Library - 运筹学问题标准测试库
  • 2DCPackGen - 二维装箱问题生成器

工业数据集 ​

  • 纺织行业数据集 - 真实服装裁片几何数据
  • 钣金加工数据集 - 机械零件CAD数据
  • 家具制造数据集 - 实木家具部件数据

商业软件参考 ​

专业排样软件 ​

  • TruNest (Trumpf) - 钣金激光切割排样
  • SigmaNest - 工业切割制造解决方案
  • OptiNest - 纺织家具包装排样
  • NestFab - CAD/CAM集成排样
  • ProNest - Hypertherm等离子切割排样

CAD/CAM集成 ​

  • Autodesk Inventor Nesting - CAD集成排样功能
  • SolidWorks Composer - 产品设计排样工具
  • Rhino Grasshopper - 参数化设计排样插件

会议与期刊 ​

主要学术会议 ​

  • ESICUP Workshop - 欧洲切割装箱研讨会
  • IFORS Conference - 国际运筹学大会
  • EURO Conference - 欧洲运筹学大会
  • INFORMS Annual Meeting - 美国运筹学会年会

相关期刊 ​

  • European Journal of Operational Research - 运筹学顶级期刊
  • Computers & Operations Research - 计算与运筹研究
  • Journal of the Operational Research Society - 运筹学会期刊
  • Annals of Operations Research - 运筹学年鉴
  • International Journal of Production Research - 生产研究国际期刊

在线资源 ​

专业网站 ​

  • ESICUP - 欧洲切割装箱特别兴趣小组
  • 2DCutting - 二维切割问题门户
  • PackingProblems.org - 装箱问题资源中心

教育资源 ​

  • MIT OpenCourseWare - 组合优化课程
  • Stanford CS261 - 优化算法课程
  • Coursera Optimization - 在线优化课程

工具软件 ​

可视化工具 ​

  • SVG Viewer - SVG格式查看器
  • OpenGL Nesting Viewer - 3D可视化工具
  • Web-based Nesting Simulator - 浏览器排样模拟器

开发工具 ​

  • Geometry Processing Toolkit - 几何处理工具包
  • Polygon Editor - 多边形编辑器
  • Nesting Benchmark Suite - 排样算法性能测试套件