The following is the problem description:

All angles of the polygon are right. It may be convex or concave. Use rectangles of the same size to cover the polygon. The edge of the polygon and rectangle are parallel with the coordinate axis. Overlapping between rectangle is allowed. All rectangles are oriented in the same direction.

The objective is to minimize the number of rectangles and to minimize the overlap, i.e., the fewest rectangles given that the smallest overlap, or the smallest overlap given that, the fewest rectangles. Note that the rectangles can cover outside of the polygons, and also allow there may exist some gaps between rectangles. The constraints are not very strict in this problem because this is not a pure math problem.

I have no background with computational geometry. I searched online and find many algorithms use different rectangles to cover the polygon.

Does anyone know some algorithms to solve this? It would be better if anyone could provide the code of the algorithm. Many thanks!

  • $\begingroup$ "Use the same rectangle to cover the polygon": Do you mean that you want to cover the polygon with rectangles all of the same size? $\endgroup$ – user3533 Jun 2 '13 at 21:24
  • $\begingroup$ You should try to specify more precisely what you want to optimize. You named two quantities. Do you want the fewest rectangles, and, given that, the smallest overlap? Or the smallest overlap, and, given that, the fewest rectangles? Also, how did you come to this problem? $\endgroup$ – dfeuer Jun 2 '13 at 22:54
  • 1
    $\begingroup$ Note that minimizing overlap can make the number of rectangles blow up: Take for example the polygonal region at flickr.com/photos/29654586@N07/8930047256 If $AB = AD = DF = CG$ and $HI$ is just a tiny bit longer than these, then minimizing overlap will require you to use many short, wide rectangles. The closer $HI$ is to $GH$ while still being longer, the more rectangles you will need to minimize overlap. $\endgroup$ – dfeuer Jun 2 '13 at 23:07
  • $\begingroup$ The wikipedia page on polygon covering: en.wikipedia.org/wiki/Polygon_covering may provide some clues, although it does not relate to your exact problem. $\endgroup$ – Erel Segal-Halevi Jul 10 '14 at 8:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.