1

All values here are real numbers with up to two floating point digits.

Suppose we have a rectangular area, 100.0 by 75.0.

Then you are given a set of rectangles. How can I check whether these rectangles, united, cover the entire area?

If we have

(0,0,50,75)

clearly this does not happen since it only covers half the area. If we have

(0,0,50,75)
(50,0,50,75)

Then this does work, since both rectangles will effectively cover the whole (100,75).

What have I tried

I attempted (didn't work) to make a multi-dimensional array of booleans:

bool area[10000][7500];

These are the dimensions of the area, multiplied by 100 so that I don't have to deal with the floating points. Then I just iterate each of my rectangles (their values also multiplied by 100), and for each "pixel" in them, I turn the boolean to true.

Ultimately, I check if all booleans in the area are true.

This proved to be very dumb. Can you help me find a better way to do this?

Saturn
  • 17,888
  • 49
  • 145
  • 271
  • 1
    Do you need to check if their surfaces add up to the surface of the main rectangle or you need to check if every pixel of the main rectangle is covered? (gave you a hint there) – Shomz Apr 23 '13 at 23:13
  • @Shomz: I'm not sure what the first one means :(. But yes, essentially, just need to check if all pixels in the main rectangle are covered. – Saturn Apr 23 '13 at 23:16
  • 1
    (0,0,50,75) (50,0,50,75) doesn't work – use (50,0,100,75) – James Waldby - jwpat7 Apr 23 '13 at 23:16
  • Sounds like a Depth buffer in open GL. Your graphics card would love to do this for you. Your method isn't "dumb" as it's the first I would attempt. Of course, what does that make me? :) – Michael Dorgan Apr 23 '13 at 23:18
  • Yeah, the matrix approach is fine, though I really like @500's optimization - basically a matrix made not of pixels, but of rectangles (those that do exist, and if needed, the "in-betweeners"). – Shomz Apr 23 '13 at 23:19
  • You could try tackling this via 2D bin packing algo here: https://en.wikipedia.org/wiki/Bin_packing_problem – Bhargav Apr 24 '13 at 03:20
  • @BhargavBhat It looks like you're given the coordinates of the rectangles, so I don't think bin packing applies. – Bernhard Barker Apr 24 '13 at 08:08
  • @Dukeling Ah, I see. I understood it as sizes of the rectangles and the area to be covered is given. – Bhargav Apr 24 '13 at 08:17

3 Answers3

4

I think a strategy like this will work:

  1. Throw away any rectangles that are completely outside your area
  2. Split your area in smaller rectangles along the edges of the rectangles in the list relative to one axis
  3. Split the list of area rectangles created in step 2 along the edges of the rectangles in the cover list relative to the other axis
  4. You now have two lists of rectangles where there must be one in the cover list that covers each of the area rectangles completely
500 - Internal Server Error
  • 28,327
  • 8
  • 59
  • 66
2

I believe your "bitmap" attempt failed because of the (usual) floating point rounding problems. Unfortunately there's little you can do about it.

Now for the algorithm proper, I would approach it using a subtraction technique.

  • Let's call your initial set of rectangles R.
  • Initialize a second set of rectangles S that initially contains a single rectangle covering the whole area.
  • For each rectangle in R:
    • For each rectangle in S:
      • If the two R and S rectangles intersect, replace the S rectangle with as many rectangles as needed (0 to 4 if I'm not mistaken) that cover the non-intersecting part left from the S rectangle.
      • Continue iterating over S, taking care not to compute anything for the new S rectangles you just added (which we already know don't intersect with the current R rectangle).
    • Continue iterating over R, this time taking the new S rectangles into account, until either:
      • There is no rectangle left in S, in which case your R rectangles do cover the whole area.
      • Or, you iterated over all R rectangles and there are still S rectangles left, in which case your R rectangles don't cover the whole area.

As for the complexity, I'm not sure how it compares to @500-Internal-Server-Error or @Tommy's solutions but hey, at least I managed to come up with something, which I didn't think I could when I read your question at first -- I'm usually not very good at spatial stuff. :)

syam
  • 14,701
  • 3
  • 41
  • 65
1

A conceptually very similar approach to 500 - Internal Server Error's that avoids the O(n^2) search implied by the final step is:

  1. build a list of the vertical boundaries of every rectangle from the covering set;
  2. supposing that makes n boundaries, you've got n+1 vertical strips to consider on the source rectangle;
  3. for each strip, get the list of all rectangles that overlap it (you can do this in O(n) time by pushing from the rectangles to the bins rather than searching backwards);
  4. sort the lists from left to right (ie, O(n log n));
  5. go through the sorted list and try to find a gap where one span ends and nothing else begins until a little later (another O(n) task).

If you find a suitable gap then the original isn't covered. If you don't then it is. And this is essentially how span buffering works, by the way.

Tommy
  • 99,986
  • 12
  • 185
  • 204