skjolber/3d-bin-container-packing

 [](https://mvnrepository.com/artifact/com.github.skjolber.3d-bin-container-packing) # 3d-bin-container-packing 该库执行3D矩形箱子装载；它尝试将一组3D物品匹配到一组3D容器中的一个或多个。结果可以限制为最大容器数量。 使用该库的项目将受益于： * 短且可预测的计算时间， * 相当好的容器空间利用率， * 对少量箱子（适合小订单）的暴力破解支持 以及 * 友好的API * 可定制的打包器 错误、功能建议和帮助请求可以通过[问题跟踪器]提交。 ## 获取 该项目使用Java实现，并通过[Maven]构建。项目可在中央Maven仓库获取。 对于上一个版本，请参见[3.x](https://github.com/skjolber/3d-bin-container-packing/tree/3.x)分支。

Maven坐标

添加 ``` <3d-bin-container-packing.version>4.0.0 ``` 和 ``` com.github.skjolber.3d-bin-container-packing core ${3d-bin-container-packing.version} ```

或

Gradle坐标

对于 ``` ext { containerBinPackingVersion = '4.0.0' } ``` 添加 ``` api("com.github.skjolber.3d-bin-container-packing:core:${containerBinPackingVersion}") ```

# 用法 计量单位不在考虑范围内，可以是厘米、毫米或英寸。 获取一个`Packager`实例，然后组合你的容器和产品列表： ``` List products = new ArrayList<>(); products.add(new BoxItem(Box.newBuilder().withId("Shoes").withSize(6, 10, 2).withRotate3D().withWeight(25).build(), 1)); products.add(new BoxItem(Box.newBuilder().withId("Pants").withSize(4, 10, 1).withRotate3D().withWeight(25).build(), 1)); products.add(new BoxItem(Box.newBuilder().withId("Hat").withSize(4, 10, 2).withRotate3D().withWeight(50).build(), 1)); // add a single container type Container container = Container.newBuilder() .withDescription("1") .withSize(10, 10, 3) .withEmptyWeight(1) .withMaxLoadWeight(100) .build(); // with unlimited number of containers available List containerItems = ContainerItem .newListBuilder() .withContainer(container) .build(); ``` 将全部装入一个容器： ``` PackagerResult result = packager .newResultBuilder() .withContainerItems(containerItems) .withBoxItems(products) .build(); if(result.isSuccess()) { Container match = result.get(0); // ... } ``` 使用最大容器数量： ``` int maxContainers = ...; // maximum number of containers which can be used PackagerResult result = packager .newResultBuilder() .withContainerItems(containerItems) .withBoxItems(products) .withMaxContainerCount(maxContainers) .build(); ``` 请注意，所有的`packager`实例都是线程安全的。 ### 简易打包器 一个简单的打包器 ``` PlainPackager packager = PlainPackager .newBuilder() .build(); ``` ### 最大面积适应优先（LAFF）打包器 使用LAFF算法的打包器 ``` LargestAreaFitFirstPackager packager = LargestAreaFitFirstPackager .newBuilder() .build(); ``` ### 暴力破解打包器 对于少量包裹（如<=6），暴力破解打包器可能是一个不错的选择。 ``` Packager packager = BruteForcePackager .newBuilder() .build(); ``` 另请参见`ParallelBoxItemBruteForcePackager`和`FastBruteForcePackager`打包器。 在实时应用中进行暴力破解时，建议使用截止时间。

算法细节

### 最大面积适应优先算法 实现基于[这篇论文][2]，并非传统的[装箱问题][1]求解器。 首先放置占据容器底部面积最大的箱子；其高度成为层级高度。填满剩余高度的箱子具有优先级。随后在同一层级剩余空间中按体积从大到小堆叠箱子。如果箱子高度低于层级高度，算法也会尝试将其放置在此处。 当一个层级无法再放入箱子时，层级递增并重复该过程。箱子可以旋转，但容器不能。 * `LargestAreaFitFirstPackager` 在每个层级内进行3D堆叠 * `FastLargestAreaFitFirstPackager` 在每个层级内进行2D堆叠 该算法运行速度合理，通常以毫秒计。某些定制化是可能的。 ### 简易算法 该算法选择体积最大的箱子，并将其放入最佳支撑位置。 ### 暴力破解算法 该算法没有选择最佳箱子或旋转的逻辑；对所有排列组合进行遍历，对每个排列尝试所有旋转： * `BruteForcePackager` 尝试所有箱子顺序、旋转和放置位置。 * `FastLargestAreaFitFirstPackager` 选择所有箱子顺序和旋转，并选择最合适的放置位置。 该方法的复杂度是[指数级的]，因此在合理时间内能够打包的箱子数量有限。然而，对于现实生活中的应用，例如在线购物订单，其可处理范围仍然很广。 可以在打包前使用相关迭代器估算最坏情况复杂度： * 排列 * 两个或更多箱子具有相同尺寸 * 在之前无法到达的索引处发生排列变异 * 更少的旋转 * 两个或更多边具有相同长度 * 在之前无法到达的索引处发生旋转变异 此外，暴力破解打包器的并行版本`ParallelBruteForcePackager`也适用于希望在多核系统上使用它的场景。 请注意，该算法在箱子数量上是递归的，因此不要尝试处理大量箱子（很可能无法及时完成）。

# 打包器定制 ## 容器内的障碍物 通过提供容器初始空闲空间（即点），使打包器考虑非矩形包装空间，例如支柱或容器内的其他障碍物。 ## 打包器控制 打包器（不包括暴力破解）可以通过各种`control`（插件）类型扩展以处理特定需求。 简而言之，`controls`是有状态的对象，在打包器构建过程中被赋予各种资源，然后在打包过程的特定里程碑处被通知和/或调用。 `Controls`必须按以下方式提供： * 构建器工厂 * 构建器 * 控件 ### 清单控件 决定哪些箱子放入哪个容器，即以何种组合方式。 一个典型示例是不要将打火机和炸药放在同一个容器中。 ### 点控件 决定特定箱子相关的哪些点。 例如，重型物品可能只需要地面级别的点，或易燃物品可能需要以特定区域堆叠。 ### 放置控件 决定箱子的最佳放置位置。 可以考虑一系列选项，如稳定性、堆叠高度、结构完整性等；甚至随机化也是可能的。请注意，这些功能不一定在此项目中的打包器内实现。 # 可视化工具 该项目包含一个简单的输出[可视化工具](visualization)，基于[three.js](https://threejs.org/)。此可视化工具目前旨在作为开发更好算法的工具；并非作为堆叠指令。 ### 安装 ``` cd visualizer/viewer npm install ``` ### 运行 ``` npm start ``` 注意：要在开发过程中“热重载”可视化工具，请让单元测试直接向查看器中的文件写入（请参见`VisualizationTest`示例）。  # 参与 如果您有任何问题、评论或改进建议，请提交问题或拉取请求。 关于错误的注意事项：请遵循[shuairan的](https://github.com/shuairan)示例，并[提交包含可视化的测试用例](https://github.com/skjolber/3d-bin-container-packing/issues/574)。 # 许可证 [Apache 2.0]。社交媒体预览来自[pch.vector on www.freepik.com](https://www.freepik.com/free-photos-vectors/people)。 # 有趣链接 * [堆叠的艺术：开发打包算法时面临的挑战](https://medium.com/@fayyazawais1412/the-art-of-stacking-challenges-faced-while-developing-a-packing-algorithm-64d869b924ab) # 历史 * 4.0.x：重大重写。破坏性变更。 * 支持打包组 * 各种打包控制方式： * 清单控件（箱子与箱子、箱子与容器） * 点控件（每个箱子的点） * 放置控件（选择最佳箱子+点） * 可视化工具的轻微改进 * 3.0.11：使用`BigInteger`验证最大体积/最大重量，计算实际剩余最大体积。 * 3.0.10：修复模块信息，升级依赖项。 * 3.0.9：修复导致无效打包结果的点支持错误 * 3.0.8：可视化修复 * 3.0.4-3.0.6：修复问题 #689 * 3.0.3：修复模块信息 * 3.0.2：使简易打包器优先选择较低的Z坐标而非支撑面积。 * 3.0.1：各种性能改进。 * 3.0.0：支持最大容器数量（即每种容器类型）。使用构建器。从现在开始进行各种优化。 * 2.1.4：修复问题 #574 * 2.1.3：修复空指针 * 2.1.2：整理代码，移除警告，删除部分依赖。 * 2.1.1：提升空闲空间计算性能 * 2.1.0：改进暴力破解迭代器，在暴力破解打包器中尊重截止时间。

标签：3D Bin Packing, 3D container packing, 3D rectangle packing, 3D装箱, bin packing, brute force, customizable packager, friendly API, Gradle, Java library, JS文件枚举, LAFF, Maven, maven central, open source, packaging library, short calculation time, small orders, space efficient, 三维布局, 供应链, 后台面板检测, 域名枚举, 容器装箱, 暴力算法, 最大矩形, 漏洞测试, 漏洞验证, 物流, 用户模式钩子绕过, 矩形打包, 空间利用率, 空间填充, 算法, 组合优化, 装箱问题, 计算几何, 路径优化