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

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.