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?