Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!)

share|improve this question
    
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

1 Answer 1

up vote 2 down vote accepted

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.

rotate

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.