Điền một đa giác với số lượng hình chữ nhật tối thiểu

Question

Tôi đang cố gắng hiển thị đa giác, nhưng chúng chỉ có thể được hiển thị bằng hình chữ nhật được căn chỉnh theo trục. Vì vậy, tôi đang tìm kiếm một thuật toán về cơ bản có thể điền vào một đa giác bằng cách sử dụng số lượng hình chữ nhật có thể là ít nhất. Nếu nó giúp giảm số lượng, các hình chữ nhật được phép chồng lên nhau.

Tôi đã triển khai this fill algorithm, hầu hết là đủ. Sự sụp đổ là nó hạn chế hình chữ nhật cho mỗi hàng pixel. Cuối cùng tôi muốn giảm số lượng hình chữ nhật càng nhiều càng tốt.

Answer 1

Biểu thị pixel đa giác giống như đa giác tuyến tính và bạn có thể phân vùng nó khá nhanh. Xem câu trả lời cho số này question.

Answer 2

Xóa giới hạn đó (mỗi hình chữ nhật có chiều cao 1 pixel) sẽ giúp trong một số trường hợp đặc biệt khi đa giác được tạo thành từ hình chữ nhật lớn, nhưng hoàn toàn không phải trong trường hợp chung. Làm thế nào về điều này: sử dụng thuật toán đó, nhưng mở rộng mỗi hình chữ nhật lên và xuống càng nhiều càng tốt, và khi tất cả các hình chữ nhật được đặt ra, loại bỏ các hình chữ nhật thừa.

Vẫn còn một chút để cải thiện, trong đó đặt hàng trong đó bạn loại bỏ hình chữ nhật thừa có thể quan trọng trong một số trường hợp rất hiếm, nhưng thành thật mà nói tôi không nghĩ là đáng lo ngại về giải pháp thực tế .