Đặt hình chữ nhật không chồng chéo ngẫu nhiên trên bảng điều khiển

Question

Tôi có bảng điều khiển có kích thước X bằng Y. Tôi muốn đặt tối đa hình chữ nhật N, có kích thước ngẫu nhiên, trên bảng này, nhưng tôi không muốn bất kỳ hình nào chồng lên nhau . Tôi cần biết vị trí X, Y cho các hình chữ nhật này.

Thuật toán, bất kỳ ai?

Chỉnh sửa: Tất cả hình chữ nhật N được biết ngay từ đầu và có thể được chọn theo thứ tự bất kỳ. Điều đó có thay đổi quy trình không?

Answer 1

Bạn có thể lập mô hình này bằng một bộ hình chữ nhật "miễn phí", bắt đầu bằng hình chữ nhật đơn có tọa độ là 0,0, kích thước (x, y). Mỗi lần bạn cần thêm một hình chữ nhật nữa, hãy chọn một hình chữ nhật "miễn phí" còn lại, tạo hình chữ nhật mới (với tọa độ và kích thước trên cùng bên trái) và chia hình chữ nhật đó cũng như bất kỳ chồng chéo nào khác " miễn phí "hình chữ nhật, như vậy trẻ em thể hiện không gian còn lại miễn phí. Điều này sẽ dẫn đến 0 đến 4 hình chữ nhật mới (0 nếu hình chữ nhật mới chính xác là kích thước của hình chữ nhật miễn phí cũ; 4 nếu nó ở giữa và vân vân). Theo thời gian, bạn sẽ nhận được nhiều hơn và nhiều hơn nữa các khu vực miễn phí nhỏ hơn và nhỏ hơn, do đó, hình chữ nhật bạn tạo ra sẽ được nhỏ hơn là tốt.

Ok, không phải là một giải thích rất phức tạp, nó dễ dàng hơn để hiển thị trên bảng trắng. Nhưng mô hình là một trong những tôi được sử dụng cho việc tìm kiếm vị trí bắt đầu cho các thành phần gui cut'n mới được dán; thật dễ dàng để theo dõi các khối màn hình có sẵn và chọn (ví dụ) ở bên trái hoặc trên cùng khu vực đó.

Answer 2

Dưới đây là một bài viết khá trên các thuật toán đóng gói 2d: http://www.devx.com/dotnet/Article/36005

Bạn thường sẽ muốn một số loại thuật toán sử dụng công nghệ tự động để đạt được kết quả khá. Một giải pháp đơn giản (nhưng không tối ưu) sẽ là thuật toán phù hợp đầu tiên.

Answer 3

Hoặc duy trì danh sách hình chữ nhật đã được thêm và tạo thuật toán để tìm ra vị trí đặt hình chữ nhật mới dựa trên danh sách đó. Bạn có thể tạo một lớp Rectangle cơ bản để giữ thông tin về các hình chữ nhật của bạn.

Không quá khó để tạo thuật toán tùy chỉnh.

Answer 4

Tôi đã sử dụng Rectangle Packing algorithm trong một trong các ứng dụng của tôi, có sẵn dưới dạng tệp nguồn C#.

Thuật toán được khởi tạo với kích thước của bảng điều khiển, sau đó bạn lặp qua tất cả các hình chữ nhật và nhận vị trí của chúng. Thứ tự của các hình chữ nhật có thể ảnh hưởng đến kết quả, tùy thuộc vào nhà đóng gói.

Answer 5

Tôi khuyên bạn nên sử dụng đề xuất StaxMans.

Đây là số 2c:

Thêm toàn bộ nhiều hình chữ nhật ngẫu nhiên (chồng lên nhau). xóa hình chữ nhật chồng chéo:

for rectangle in list of rectangles: 
    if rectangle not deleted: 
     delete all rectangles touching rectangle. 

để tìm tất cả các hình chữ nhật chạm vào một hình chữ nhật cụ thể, bạn có thể sử dụng một cây quad hoặc bất bình đẳng dựa trên x1, y1 x2, y2 giá trị.

Chỉnh sửa: Trên thực tế, hầu hết các công cụ trò chơi như pygame, v.v. bao gồm phát hiện va chạm của hình chữ nhật, đây là vấn đề thường gặp.