2DBinPacking

2DBinPacking

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

特性

• NFP 排版器（NfpPlacer）：无碰撞多边形（No-Fit Polygon）算法，基于 pyclipper 布尔并集合并禁止区，沿边界搜索最优位置——布局紧凑，支持圆与凸多边形
• BottomLeft 排版器（BottomLeftPlacer）：左下角快速贪心算法（下移→左移交替），速度快，支持简单非凸形状（L 形等）
• 重量优先：Shape.weight 参与放置顺序，重件先放 → 自然堆在底层
• 可配置排版模式（placement）：corner（默认，先低后左词典序、堆左下角）或 center（首件放箱子中心、按与中心的距离打分 → 以中心为原点向外扩散）
• 排版图输出：plot_layout() 把排版结果直接保存为图片（matplotlib）
• First-Fit 多 bin：FirstFit.do_pack() 自动开新 bin，返回 (bins, unplaced)

安装

pip install 2DBinPacking

依赖：pyclipper（Clipper 多边形布尔运算）、matplotlib（输出排版图需要）。

快速开始

圆 + 矩形 + 三角形 + 正五/六边形共 46 件混合凸形状，在单个 600×600 箱内排版，面积利用率约 83%、无重叠：

import math
from BinPacking.geometry import Polygon, Circle, Bin
from BinPacking.first_fit_algorithm import FirstFit
from BinPacking.visualize import plot_layout   # 也可 from BinPacking import plot_layout

W, H = 600, 600                                # 箱体尺寸（mm）

def rect(w, h):                                # 矩形
    return Polygon([(0, 0), (w, 0), (w, h), (0, h)])

def tri(b, h):                                 # 三角形
    return Polygon([(0, 0), (b, 0), (b / 2, h)])

def regular(r, n):                             # 正 n 边形（任意凸多边形）
    return Polygon([(r * math.cos(math.pi / 2 + 2 * math.pi * i / n),
                     r * math.sin(math.pi / 2 + 2 * math.pi * i / n))
                    for i in range(n)])

items  = [rect(168, 84)   for _ in range(4)]   # 矩形
items += [rect(126, 105)  for _ in range(4)]
items += [rect(126, 63)   for _ in range(4)]
items += [rect(84, 84)    for _ in range(6)]
items += [rect(63, 63)    for _ in range(4)]
items += [tri(105, 84)    for _ in range(4)]   # 三角形
items += [tri(63, 63)     for _ in range(4)]
items += [Circle(58)      for _ in range(2)]   # 圆
items += [Circle(40)      for _ in range(3)]
items += [Circle(26)      for _ in range(4)]
items += [regular(42, 6)  for _ in range(3)]   # 正六边形
items += [regular(40, 5)  for _ in range(2)]   # 正五边形
items += [rect(300, 20), rect(160, 20)]        # 顶层扁条

bins, unplaced = FirstFit(items, Bin(W, H), strategy="nfp").do_pack()
print(f"使用 {len(bins)} 个 bin，放置 {sum(len(g) for g in bins)} / {len(items)} 件")

# 输出排版图（运行本段代码即可得到文首那张图；利用率为 83.4%）
plot_layout(bins, W, H, out_path="layout.png",
            title="mixed shapes / nfp / 46 items / 83.4%", label=False)

大件先放、一层层从下往上铺——圆、三角形等不同形状也能与矩形紧密贴合，塞满箱体。

排版模式（placement）

placement 控制「物件从哪里开始排、按什么目标选位置」，支持两种模式（默认 "corner"，与旧版本行为一致）：

# center 模式：首件居中，后续物件紧贴已放件、尽量靠近中心 → 布局以中心原点向外扩散
ff = FirstFit(items, Bin(600, 600), strategy="nfp", placement="center")
bins, unplaced = ff.do_pack()

说明：

• placement="center" 仅 NFP 策略（strategy="nfp"）支持；配合 "bl" 会抛 ValueError（BottomLeft 是挤压贴角算法，无中心语义）。
• center 与 C++ libnest2d 的默认目标函数一致（物件仍彼此紧贴成簇，簇以第一个居中的物件为中心向外生长）。

输出排版图

BinPacking.visualize.plot_layout()（也在包顶层导出）把 do_pack() 的结果直接画出来，多个 bin 从左到右并排、物件默认按 shape_id 标注（label=False 可关闭标注，展示大片混合形状时更清爽）：

from BinPacking import plot_layout

bins, unplaced = FirstFit(items, Bin(600, 600), strategy="nfp").do_pack()

# 保存为图片（多 bin 会自动并排绘制）
plot_layout(bins, 600, 600, out_path="layout.png", title="600x600 / nfp")

# 或返回 Figure 继续定制 / 弹窗展示：
fig = plot_layout(bins, 600, 600, title="600x600 / nfp")   # 不传 out_path
# fig.axes[0].set_xlabel("x") 等自定义后：
fig.savefig("layout_custom.png")

签名：plot_layout(bins, bin_w, bin_h, out_path=None, title=None, dpi=150, show=False, label=True)。 bins 即 do_pack() 返回的第一项（List[List[Shape]]），也可直接传某个排版器的 placer.packed。

API 概览

算法说明

• NFP：对每个已放物件计算无碰撞多边形（禁止区），用 pyclipper（Clipper 布尔并集）合并为整体禁止区，沿边界采样搜索最优位置。圆-圆/圆-多边形 NFP 用 64 边形近似（误差 < 0.12%·r，与 C++ libnest2d 一致）
• 打分：placement="corner" 用「先低后左」词典序（模拟人工从下往上装卸，Python 版为管材装箱新增）；placement="center" 用「物件中心到箱子中心距离」最小（C++ libnest2d 默认目标函数）
• 非凸限制：NFP 策略只支持凸多边形/圆（非凸输入会被拒绝并计入 unplaced，避免错误重叠）；非凸形状请用 strategy="bl"
• 间距：global_distance 指定物件间最小间距（排版时各膨胀一半）

许可证

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