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!)
Best Answer
As has been mentioned over at SO, this problem is very difficult from a computational perspective. It may help to see what methods have been implemented for the packing problem. There are some algorithms out there, but you may have to fine-tune one to fit your needs.
Even a naive, greedy approach may end up being pretty inefficient. Would you take into account things like rotating the shape? There are all kinds of trade-offs to be made, but your "slices" (first fit) approach may work if you need something quick and dirty.