generate a random point within rectangles' areas uniformly (some rectangles could overlap)

Question

Assume it's given a set of rectangles with different areas and some rectangles could overlap. Objective is generating of a uniform random point among rectangles' areas.

Rectangle is defined as a pair of two points:

• (x1,y1) - bottom leftmost corner;
• (x2,y2) - top rightmost corner.

My strategy for uniform distribution of a random point among not overlapped rectangles is that,- randomly select a rectangle based on areas (existing solution):

   for(int i = 0; i < rectangles.length; i++) {
      int area = (rectangles[i].x2 - rectangles[i].x1) * 
                 (rectangles[i].y1 - rectangles[i].y2);
         if(rand.nextInt(total + area) >= total) {
             selected = i;
             break;
         }
         total += area;
   }

Then generate an arbitrary point within a rectangle:

• x1 +(1/(x2-x1))*rand(0,(x2-x1-1)),
• y1 +(1/(y2-y1))*rand(0,(y2-y1-1)).

But how to be if some of rectangles could overlap?

Answer 1

Here is a simple and very fast solution if the first preprocessing step is fast enough (assumes rectangles are integer coordinates less than say.. 1000):

squares = set()
for rect in rects:
    for oneByOneSquare in rect:
        squares.add(oneByOneSquare)

squares = list(squares)
while True:
    randomSquare = random.choice(squares)
    randomPoint = randomPointInsideSquare(randomSquare)

The idea is to partition the rectangles into squares. Then randomly select squares and the randomly generate a point within that square.

Answer 2

An industrial-grade solution would be

1. Merge all rectangles into orthogonal polygons. These polygons do not overlap.
2. Decompose the polygons obtained at step 1 into non-overlapping rectangles.
3. Select your point uniformly in these non-overlapping rectangles.

This approach is applicable to any input of potentially overlapping polygons, if you replace the second step with any kind of triangulation (like trapezoidal decomposition followed by triangulation) and then select the point from the final set of triangles.