Re: Covering rectangles in 2D

On Sun, 23 Mar 2008 03:14:33 -0000, Tim Little
<tim@xxxxxxxxxxxxxxxxxxxxxxxxxx> wrote:

On 2008-03-22, quasi <quasi@xxxxxxxx> wrote:
Why 2, why not 4?

I meant 2 on each axis.

OK, so each cell owns _all_ 4 of its grid lines. You use aliases to
insure uniqueness. In other words, if 2 cells share a grid line, you
make 2 separate versions of that grid line -- right?

Presumably, a grid line is the extension of a side of a rectangle --
yes?

Yes.

Also, since it seems you only care about grid lines that can be
_crossed_, there's no need to consider the sides of the outer
rectangle as grid lines -- right?

Correct, but in the original problem I thougth I remembered that the
rectangles were contained within the area to be checked for coverage.

Yes, but those outer grid lines can't be crossed, so while it's ok to
have them as grid lines, it's also ok to omit them, since they are
irrelevant to the count -- right?

Now the grid lines partition the big rectangle into cells, at most
(2n + 1)^2 of them, I think,
although if there are that many, then there will be empty cells, for
sure.

Yes.

In any case, O(n) cells. Correct so far?

O(n^2) cells, but I'm guessing that was just a typo.

Yes, I meant O(n^2) cells.

So when you talk about "crossing grid lines", I think you mean
crossing from a cell to an adjoining cell, moving either horizontally
or vertically -- right?

Yes.

It appears you want each grid line to be "owned" by one if its
bordering rectangles -- yes?

There are different ways to treat rectangles with aligned borders. I
chose for each rectangle to define a grid line, and that some grid
lines may have zero distance between them, and therefore that some
cells may have zero area.

Ok, so as I now understand it, every grid line is owned by a _unique_
bordering rectangle, since duplicate ownership has been avoided by
instead creating duplicate grid lines.

This is not clear. I can see that you don't want shared ownership,
but if the grid lines for some rectangle would coincide with an
already owned grid line, why not simply refuse to assign that
particular grid line to the new rectangle.

It's just an arbitrary choice.

Ok.

I could assign multiple rectangles to
one grid line, but then upon crossing a grid line I could then check
each assigned rectangle. This could be up to O(N) for some cells,
making it less clear that the algorithm is O(N^2) overall.

Exactly.

I don't see the need to create a duplicate grid line with empty
cells between them.

Just to make the O(1) complexity per cell clearer.

OK.

Do an O(N) check for how many rectangles cover that starting cell.

I don't see why the initial cell gets special treatment.

In theory it could be treated no differently from any other: examine
*every* cell inside or outside the area being considered. I just
chose to examine only cells within the area being examined. If it
makes the algorithm clearer, ignore that restriction.

Hmmm ... I'll have to come back to the above comment. For now, let's
go on.

Presumably, you have a separate C for each cell -- right?

In theory you could, but in practice we're only interested in whether
any cell is uncovered, not average coverage or any other such measure.
Re-using the same variable is fine.

Ok, so a single variable C for the whole grid.

The only thing you check for is whether you are entering or leaving
the owning rectangle for the grid line just crossed -- right?

Correct.

Now I'm lost. Suppose we start at cell (1,1) -- row 1, column 1, in
the top left hand corner

This is the first cell, so we do the O(N) count of how many rectangles
cover that cell. If it happens to be 0, we're done and can ignore the
rest of the algorithm. Otherwise C = C0 > 0.

Ok, I see.

, and cross into cell (1,2) -- row 1, column 2. Suppose the two
vertical grid lines for column 2 are owned by a 1x1 rectangle which
lives right there at cell (1,2). As you enter cell (1,2), the count
for that cell gets incremented.

OK, so now C = C0 + 1.

If you now proceed horizontally to cell (1,3), the count for cell
(1,2) gets decremented, so is now 0.

No, it is now C0 again, and C0 > 0 since otherwise we would have
stopped earlier.

Right.

I'm definitely confused about the C variable. Is there just one for
the whole grid, or one for each grid line, or one for each cell?

It's mathematically one per cell, but in a computer program I would
just re-use the same variable since we never care about what the
values were for any preceding cells.

I think it would actually be clearer to just hash out the points of
confusion. It would suffice to indicate the _first_ place where I've
seriously gone off course. I can then retry, starting from that point.
I'd like to understand this.

I think it's the step just before walking the grid: we initialize C to
be the count of rectangles overlapping the very first cell.

An alternative would be to just start with C=0 and walk all grid cells
whether they correspond to areas within the region of interest or not.

We would then only terminate the algorithm early when C=0 for a grid
cell that has both nonzero area and is within the region of interest.

Ok, but what does C represent?

It's not the count of the area covered so far, otherwise there would
be no need to decrement C. By the way, why not try to compute the
total area covered. Wouldn't your ownership scheme allow for a correct
"area covered" count? Then at the end, you could simply compare the
total area covered vs the area of the big rectangle.

In any case, for your variable C, I don't understand why C = 0 allows
you to conclude that the current cell can't be covered.

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
    ... 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: Grid and Array Association
    ... When all the calculations are completed, you want to put the total ... count for each date in the cell just below that date. ... Loop through GridArray assigning the date found at the top of the grid ... called dResult. ...
    (microsoft.public.vb.general.discussion)
  • Re: Grid and Array Association
    ... When all the calculations are completed, you want to put the total ... count for each date in the cell just below that date. ... Loop through GridArray assigning the date found at the top of the grid ... called dResult. ...
    (microsoft.public.vb.general.discussion)
  • Re: Grid and Array Association
    ... When all the calculations are completed, you want to put the total ... count for each date in the cell just below that date. ... Loop through GridArray assigning the date found at the top of the grid ... called dResult. ...
    (microsoft.public.vb.general.discussion)