Efficient algorithm for finding a point not affected by a set of rectangles

Question

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

Output: a point that none of the rectangles contains.

What is an efficient algorithm for this? The only two that I can think of right now are as follows:

• Create an array of buffers 1600x1200. Iterates over the area of ​​each rectangle, designating these bits as True. Iterate at the end and find the False bit. The problem is that it takes memory and can be slow.
• Iterate randomly through points. For each point, swipe through the rectangles and see if any of them contain a point. Return the first point that does not contain any of the rectangles. The problem is that it is really slow for tightly populated problem instances.

Why am I doing this? This is not for homework or for programming competitions, although I think that a more complex version of this question was asked on one (each rectangle had a “color”, and you had to output the color of several points that they gave you). I'm just trying to programmatically disable a second monitor in Windows, and I'm having problems with a more reasonable approach . Therefore, my goal is to find an unallocated space on the desktop, and then simulate a right-click, and then simulate all the clicks necessary to disable it in the screen properties window.

Answer 1

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

Sort the list, first Y, then X.

Go through the list. Overlapping runs must be contiguous, so you can combine them.

When you find the first run that does not stretch across the screen, you are done.

Answer 2

• I would highlight the image with my favorite graphics library and let me draw a rectangle.
• First, you can try the low resolution option (reduce the factor of 8), which will work if there is an area with a size of 15x15. If this fails, you can try high resolution.
• Use Windows HRGN ( Region in .net). For this they were invented. But this is not an agnostic language no.
• Finally, you can do the subtraction of the rectangle. The only problem is that you can get up to 4 rectangles each time you subtract one rectangle from another. If there are many small ones, this can get out of hand.

PS: Consider optimizing for maximized windows. Then you can say that there are no visible pixels without impact testing.

Answer 3

• Sort all X-coordinates (the beginning and end of the rectangles), plus 0 and 1600, remove duplicates. We denote this by Xi (0 <= i <= n).
• Sort all Y-coordinates (the beginning and end of the rectangles) plus 0 and 1200, removing duplicates. Denote this by Yj (0 <= j <= m).
• Make an n * m grid with the given Xi and Yj from the previous points, this should be much smaller than the original 1600x1200 (unless you have a thousand rectangles, in which case this idea does not apply). Each point in this grid displays a rectangle in the original 1600 x 1200 image.
• Color the rectangles in this grid: find the coordinates of the rectangles in the sets from the first steps, color in the grid. Each rectangle will be in the form (Xi1, Yj1, Xi2, Yj2), so you draw all the points (x, y) in the small grid such that i1 <= x <i2 && j1 <= y <j2.
• Find the first unpainted cell in the grid, take any point from it, for example, the center.

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

Nore2: Sets Xi and Yj can be stored in a sorted array or tree for O (log n) access. If the number of rectangles is large.

Answer 4

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

Note that 1600x1200 is smaller than 2M pixels. Is it really that much memory? If you use a bitvector, you only need 235k.

Answer 5

You first idea is not so bad ... you just need to change the presentation of the data. You can be integrated into a sparse array of booleans.

A language-specific solution is to use Area (Java) .

Answer 6

If I had to do this myself, I would probably go for a 2d array of logic elements (especially with a reduced scale, for example, using jdv or using accelerated graphics routines) or an arbitrary point approach.

If you really wanted to make a smarter approach, you can simply consider the rectangles. Start with a rectangle with angles (0,0), (1600,1200) = (lx, ly), (rx, ry) and subtract the first window (wx1, wy1) (wx2, wy2).

This can generate a maximum of 4 new "still available" rectangles if they are completely contained in the original free rectangle: (for example, all 4 corners of the new window are contained in the old one), they (lx, ly) - (rx, wy1), (lx , wy1) - (wx1, wy2), (wx2, wy1) - (rx, wy2) and (lx, wy2) - (rx, ry). If only the corner of the window overlaps (only one corner is inside the free rectangle), it splits it into two new rectangles; if the side (2 angles) in it are divided into 3; and if there is no coincidence, nothing changes. (If all axes are aligned, you cannot have 3 angles inside).

So, continue the loop through the windows, checking the intersection and dividing rectangles until you have a list (if any) of the remaining free space in terms of the rectangles.

This will probably be slower than any of the above approaches to the graphics library, but it would be more interesting to write :)

Answer 7

• Keep a list of rectangles representing 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 coverage rectangle and add smaller rectangles (if any) to the uncovered list.
• If your uncovered space list still has any entries, they contain all points not covered by the given rectangles.

It does not depend on the number of pixels in your area, so it will work for large (or infinite) resolutions. Each new rectangle in the uncovered list will have angles at unique intersections of pairs of other rectangles, so the list will have at most O (n ^ 2), which will give the total execution time O (n ^ 3). You can make it more efficient by keeping a list of unclosed rectangles for a better structure to check each coverage rectangle.

Answer 8

This is a simple solution with only spatial complexity of 1600 + 1200, it is essentially similar to creating a 1600x1200 matrix, but without using an entire matrix:

• Start with two Boolean arrays W [1600] and H [1200] set to true.
• Then, for each visible rectangle of the window with the coordinate ranges w1..w2 and h1..h2, mark W [w1..w2] and H [h1..h2] false.
• To check if a point with coordinates (w, h) falls into empty space, just check, (W [w] & H [h]) == true