7

Is there any algorithm that can approximate the given polygon with n non overlapping rectangles that gives the maximum coverage? By maximum coverage I mean, the sum of the rectangle areas are maximized. Rectangles are not necessarily equal sized.

The polygons I am dealing are convex. If exact solution is hard/expensive to find (which I am expecting it to be), simple good heuristics are welcome too.

Edit I always thought of approximating the polygon with rectangles inside polygon, but solutions with rectangles not totally inside polygons are also fine. If that is the case, maximization of the area becomes minimization of the area.

Edit 2 I forgot to mention that these rectangles are orthogonal rectangles, i.e. aligned with axises.

nimcap
  • 10,062
  • 15
  • 61
  • 69
  • Can you maybe provide some more information? I would like to know, what information you want to gain (number of rectangles, total area sum, % of wasted 'space'). Additionally there is also something you have to specify: Do you want the maximum area coverage with the minimum number of rectangles? Because with a lot of 1mm^2 rectangles you could approximate the area pretty good. If so, this sounds like http://en.wikipedia.org/wiki/Multi-objective_optimization. Maybe you can project your problem onto a multiple knapsack-problem. – Slomo Jun 06 '12 at 14:39
  • @Slomo: I will give the polygon and number of rectangles as input. Is that enough? – nimcap Jun 06 '12 at 14:58
  • Well yes, thank you. Based on this, the first idea of Jens Schauder seems reasonable. As you have only convex polygons, the biggest rectangle will be in the center. So you can recursively find the maximum rectangle of the next smaller area left over. Your recursion will end when you hit your nth rectangle (input). – Slomo Jun 06 '12 at 15:24
  • There's an interesting solution for *regular* polygons here http://stackoverflow.com/questions/3296102/efficient-packing-algorithm-for-regular-polygons – smirkingman Jun 07 '12 at 07:24
  • A very good method for the the largest orthogonal rectangle here http://cgm.cs.mcgill.ca/~athens/cs507/Projects/2003/DanielSud/ – smirkingman Jun 07 '12 at 07:37

4 Answers4

8

One approach would be to create a (in the general case rectangular) bounding box for your polygon. Calculate the difference between the area of the bounding box and the area of the polygon. If the difference is small enough, you're done, if not, continue ...

Divide the box into 4 equal-sized rectangles, 2x2. Figure out which of these rectangles is entirely inside the polygon. Calculate the difference between the total area of the rectangles inside the polygon and of the polygon. If the difference is small enough you're done, if not continue ...

Divide each of the 4 rectangles into 4 sub-rectangles ... if at any stage you find that a rectangle is either fully inside or fully outside your polygon you can remove it from the list of rectangles to subdivide at the next iteration.

In other words, use a quadtree to divide the space containing your polygon and develop it to the extent necessary to meet your accuracy criteria.

High Performance Mark
  • 77,191
  • 7
  • 105
  • 161
4
  1. Create a queue of polygons, Q, to be processed

  2. Add the initial polygon to Q

  3. Remove a polygon P from Q

  4. Find the longest side A of P
  5. Rotate P so that A is on the X-axis
  6. If P is a triangle, split it with a perpendicular line in the centre of A: enter image description here
  7. Add the two halves G and H to Q and goto 3
  8. (Now, P has 4 or more sides)
  9. If X and/or Y are acute:

enter image description here

10 . Take the next longest side of P, A, and goto 5

11 . Project a red rectangle up from A. Find the 2 points where it intersects P, B and C: enter image description here

12 . Choose the longer(B) and finalise the green rectangle

13 . Add the remaining figures (D, E and F) to Q

14 . Goto 3

smirkingman
  • 6,167
  • 4
  • 34
  • 47
3

I realize this is a really old question but I recently stumbled across a similar problem where I had to try to approximate a polygon with rectangles. Using some of the ideas presented here and elsewhere, I started with an inscribed rectangle and generated rectangles around the inscribed rectangle to provide the general shape of the polygon.

This approach works well for convex polygons and reasonable well for some concave polygons - especially if you take an iterative approach (e.g. feed output rectangles as inputs to another iteration).

For extremely concave shapes, you might consider breaking up the polygon into convex hulls and then applying the technique I described above. The Bayazit implementation looks very promising.

In case anyone is interested, I have posted my implementation using inscribed rectangles here: https://github.com/pborissow/Poly2Rect

Poly2Rect

Peter
  • 1,182
  • 2
  • 12
  • 23
2

A first idea, maybe others can improve on it.

  • place a squaresomewhere inside the polygon, as far as possible away from any edges.
  • iteratively 1.) grow it, 2.) move it and turn it to maximize its distance from edges. until you can't grow it any more
  • start from the beginning, while considering edges of placed rectangles as edges of the polygon.
Jens Schauder
  • 77,657
  • 34
  • 181
  • 348