Skip to content

Function to cover polygons by rectangles

5 messages · Christoph Hofer, Barry Rowlingson, Roger Bivand

Original
Christoph Hofer
# 
Dear all,

Is there a function or package  to cover arbitrary polygons by  
rectangles?
I want to approximate a polygon area with as few rectangles as possible.


Thanks in advance.

Best regards

Christoph
Roger Bivand
#
On Thu, 7 Dec 2006, Christoph Hofer wrote:

            

      
      
      
    

        
If regular rectangles, then maybe overlaying SpatialPolygons and 
SpatialPixels may help. But if you are asking for quadtrees, that is I 
think not provided anywhere that I'm aware of (SPANS did that until they 
disappeared). Does starspan help:

http://starspan.casil.ucdavis.edu/?StarSpan

Roger

            

      
      
      
    

        

      
      
    

        

  
    

      
      
    

  


  


      

    

    

      
      

        


  

        

      Christoph Hofer
    

    

      
      #
    

  


  

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

Best Regards

Christoph





Am 07.12.2006 um 10:23 schrieb Roger Bivand:

            

      
      
      
    

        

      
      
    

            

      
      
      
    

  
  


  


      

    

    

      
      

        


  

        

      Barry Rowlingson
    

    

      
      #
    

  


  

      
Christoph Hofer wrote:

            

      
      
      
    

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

  
  


  


      

    

    

      
      

        


  

        

      Roger Bivand
    

    

      
      #
    

  


  

      
On Thu, 7 Dec 2006, Christoph Hofer wrote:

        

            

      
      
      
    

        
Then try overlay() of a SpatialGrid on SpatialPolygons, varying the grid 
size and origin manually until you are happy.

Roger