Tell me more ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.
up vote 1 down vote favorite

I'm trying to cover a polygon with the minimum set of rectangles like explained in the picture below, the used rectangles have the same size a*b (a != b) , the rectangle could be rotated by 90°(otherwise the square size could be a*b or b*a).

in the best case if we could have some overlap area, on the edge of adjacent rectangles, it would be great.

i would like to know if there's an algorithm could help in this problem. any help is welcomed.

enter image description here

I'm using arcpy in arcgis 10.1

share|improve this question
2  
This problem, with minor changes, is practically the same as packing polygons within a given polygon, whose solution is discussed at gis.stackexchange.com/questions/27303/…. – whuber♦ Dec 26 '12 at 16:03
@whuber thanks a lot – geogeek Dec 27 '12 at 16:09
i think that this problem is simpler than the problem in the link, i'm not quite sure but i think that this question could have a simple solution , i have added a picture for more explanation. – geogeek Dec 27 '12 at 17:35
1  
Yes, I thought so too. It looks simpler when you do not allow the rectangle to be rotated, but with the rotations, it becomes combinatorially much more difficult. Even in your tiny example it looks to me like a better solution may be available involving only four rectangles. – whuber♦ Dec 27 '12 at 17:42

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.