Cách đóng gói thùng 2D được lập trình như thế nào?

Question

Có một vài câu hỏi tương tự trên stackoverflow, nhưng không có câu hỏi nào có vẻ như cung cấp câu trả lời hữu hình cho người nào đó mà không hiểu rõ vấn đề NP-hard và thuật toán có thể hiểu được.

Làm cách nào để thực hiện đóng gói thùng 2D đối tượng hình chữ nhật? Trong trường hợp của tôi, tôi đang cố gắng tập hợp một số hình ảnh thành một hình ảnh duy nhất, để sử dụng như một spritesheet, sử dụng số lượng nhỏ nhất của không gian. Mỗi hình ảnh có thể có các giới hạn cực kỳ khác nhau, nhưng không có giới hạn nào được đặt cho vùng chứa. Tôi đã hy vọng một ai đó hiểu biết về các thuật toán đóng gói thùng rác có thể giải thích cách thức này có thể đạt được lập trình, thay vì cung cấp tổng quan chung về phương pháp đóng gói thùng rác.

Answer 1

I Googled "bin packing code" và đây là hit đầu tiên của tôi: http://codeincomplete.com/posts/2011/5/7/bin_packing/

Dưới đây là một bản tóm tắt: xây dựng một cây nhị phân. Mỗi nhánh cây có chứa một sprite. Mỗi nút lá đại diện cho không gian có sẵn. Ban đầu cây chỉ có nút gốc, biểu thị tất cả không gian có sẵn. Để thêm một sprite vào cây, tìm kiếm cây cho một nút trống (lá) đủ lớn để giữ hình sprite. Biến nút đó từ một lá thành một nhánh bằng cách thiết lập sprite là người cư ngụ của nút và cho nút hai con. Một đứa trẻ đại diện cho không gian còn lại ở bên phải của sprite; khác đại diện cho không gian còn lại bên dưới sprite và đứa trẻ đầu tiên.

Bài viết tôi đã liên kết ở trên giải thích điều này đầy đủ hơn, với sơ đồ và mã JavaScript. Nó cũng giải thích làm thế nào để tự động phát triển bảng ma trận thay vì chọn một kích thước cố định trước.

Answer 2

Tất cả bạn cần là ở đây: https://github.com/juj/RectangleBinPack

Có một giấy và một phong nha C++ thực hiện.

Nếu bạn cần một pseudo-code thậm chí đơn giản hơn, hãy xem tại trang web này: http://www.blackpawn.com/texts/lightmaps/

Các "chém gói" được gọi là đóng gói cây dựa trên đó.