2DBinPacking

面向钢管打捆装箱场景的二维排版算法包：重管在下、轻管在上、紧凑堆叠。

特性

• NFP 排版器（NfpPlacer）：无碰撞多边形（No-Fit Polygon）算法，基于 pyclipper 布尔并集合并禁止区，沿边界搜索最优位置——布局紧凑，支持圆与凸多边形
• BottomLeft 排版器（BottomLeftPlacer）：左下角快速贪心算法（下移→左移交替），速度快，支持简单非凸形状（L 形等）
• 重量优先：Shape.weight 参与放置顺序，重件先放 → 自然堆在底层
• 词典序评分：先装下面再装上面、同层从左到右，模拟人工装卸
• First-Fit 多 bin：FirstFit.do_pack() 自动开新 bin，返回 (bins, unplaced)

安装

pip install 2DBinPacking

依赖：pyclipper（Clipper 多边形布尔运算）、matplotlib（可选，绘图用）。

快速开始

from BinPacking.geometry import Polygon, Circle, Bin
from BinPacking.first_fit_algorithm import FirstFit

# 构造物件（钢管：Circle + 重量；型材：凸多边形）
pipes = [Circle(30, shape_id=1) for _ in range(15)]   # 粗管 r=30mm
for p in pipes:
    p.weight = 12.0                                    # kg，重件先放

plates = [Polygon([(-30, -20), (30, -20), (30, 20), (-30, 20), (-30, -20)]) for _ in range(10)]
items = pipes + plates

# 排版：600×600 bin，nfp 策略（bl 策略用 strategy="bl"）
ff = FirstFit(items, Bin(600, 600), global_distance=0.0,
              rotations=None, strategy="nfp")
bins, unplaced = ff.do_pack()

print(f"使用了 {len(bins)} 个 bin，未放置 {len(unplaced)} 件")
for i, packed in enumerate(bins):
    print(f"bin{i+1}: {len(packed)} 件")

API 概览

算法说明

• NFP：对每个已放物件计算无碰撞多边形（禁止区），用 pyclipper（Clipper 布尔并集）合并为整体禁止区，沿边界采样搜索最优位置。圆-圆/圆-多边形 NFP 用 64 边形近似（误差 < 0.12%·r，与 C++ libnest2d 一致）
• 非凸限制：NFP 策略只支持凸多边形/圆（非凸输入会被拒绝并计入 unplaced，避免错误重叠）；非凸形状请用 strategy="bl"
• 间距：global_distance 指定物件间最小间距（排版时各膨胀一半）

许可证

MIT（灵感与算法结构参考 libnest2d，同样为 MIT 许可）