CODEWITHSUNDEEP
algorithmgeometrycomputational-geometry
nimcap
nimcap

Reputation: 10493

How to approximate a polygon with n rectangles?

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.

Upvotes: 9

Views: 6043

Answers (4)

Peter
Peter

Reputation: 1260

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

Upvotes: 5

smirkingman
smirkingman

Reputation: 6358

  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

Upvotes: 5

High Performance Mark
High Performance Mark

Reputation: 78316

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.

Upvotes: 8

Jens Schauder
Jens Schauder

Reputation: 81882

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.

Upvotes: 2

Related Questions