# [R-sig-Geo] Function to cover polygons by rectangles

Barry Rowlingson b.rowlingson at lancaster.ac.uk
Thu Dec 7 11:22:59 CET 2006

```Christoph Hofer wrote:
> I am looking for an algorithm that cover an arbitrary polygon with as
> few rectangles as possible.

Just use one big rectangle. Big enough to cover the polygon. Job done.

Okay, I'll assume from now on you want to divide the polygon
internally into rectangles.

> (This rectangle approximate the area and the shape of the polygon)
> That means that the input parameter of the algorithm may  only be the
> coordinates of the polygon-vertices  and
> the output are the coordinates of a number of regular rectangles.

This problem doesn't seem well-posed just yet. You can't cover some
polygons with a finite number of rectangles, so you need to specify when
to stop - at a given number of rectangles or when X% of the polygon is
covered? Also, do you want to restrict your rectangles to be aligned to
some axis, or can each rectangle have any rotation?

This looks like a hard problem. I'm just trying to think about the
simplest non-trivial case I can come up with, filling an equilateral
triangle. How do you stick one rectangle in an equilateral triangle and
maximise its area?[1] Then for two rectangles, do you start with the
best one-rectangle solution and then add another to fill in a gap? Or is
the best solution two completely new rectangles?

Now, for a general, complicated, concave polygon... Ahhhh I give up.

Barry

[1] I think for a equilateral triangle of side 2 the best single
rectangle is a rectangle of side (1,sqrt(3)) aligned centrally and
adjacent to one side. I think I've just convinced myself that for two
rectangles you stick a similar rectangle into the remaining equilateral
triangle portion. If you continue, at some point you'll want to start
filling in the semi-equilateral triangle pieces left by the first
rectangle...

```