# How many rectangles can fit in a polygon with n-sides?

I am trying to write an algorithm to solve a problem I have. I have a few ideas of what the algorithm might be like but I am posting to see if anyone else has a better more efficient solution or any helpful suggestions. For context, this algorithm is going to be for maximising the number of solar panels that can be placed on a roof.

Given a polygon with n-sides with coordinates $(x_1, y_1), (x_2, y_2) .....(x_n, y_n)$, how many rectangles of dimension (for example) $1\times3$ can fit within this shape?

The orientation of the rectangle can be portrait or landscape but must be consistent throughout. They are also to be arranged in a grid pattern.

At the moment my half solution is to "cut" the polygon into "strips" of, let's say, $1$ unit and see how many can fit on that and continue until all the strips are done. Alternatively, for simple polygons with a low "$n$", finding the largest rectangle that can fit within the polygon and fill it? I am keen to work out the coordinates of the rectangle that can fit in the polygon in the final solution!

Any help or suggestions would be much appreciated,

Kelvin.

EDIT: I am probably looking towards a more simple and crude solution rather than a complex and more accurate method (as I am a geographer and therefore my maths skills are a bit limited!)

-
This question has been seen over at SO. Also, when you mention "must be consistent throughout", do you mean that all rectangles must be portrait or that their edges can only be perpendicular/parallel with each other (no weird angles)? – Zairja Jul 30 '12 at 16:42
Thank you @Zairja for linking me to that thread! – Kel196 Jul 30 '12 at 16:45
When I mention "consistent throughout" I mean the rectangles must all be portrait or landscape and also be parallel with each other. – Kel196 Jul 30 '12 at 16:47