Any general rectangle covering algorithms?

Any general rectangle covering algorithms?

Post by Choose Anonymit » Sun, 01 Apr 2001 04:40:21



Is there an algorithm (no matter how inefficient) for covering any
general polygon (allowing holes) with rectangles?

(Clearly, a polygon with any acute interior angles would have to be
approximated, possibly using some specified epsilon.)

I've read a variety of papers from Levcopoulos, et. al.; Reckhow &
Culberson; and Avis & Toussaint among other references.  All of these
consider only a restricted class of polygons and all are attempting to
find the optimal (or close approximate) cover.  However, the only hint
at a general solution I've seen are references to the "GENCOV" algorithm

by Hegedus [A. Hegedus.  Algorithms for covering polygons by rectangles.

_Computer Aided Design_, 14(5), 1982].  To date I have been unsuccessful

in locating this article or any elaboration on the algorithm.

Any assistance in finding additional references, algorithms, or code is
greatly appreciated.

 
 
 

Any general rectangle covering algorithms?

Post by Ric » Sun, 01 Apr 2001 05:42:02


[Please do not mail me a copy of your followup]



Quote:>Is there an algorithm (no matter how inefficient) for covering any
>general polygon (allowing holes) with rectangles?

You can consider scan conversion an algorithm that covers a general
polygon with rectangles that happen to be squares the size of a
pixel.
--
Ask me about my upcoming book on Direct3D from Addison-Wesley!
Direct3D Book <http://www.xmission.com/~legalize/book/>
         Home <http://www.xmission.com/~legalize/>
    Fractals! <http://www.xmission.com/~legalize/fractals/>

 
 
 

Any general rectangle covering algorithms?

Post by Tim Tyle » Sat, 07 Apr 2001 21:37:24


: Is there an algorithm (no matter how inefficient) for covering any
: general polygon (allowing holes) with rectangles?

Not enough information:

Are you trying to use the minimum number of rectangles?

If not, the problem is easy...

I recommend you say in more detail what the constraints are: what
"allowing holes means", whether the rectangles can overlap, etc.
--
__________
 |im |yler  Try my latest game - it rockz - http://rockz.co.uk/

 
 
 

Any general rectangle covering algorithms?

Post by Choose Anonymit » Sun, 08 Apr 2001 06:05:14


I'm trying to find an algorithm to solve the general version of the
"rectangle covering
problem" of computational geometry.

1) The polygon is any general 2-D polygon.  It is very common for a
subset of
polygons to be discussed in this context.  For example, there are
numerous papers
discussing rectangle covering of "rectilinear" polygons (those with only
90 degree
angles).  There are also a few papers discussing "convex" polygons
(those with
interior angles of 90 degrees or more).

2) "With holes" means the polygon can have a polygonal "gap" in its
interior.  For
example, if you transformed a donut into a 2-D polygon, you would have a
polygon
with a hole.  This presents challenges to the covering algorithm.

3) In general "covering" problems mean that the shapes can overlap,
whereas
"partitioning" problems mean that the shapes cannot overlap.  I'm
interested in the
covering problem.

4) While the "rectangle covering problem" is generally concerned with
finding the
minimum number of rectangles, I'm interested in any proposed solution
(the fewer
rectangles the better).

I appreciate your response and look forward to your next post.

  :I recommend you say in more detail what the constraints are: what
  :"allowing holes means", whether the rectangles can overlap, etc.

 
 
 

Any general rectangle covering algorithms?

Post by Amitava Dat » Sun, 08 Apr 2001 15:28:56


: I'm trying to find an algorithm to solve the general version of the
: "rectangle covering
: problem" of computational geometry.

: 1) The polygon is any general 2-D polygon.  It is very common for a
: subset of
: polygons to be discussed in this context.  For example, there are
: numerous papers
: discussing rectangle covering of "rectilinear" polygons (those with only
: 90 degree
: angles).  There are also a few papers discussing "convex" polygons
: (those with
: interior angles of 90 degrees or more).

: 2) "With holes" means the polygon can have a polygonal "gap" in its
: interior.  For
: example, if you transformed a donut into a 2-D polygon, you would have a
: polygon
: with a hole.  This presents challenges to the covering algorithm.

: 3) In general "covering" problems mean that the shapes can overlap,
: whereas
: "partitioning" problems mean that the shapes cannot overlap.  I'm
: interested in the
: covering problem.

: 4) While the "rectangle covering problem" is generally concerned with
: finding the
: minimum number of rectangles, I'm interested in any proposed solution
: (the fewer
: rectangles the better).

: I appreciate your response and look forward to your next post.

