2
$\begingroup$

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

Improve this question
$\endgroup$
5
  • 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
    Commented Jul 20, 2016 at 20:16
  • $\begingroup$ Thanks @JosephO'Rourke. Youre were right, I edited my question. $\endgroup$
    – Antoine L.
    Commented Jul 20, 2016 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
    Commented Jul 20, 2016 at 23:12
  • $\begingroup$ stackoverflow.com/questions/3303689/… might also be helpful. $\endgroup$
    – Gerry Myerson
    Commented Jul 20, 2016 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.
    Commented Jul 22, 2016 at 6:39

1 Answer 1

Reset to default
4
$\begingroup$

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.

      RectCover
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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Unfortunately rectangles can point in different directions.. $\endgroup$
    – Antoine L.
    Commented Jul 22, 2016 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
    Commented Jul 22, 2016 at 12:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .