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

[Barry Rowlingson]

Christoph Hofer wrote:
> Thanks for your answer. But sadly starspan is not what im looking for.
> 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...