:   :I recommend you say in more detail what the constraints are: what
:   :"allowing holes means", whether the rectangles can overlap, etc.

Hi,

The partitioning problem (according to your definition) is NP-Hard even
for simple variants like rectilinear polygons and axes-parallel rectangles.
There are approximation algorithms, but I can't say how implementable those
are. A recent reference is :

A. Kumar and R. Hariharan, ``Covering rectilinear polygons with axis-parallel
 rectangles" ACM STOC '99.

I am not sure whether any solution for the covering problem (according to your
definition) exists if you don't allow your rectangles to go out of your polygon.
In other words, if you have an additional constraint that all the rectangles
should be inside the polygon that you are trying to cover. It is not difficult
to show that even for fairly simple polygons, you cannot cover them with
rectangles (axes-parallel or general) if you have this constraint.

If you allow your rectangles to go out of your polygon, one can give a simple
algorithm as follows :

Find the smallest bounding box for the polygon by computing the maximum x, minimum x,
maximum y and minimum y vertices. Now you have a rectangle which covers the
whole polygon. You can even partition it into smaller rectangles if you wish.

Hope this helps,
Amitava Datta

 
 
 

Any general rectangle covering algorithms?

Post by Choose Anonymit » Fri, 13 Apr 2001 05:19:51


[snip]

Quote:> I am not sure whether any solution for the covering problem (according to your
> definition) exists if you don't allow your rectangles to go out of your polygon.
> In other words, if you have an additional constraint that all the rectangles
> should be inside the polygon that you are trying to cover.

I neglected to mention the constraint of the covering problem that
concerns this:  The union of all the rectangles should be equal to the
original polygon.

Quote:> It is not difficult
> to show that even for fairly simple polygons, you cannot cover them with
> rectangles (axes-parallel or general) if you have this constraint.

This seems counter-intuitive to me.  I understand that a polygon with
one or more acute interior angles will have to be approximately covered,
but otherwise it seems like an exact covering should exist.  Do you have
an example where this is not true?
 
 
 

Any general rectangle covering algorithms?

Post by Stephan Rasenbergve » Fri, 13 Apr 2001 20:34:53




> > It is not difficult
> > to show that even for fairly simple polygons, you cannot cover them with
> > rectangles (axes-parallel or general) if you have this constraint.

> This seems counter-intuitive to me.  I understand that a polygon with
> one or more acute interior angles will have to be approximately covered,
> but otherwise it seems like an exact covering should exist.  Do you have
> an example where this is not true?

Well.. I guess he(/she?) means examples like triangles:

|\    
| \  
|__\

you can only aproximate this by rectangles, like:

|\    
|#\  
|##\

but as you can notice the upper corner (as a triangle itself) is still not
covered. And mathematicly this can go upto infinite..

But when your application is limited to integer values (such as pixels on
your computer screen), you can have the entire set of rectangles.
I guess this is what you want?

: Is there an algorithm (no matter how inefficient) for covering any
: general polygon (allowing holes) with rectangles?
I don't know about any general alg. which is available, but you create
one yourself.

One thing that may help you is keping track of the holes/material using
the basics of a scanline alg. With this I mean you first order all your
coordinates on y and x and traverse this (link-)list keeping track of
material inside/outside on each `scanline' :

 0,10          <--- scanline 2
  |\    
  | \  
  |__\         <--- scanline 1
0,0  10,0

link-list --> (0,0;10,0;0,10)

scanline 2 --> outside (0,10) outside
scanline 1 --> outside (0,0) inside (10,0) outside

With this you have an easier task to create rectangles between scanline 1
and 2, based on where material is `inside'.

Start with the largest enclosing rectangle and fill up the holes..

--
Stephan.

 
 
 

1. Clever rectangle in rectangle clipping algorithm...

Hi,
  IS there a well known algorithm to clip rectangles to rectangles?  Im
looking for something along the lines of the cohen-sutherland
alogorithm for clipping lines to rectangles....

thanks you.
--

-re

  ########################################################################
  #                            Ramiro Estrugo                            #

  #                  http://www.fateware.com/~restrugo                   #
  ########################################################################

2. how to draw "bresenham Arc" ?

3. Rectangle in Rectangle Algorithm

4. Paper References Needed for CG Reading Course

5. How Tell if a Rectangle Covered?

6. newbie: Question about bouble buffering.

7. minimum number of rectangles covering largest area

8. reducing colordepth

9. Minimum rectangles to cover a polygon

10. Finding a minimal square covering rectangles

11. Text cannot be covered by filled rectangle?

12. Algorithm to find minimal circle which covers an irregular polygon

13. Layout algorithm for general graphs???