I'm looking to an algorithm to covering maximum surface of a polygon with rectangles. Rectangles have to have a specific width, a rectangle can't overlap an other one and each one has to fit in the polygon. I've already looking for other posts but I couldn't find an algo without overlap or specific width.

Note: The length can be different for any rectangle and rectangles can point in different directions.

Thanks for your help

  • 1
    $\begingroup$ I don't think your question is well-posed. Why not just take sufficiently long rectangles and stack them one on top of another until your polygon is covered? Perhaps you mean: Each rectangle must fit inside the polygon? $\endgroup$ – Joseph O'Rourke Jul 20 '16 at 20:16
  • $\begingroup$ Thanks @JosephO'Rourke. Youre were right, I edited my question. $\endgroup$ – Antoine L. Jul 20 '16 at 20:35
  • 1
    $\begingroup$ Still not clear. The rectangles all have the same, given, width, but the lengths can be different and arbitrary? Must the rectangles all be aligned, or can they all point in different directions? Anyway, this is a packing problem, and maybe that keyword will aid your search. But optimal packing algorithms are few and far between, you may have to settle for considerably less than the maximum area, or for a really slow algorithm. gamedev.stackexchange.com/questions/27055/… might be helpful. $\endgroup$ – Gerry Myerson Jul 20 '16 at 23:12
  • $\begingroup$ stackoverflow.com/questions/3303689/… might also be helpful. $\endgroup$ – Gerry Myerson Jul 20 '16 at 23:15
  • $\begingroup$ The length can be different for any rectangle and rectangles can point in different directions. I'll try searching with this keyword. Thanks @GerryMyerson $\endgroup$ – Antoine L. Jul 22 '16 at 6:39

If the rectangles must be aligned (Gerry Myerson's question), then perhaps this approximation might suffice, depending on your needs. Let the width $w$ of your rectangles be $1$. Orient your polygon $P$ randomly. Lay a series of unit-separated parallel lines over $P$ and compute the area of the induced rectangle cover determined by those lines.

Reorient and repeat. Retain the maximal area.

It seems possible that the optimal orientation could be computed, but at the moment I don't see how.

  • $\begingroup$ Unfortunately rectangles can point in different directions.. $\endgroup$ – Antoine L. Jul 22 '16 at 6:44
  • $\begingroup$ It may be that your problem is such a specific variant of rectangle packing that it has not yet been investigated. There has been work on packing with rectangles whose width is maximized; but the rectangles have different widths, just none very thin. $\endgroup$ – Joseph O'Rourke Jul 22 '16 at 12:16

Your Answer

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

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