CODEWITHSUNDEEP
algorithmmathrandomprobabilityuniform-distribution
Zhandos
Zhandos

Reputation: 279

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

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:

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:

But how to be if some of rectangles could overlap?

Upvotes: 6

Views: 2549

Answers (2)

AnT stands with Russia
AnT stands with Russia

Reputation: 320709

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.

Upvotes: 2

Rusty Rob
Rusty Rob

Reputation: 17213

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.

Upvotes: 2

Related Questions