Re: Covering rectangles in 2D

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

I meant 2 on each axis.


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.

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.


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.


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


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.


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.


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.


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.


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


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.


- Tim
.

Relevant Pages

  • 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: 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)
Quantcast