Fill a polygon with the smallest sum of rectangles

Question

I'm trying to display polygons, but they can only be displayed using rectangles aligned on the axis. So, I'm looking for an algorithm that can basically fill a polygon using the least amount of rectangles. If this helps reduce the amount, the rectangles may overlap.

I have already implemented this filling algorithm , which is mostly enough. The fall is that it limits the rectangles to each row of each pixel. Ultimately, I want to reduce the number of rectangles as much as possible.

Answer 1

The pixel representation of the polygon is the same as the rectilinear polygon, and you can split it pretty quickly. See the answer to this question .

Answer 2

Removing this restriction (each rectangle has a height of one pixel) helps in some special cases when the polygon is made of large rectangles, but not at all in the general case.

How about this: use this algorithm, but expand each rectangle up and down as much as you can, and when all the rectangles are in place, eliminate the extra ones.

There is still little room for improvement, since the order in which you eliminate redundant rectangles may matter in some very rare cases, but to be honest, I don’t think it’s worth worrying about a practical solution.