Hình chữ nhật đóng gói Thuật toán

Question

Tôi cần giải quyết vấn đề sau: Tôi có nhiều hình chữ nhật kích thước: chiều rộng chiều rộng, chiều rộng/2 chiều cao/2, chiều rộng/4 chiều cao/4, chiều rộng/8 chiều cao/8 ... v.v.

Tôi cần phải đóng gói các hình chữ nhật này thành hình chữ nhật lớn có kích thước x * chiều rộng y * chiều cao sao cho không có hình chữ nhật chồng lên nhau, các hình chữ nhật được phân phối ngẫu nhiên trong bao bì và bất kỳ hình chữ nhật nào. Tôi đã thử một thuật toán tham lam khá cơ bản nhưng nó không thành công.

Bạn có thể cho tôi một số đề xuất về cách giải quyết sự cố không?

Cảm ơn!

EDIT: Bạn có thể có nhiều hơn một hình chữ nhật của mỗi kích thước

Đây không phải là bài tập về nhà. Tôi đang cố tạo hiệu ứng tương tự như hiệu ứng trên ted.com

Theo cách ngẫu nhiên, tôi có thể tồn tại nhiều hơn một bao bì hình chữ nhật đáp ứng các ràng buộc. Thuật toán không được tạo ra cùng một đóng gói ở mỗi lần chạy.

Answer 1

Bạn có thể sử dụng chỉ mục không gian hoặc quadtree để chia nhỏ mặt phẳng 2d. Ý tưởng là để giảm vấn đề 2d xuống một vấn đề 1d. Một khi bạn có chỉ số không gian (hoặc không gian-điền đường cong) và bạn có thể discretize 2d vào 1d bạn có thể sử dụng 1d để tìm kiếm tương tự hoặc để sắp xếp từ thấp đến cao hoặc ngược lại ví dụ theo chiều dài. Nếu bạn nhận được đơn đặt hàng này, bạn có thể tính toán chỉ mục trở lại với represenation 2d và đóng gói chúng theo cách hiệu quả nhất trong vùng chứa của bạn. Có nhiều cách để tạo ra một chỉ mục không gian. Một số tốt nhất nhưng khó thực hiện là đường cong hilbert. Một số khác là đường cong z hoặc đường cong hình tròn. Nó khác với đường cong zizag vì nó chia nhỏ mặt phẳng thành 4 ô vuông (không phải hình chữ nhật).

EDIT: Đây là một liên kết cho một Jquery-Plugin: http://www.fbtools.com/jquery/treemap/ đây với poplulation thế giới: http://www.fbtools.com/jquery/treemap/population.html

EDIT: http://people.csail.mit.edu/konak/papers/socg_2008-circular_partitions_with_applications_to_visualization_and_embeddings.html

EDIT: http://lip.sourceforge.net/ctreemap.html

Answer 2

Giả sử bạn chỉ có một hình chữ nhật cho mỗi kích thước, bạn có thể cố gắng sao chép sắp xếp kích thước giấy. Sắp xếp các hình chữ nhật theo kích thước từ lớn nhất đến nhỏ nhất, sau đó

1. Đặt hình chữ nhật đầu tiên và đặt nó ở góc của mặt phẳng đích.
2. Hãy hình chữ nhật tiếp theo (khẳng định đó là nhỏ hơn so với hình chữ nhật trước)
3. Xoay khoảng 90 độ
4. Nơi để
   • kích thước ngắn hơn của nó là tiếp giáp với kích thước dài hơn những người hàng xóm lớn cuối cùng
   • và cạnh dài hơn của nó tiếp giáp với cạnh của mặt phẳng đích hoặc cạnh của hàng xóm của cùng một kích thước
5. Lặp lại 2 - 4

Tôi nhận ra sự mô tả có thể là không rõ ràng, vì vậy đây là hình ảnh giới thiệu các giải pháp - nó sẽ giúp để nắm bắt nó:

Answer 3

Tại mỗi bước bạn chia bề mặt mới của bạn rectange bởi 4.

SUM (1/4 n cho n trong [0, inf]) = 4/3 **

Vì vậy, tốt nhất bạn có thể làm là phù hợp với hình chữ nhật của bạn trong một hình chữ nhật bề mặt 4/3 (chiều cao * chiều rộng)

(đó là một ràng buộc thấp hơn)

thuật toán @mloskot đưa ra một giải pháp khả thi mà sẽ nằm trong một hình chữ nhật bề mặt 3/2 * (chiều cao * chiều rộng): đây là một minh hoạ :

Tôi không thấy cách bạn có thể làm tốt hơn.

Answer 4

Đây là rất giống MIP-mapping

Answer 5

này nghe có vẻ giống như một rectangle packing problem. Có một liên kết đến một số algorithm. Mã đó gói các hình chữ nhật càng chặt càng tốt. Bạn nói rằng bạn muốn các hình chữ nhật được phân phối ngẫu nhiên, mà tôi đoán có nghĩa là không phải tất cả các hình chữ nhật có kích thước cạnh nhau và tất cả các hình chữ nhật trải ra để lấp đầy hình chữ nhật lớn. Có lẽ mã ở liên kết ở trên sẽ là một điểm khởi đầu tốt để có được một số ý tưởng.