Metadata-Version: 2.1
Name: 2DBinPacking
Version: 0.1.1
Summary: 面向装箱的二维排版算法（NFP + BottomLeft）：支持圆与凸多边形、重量优先堆叠、First-Fit 多 bin
License: MIT
Requires-Python: >=3.9
Requires-Dist: pyclipper
Requires-Dist: matplotlib
Description-Content-Type: text/markdown

# 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)`

## 安装

```bash
pip install 2DBinPacking
```

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

## 快速开始

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

![混合形状排版效果](https://raw.githubusercontent.com/GLK52145/picture/main/layout_demo.png)

```python
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"`，与旧版本行为一致）：

| 模式 | 空 bin 首件位置 | 目标打分 | 适用场景 |
|------|----------------|----------|----------|
| `"corner"`（默认） | 左下角原点（包围盒贴 (0,0)） | 先低后左词典序：一层层从下往上填、同层从左到右 | 钢管/管材装箱，重件压底、堆叠整齐 |
| `"center"` | 箱子中心（包围盒中心对齐 bin 中心） | 物件包围盒中心到箱子中心的距离（越小越好） | 以中心为原点向外扩散、重心居中 |

```python
# 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` 可关闭标注，展示大片混合形状时更清爽）：

```python
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 概览

| 组件 | 说明 |
|------|------|
| `BinPacking.geometry.Polygon` | 凸多边形（CW 外轮廓，可选 CCW 洞），`weight` 属性 |
| `BinPacking.geometry.Circle` | 圆（旋转不变），`weight` 属性 |
| `BinPacking.geometry.Bin` | 容器：`Bin(width, height)` |
| `BinPacking.first_fit_algorithm.FirstFit` | 多 bin 装箱入口：`FirstFit(items, bin, global_distance, rotations, strategy, placement).do_pack()` |
| `BinPacking.placer_nfp.NfpPlacer` | NFP 排版器（直接使用需自行管理单 bin） |
| `BinPacking.placer_bl.BottomLeftPlacer` | 左下角贪心排版器 |
| `BinPacking.visualize.plot_layout` | 排版图输出：`plot_layout(bins, bin_w, bin_h, out_path=...)` |

## 算法说明

- **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](https://github.com/tamasmeszaros/libnest2d)，同样为 MIT 许可）
