Random Rectangles without Overlapping some Pixels

I want to generate random rectangles. That is a pretty easy task. The issue is I need them to not overlap with any of these black dots:

Inverted for ease of sight:

Now I can just tell it to ignore any rectangles it generates if it overlaps with any black dots, but as the dot density increases, it gets to bogosort levels of inefficiency. Is there a more efficient way to do this?

1. Generate random line segment (that does not pass through any point) (green line on attached image)
2. Find distance to closest point on each side of the rectangle (red lines)
3. Choose random two points on the red lines that will belong to the sides of the rectangle (yellow dots)

1. Select a random white point.

2. Find the nearest black dot. This will be the radius of a circle

3. Create a circle centered at the random point.

4. Choose 2 points on the circle. Find their opposite point that pass by the center of the circle draw the rectangle from the 4 points.

P.S. Just be sure that the 2 points are not the diameter of the circle...

Here's my idea that is slightly different than what others have proposed. Here's the algorithm:

1. Create 2 arrays for the x and ys of the points. Copy the x and ys over and sort the arrays increaesingly.
2. Create a random x and random y. This will be the upper-left corner of the rectangle. Let's call them x1 and y1.
3. Do a binary search in the x array for the smallest x such that x >= x1.
4. Do a binary search in the y array for the largest y such that y <= y1.
   • if x1 == x or y1 == y: go to step 2 Note: we can't expand to create a rectangle.
5. Create a random x between x1 and the right bound x you found in step 3, exclusive on both ends. Call it x2.
6. Create a random y between y2 and the lower bound y you found in step 4, exclusive on both ends. Call it y2.
7. Save (x1, y1) and (x2, y2) as the left-upper and right-lower corners of your rectangle.
8. Repeat from step 2.

This algorithm has an initial time complexity of O(n * log n) and space complexity of O(n) for the preparation phase, where n is the number of given points. Each rectangle creation has a O(log n) time complexity for the binary search. I assume that the probability of collision between the left-upper corner of the rectangle and a point is so low that we can disregard it.

This approach also allows you to update the points in logarithmic time if you choosee the right data structure for them (something like a sorted map, sorted list, or similar depending on what it is called in a specific language).

You could use multiple randomly-generated quadtrees to generate a list of axis-aligned bounding boxes that do not contain any points, and then for each rectangle, randomly select an AABB from the list and then randomly generate a rectangle inside the AABB.

You don't need to retain the quadtree structure because you are only interested in the leaf nodes (which are AABBs). Start off with an AABB enclosing your entire 2D space and write a recursive function that accepts an AABB and a list of points. Create an empty list of AABBs and then call the function with the top-level bounding box and the point list.

Inside the function, randomly select one of the points to use as a splitting line, and randomly select an orientation (horizontal or vertical) or alternate horizontal and vertical. Create two lists of points made up of the points above and below the X or Y value of the splitting point, and two AABBs by splitting the AABB parameter using the point, then recursively call the function twice. If the function is called with an empty point list then add the AABB to your list and stop recursing.

If you call this from the top level multiple times you will have a whole bunch of overlapping AABBs in your list (provided the splitting points are selected randomly), so there won't be any obvious artifacts in the random generation. You can then randomly generate as many rectangles as you want.

The setup will be O(N log N) on the number of points (in the average case), and the random rectangle generation will be O(1).

To make the distribution more even, you could calculate the area of each AABB in your list and weight the probability of randomly selecting it based on its size. If you used a binary search tree to map your raw random number to your weighted AABBs, it would make your random generation O(log N)