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?

Why does it matter to you if the point is contained in multiple overlapping rectangles? — Jim Mischel, Apr 04 '18 at 21:05
@JimMischel The aim is generating uniformly a random point among rectangles' areas. — Zhandos, Apr 05 '18 at 03:51
Uniformly select a point in the bounding rectangle, repeat until it is inside one of the rectangles. — peterchen, Apr 05 '18 at 12:39

score 2 · Answer 1 · answered Apr 05 '18 at 04:50

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.

if there are too many squares, check out line sweeping rectangles: https://www.topcoder.com/community/data-science/data-science-tutorials/line-sweep-algorithms/ — Rusty Rob, Apr 05 '18 at 19:47

AnT stands with Russia · Answer 2 · 2018-04-05T13:03:06.907

An industrial-grade solution would be

Merge all rectangles into orthogonal polygons. These polygons do not overlap.
Decompose the polygons obtained at step 1 into non-overlapping rectangles.
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.

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

2 Answers2