Cover a Concave Polygon with a minimum number of rectangles

I am trying to cover a simple concave polygon with a minimum rectangles. My rectangles can be any length, but they have maximum widths, and the polygon will never have an acute angle.

I thought about trying to decompose my concave polygon into triangles that produce a set of minimumally overlapping rectangles minimally bounding each triangle and then merging those rectangles into larger ones. However, I don't think this will work for small notches in the edges of the polygon. The triangles created by the reflex vertices on those notches will create the wrong rectangles. I am looking for rectangles that will span/ignore notches.

I don't really know anything about computational geometry, so I'm not really sure on how to begin asking the question.

I found other posts that were similar, but not what I need:

Some examples: Black is the input. Red is the acceptable output.

Another exmaple: The second output is prefered. However, generating both outputs and using another factor to determine preference is probably necessary and not the responsibility of this algorithm.

Polygons that mimic curves are extremely rare. In this scenario much of the area of the rectangles is wasted. However, this is acceptable because each rectangle obeys the max width constraint.

Also, I found this article to be close to what I need:

Maybe a better question is "How can I identify rectangular-like portions of a concave polygon?"

Here is an image showing the desired implementation:

The green is the actual material usage. The red rectangles are the layouts. The blue is the MBR of the entire polygon. I am thinking I should try to get little MBRs and fill them in. The 2-3 green rectangles in the upper left corner that terminate into the middle of the polygon are expensive. That is what I want to minimize. The green rectangles have a min and max width and height, but I can use as many rows and columns necessary to cover a region. Again, I must minimize the number of rectangles that do not span across the input. I can also modify the shape of the green rectangle to fit in small places that is also very expensive. In other words, getting as many rectangles as possible to span as much as possible is ideal.

• Your title says convex polygons, but the question talks of concave polygons. Perhaps you need to make some corrections? Aug 22, 2012 at 1:50
• @JukkaSuomela, in the first two pictures, the polygon is roughly the same size, and in the first picture, I could have run three rectangles vertically as I did in the second. However, this is less desirable. I think the trick has to do with the perimeters of the rectangles. Maybe what I am trying to do is minimize the amount of boundry of rectangle that is inside of the polygon, and maximize the amount of boundry that is collinear with the edges of the polygon. However, sometimes the rectangles must spill out of the polygon to cover it fully. Aug 22, 2012 at 14:00
• @JohnMoeller, I understand. This is a problem where a human can identify the solution easily but stating the problem correctly is quite difficult. The problem is similar to laying carpet or wall paper and the actual problem is a structural/architectual one. I am trying to identify regions of rectangular layouts that later will be filled with another form of tesselation. Finding those rectangles and handling the non-rectangular regions is the problem. Let me know if I can explain more. Aug 22, 2012 at 20:54
• I think we should approach this first as a modelling question: the goal is not to come up with an algorithm that solves a well-defined optimisation problem, but the goal is to define the optimisation problem. Aug 22, 2012 at 21:01
• @JoshC.: Perhaps it would be also helpful if you tried to tell us more about the real-world application. I gather from your description that, for example, cutting is fairly expensive — ideally, the rectangular pieces would require as little cutting as possible. Is this correct? Aug 22, 2012 at 21:03