Re: Covering rectangles in 2D

On Sat, 22 Mar 2008 05:41:42 -0000, Tim Little
<tim@xxxxxxxxxxxxxxxxxxxxxxxxxx> wrote:

On 2008-03-22, quasi <quasi@xxxxxxxx> wrote:
But as far as I can see, you need to check every cell in a row (or
column), not just the one that generated the grid lines for that row
(or column).

Sort the x and y bounds of each rectangle, so that every rectangle is
associated with exactly two grid lines. (In the case of coinciding
grid lines, treat the grid cells between them as a region of zero area
which is not eligible for "uncovered" status)

Start at some cell. I chose the top left.

Do an O(N) check for how many rectangles cover that starting cell.
Keep track of this in a variable C that records the number of
rectangles covering the current cell.

Choose any path that covers the grid, crossing one grid line per step.
I chose a sweep back and forth: along each row, then down one cell,
then back along the next row in the opposite direction.

(Crossing any grid line gives the possibility of entering or leaving
at most the one, known, rectangle associated with that grid line.)

Check whether that rectangle boundary was actually crossed.
Increment, decrement, or leave C unchanged accordingly. This is an
O(1) operation.

If C = 0 for a cell with nonzero area, the area is not covered. If
instead the grid is exhausted, the area is covered.

If this is still too obscure, I could probably post code in some
programming language of your choice.

No, let me think about this.

Thanks.

quasi
.

Relevant Pages

  • Re: Covering rectangles in 2D
    ... since it seems you only care about grid lines that can be ... crossing from a cell to an adjoining cell, ... chose for each rectangle to define a grid line, ...
    (sci.math)
  • Re: Covering rectangles in 2D
    ... insure uniqueness. ... In other words, if 2 cells share a grid line, you ... crossing from a cell to an adjoining cell, ... chose for each rectangle to define a grid line, ...
    (sci.math)
  • RE: Help with developing sudoku gui using GDI+
    ... x/y mouse coordinates to indices in your array. ... Let's assume that your grid ... information like the number that is already filled in on the cell. ... the selected rectangle. ...
    (microsoft.public.dotnet.framework.drawing)
  • Re: Covering rectangles in 2D
    ... Sort the x and y bounds of each rectangle, ... associated with exactly two grid lines. ... crossing from a cell to an adjoining cell, ... Increment, decrement, or leave C unchanged accordingly. ...
    (sci.math)
  • Re: Rectangles
    ... going into one square, and stay in that square until -- we cross a grid ... The score for a given rectangle is the number of points where the ... the retangle has relatively prime sides, as assumed in this discussion, ...
    (sci.math)
Quantcast