Generate a random point inside the rectangle areas evenly (some rectangles may overlap)

Question

Suppose that he is given a set of rectangles with different areas, and some rectangles may overlap. The task is to create a uniform random point among the areas of the rectangles.

A rectangle is defined as a pair of two points:

• (x1, y1) - lower left corner;
• (x2, y2) is the upper right corner.

My strategy for evenly distributing a random point among non-overlapping rectangles is to - 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 create an arbitrary point inside the rectangle:

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

But what if some of the rectangles may overlap?

Answer 1

Here is a simple and very quick solution if the first step of the preprocessing is fast enough (it is assumed that the 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 split the rectangles into squares. Then randomly select the squares and randomly generate a point inside this square.

Answer 2

Industrial solution will be

• Merge all rectangles into orthogonal polygons. These polygons do not overlap.
• Lay out the polygons obtained in step 1 into non-overlapping rectangles.
• Select your point evenly in these non-overlapping rectangles.

This approach applies to any input of potentially overlapping polygons if you replace the second step with any triangulation (for example, a trapezoidal decomposition followed by triangulation), and then select a point from a finite set of triangles.