Efficient algorithm to find a point not touched by a set of rectangles

Question

Input: a set of rectangles within the area (0, 0) to (1600, 1200).

Output: a point which none of the rectangles contains.

What's an efficient algorithm for this? The only two I can currently think of are:

• Create a 1600x1200 array of booleans. Iterate through the area of each rectangle, marking those bits as True. Iterate at the end and find a False bit. Problem is that it wastes memory and can be slow.
• Iterate randomly through points. For each point, iterate through the rectangles and see if any of them contain the point. Return the first point that none of the rectangles contain. Problem is that it is really slow for densely populated problem instances.

Why am I doing this? It's not for homework or for a programming competition, although I think that a more complicated version of this question was asked at one (each rectangle had a 'color', and you had to output the color of a few points they gave you). I'm just trying to programmatically disable the second monitor on Windows, and I'm running into problems with a more sane approach. So my goal is to find an unoccupied spot on the desktop, then simulate a right-click, then simulate all the clicks necessary to disable it from the display properties window.

Answer 1

If you know the minimum x and y dimensions of the rectangles, you can use the first approach (a 2D array of booleans) using fewer pixels.

Take into account that 1600x1200 is less than 2M pixels. Is that really so much memory? If you use a bitvector, you only need 235k.

Answer 2

• I would allocate an image with my favorite graphics library, and let it do rectangle drawing.
• You can try a low res version first (scale down a factor 8), that will work if there is at least a 15x15 area. If it fails, you can try a high res.
• Use Windows HRGNs (Region in .net). They were kind of invented for this. But that's not language agnostic no.
• Finally you can do rectangle subtraction. Only problem is that you can get up to 4 rectangles each time you subtract one rect from another. If there are lots of small ones, this can get out of hand.

P.S.: Consider optimizing for maximized windows. Then you can tell there are no pixels visible without hit testing.

Answer 3

You first idea is not so bad... you should just change the representation of the data. You may be interessed in a sparse array of booleans.

A language dependant solution is to use the Area (Java).

Answer 4

If I had to do this myself, I'd probably go for the 2d array of booleans (particularly downscaled as jdv suggests, or using accelerated graphics routines) or the random point approach.

If you really wanted to do a more clever approach, though, you can just consider rectangles. Start with a rectangle with corners (0,0),(1600,1200) = (lx,ly),(rx,ry) and "subtract" the first window (wx1,wy1)(wx2,wy2).

This can generate at most 4 new "still available" rectangles if it is completely contained within the original free rectangle: (eg, all 4 corners of the new window are contained within the old one) they are (lx,ly)-(rx,wy1), (lx,wy1)-(wx1,wy2), (wx2,wy1)-(rx,wy2), and (lx,wy2)-(rx,ry). If just a corner of the window overlaps (only 1 corner is inside the free rectangle), it breaks it into two new rectangles; if a side (2 corners) juts in it breaks it into 3; and if there's no overlap, nothing changes. (If they're all axes aligned, you can't have 3 corners inside).

So then keep looping through the windows, testing for intersection and sub-dividing rectangles, until you have a list (if any) of all remaining free space in terms of rectangles.

This is probably going to be slower than any of the graphics-library powered approaches above, but it'd be more fun to write :)

Answer 5

For each rectangle, create a list of runs along the horizontal direction. For example a rectangle of 100x50 will generate 50 runs of 100. Write these with their left-most X coordinate and Y coordinate to a list or map.

Sort the list, Y first then X.

Go through the list. Overlapping runs should be adjacent, so you can merge them.

When you find the first run that doesn't stretch across the whole screen, you're done.

Answer 6

• Keep a list of rectangles that represent uncovered space. Initialize it to the entire area.
• For each of the given rectangles
  • For each rectangle in uncovered space
    • If they intersect, divide the uncovered space into smaller rectangles around the covering rectangle, and add the smaller rectangles (if any) to your list of uncovered ones.
• If your list of uncovered space still has any entries, they contain all points not covered by the given rectangles.

This doesn't depend on the number of pixels in your area, so it will work for large (or infinite) resolution. Each new rectangle in the uncovered list will have corners at unique intersections of pairs of other rectangles, so there will be at most O(n^2) in the list, giving a total runtime of O(n^3). You can make it more efficient by keeping your list of uncovered rectangles an a better structure to check each covering rectangle against.

Answer 7

• Sort all X-coordinates (start and ends of rectangles), plus 0 & 1600, remove duplicates. Denote this Xi (0 <= i <= n).
• Sort all Y-coordinates (start and ends of rectangles), plus 0 & 1200, remove duplicates. Denote this Yj (0 <= j <= m).
• Make a n * m grid with the given Xi and Yj from the previous points, this should be much smaller than the original 1600x1200 one (unless you have a thousand rectangles, in which case this idea doesn't apply). Each point in this grid maps to a rectangle in the original 1600 x 1200 image.
• Paint rectangles in this grid: find the coordinates of the rectangles in the sets from the first steps, paint in the grid. Each rectangle will be on the form (Xi1, Yj1, Xi2, Yj2), so you paint in the small grid all points (x, y) such that i1 <= x < i2 && j1 <= y < j2.
• Find the first unpainted cell in the grid, take any point from it, the center for example.

Note: Rectangles are assumed to be on the form: (x1, y1, x2, y2), representing all points (x, y) such that x1 <= x < x2 && y1 <= y < y2.

Nore2: The sets of Xi & Yj may be stored in a sorted array or tree for O(log n) access. If the number of rectangles is big.

Answer 8

This is a simple solution with a 1600+1200 space complexity only, it is similar in concept to creating a 1600x1200 matrix but without using a whole matrix:

1. Start with two boolean arrays W[1600] and H[1200] set to true.
2. Then for each visible window rectangle with coordinate ranges w1..w2 and h1..h2, mark W[w1..w2] and H[h1..h2] to false.
3. To check if a point with coordinates (w, h) falls in an empty space just check that (W[w] && H[h]) == true