Cần giúp đỡ sáp nhập một số hình chữ nhật
Hi, tôi có mớ hỗn độn đống lộn xộn này ở bên trái, đó là khá nhiều một mảng của hình chữ nhật với một số lỗ (đánh dấu màu đỏ). Tôi đang tìm một cách để kết hợp chúng theo cách mà tôi sẽ kết thúc với càng ít hình chữ nhật càng tốt và tốt nhất là hầu hết chúng sẽ càng gần hình vuông càng tốt. Nhìn vào hình ảnh bên phải, đó là loại điều tôi đang cố gắng hoàn thành, chỉ cần một chút đẹp hơn và tốt hơn là tự động hơn một chút.
Tôi cần điều này cho một trò chơi và nó sẽ không được thực hiện trong thời gian chạy vì vậy tốc độ không thực sự là một mối quan tâm (trừ khi nó cực kỳ chậm, bởi vì tôi phải làm điều đó trên một diện tích khá lớn) nhưng tôi chưa bao giờ phải làm điều gì đó như thế này trước đây và tôi thành thật không biết phải bắt đầu từ đâu.
Tôi đã cố gắng bruteforcing theo cách của tôi thông qua mảng, bắt đầu từ hình vuông bên trái và loại sáp nhập cho đến khi không còn gì để hợp nhất nhưng thực sự không hiệu quả vì không thể xem xét hợp nhất hình chữ nhật 3x2, 4x3 , vv ..
Nếu bạn có thể chỉ cho tôi bất kỳ thuật toán nào có thể xử lý loại điều này hoặc có ý tưởng về cách thực hiện điều này, nó sẽ được đánh giá cao. Cảm ơn!
Tôi gặp vấn đề tương tự một chút trong khi trở lại: https: //stackoverflow.com/questions/11002205/find-all-rectangular-areas-with-certain-properties-in-a- ma trận Tuy nhiên trong trường hợp của tôi, các hình chữ nhật thu được có thể trùng lặp. Có lẽ bạn có thể thích ứng với điều đó, tìm tất cả các hình chữ nhật chồng chéo có kích thước tối đa, sau đó cho mỗi vùng được bao phủ bởi nhiều hình chữ nhật, thêm nó vào chính xác một trong những hình chữ nhật đó. – HugoRune
chỉ vì vậy tôi hoàn toàn hiểu, là các hình chữ nhật được tạo ra từ việc vẽ các đường dọc/ngang trên một hình chữ nhật lớn và sau đó chọn một số hình chữ nhật được tạo ngẫu nhiên làm hình chữ nhật 'đỏ'? –
Không, tôi bắt đầu với một tờ chỉ có hình chữ nhật màu đỏ và sau đó tôi cắt toàn bộ trang tính xung quanh. – Otopkin