在矩形区域内均匀生成随机点(某些矩形可能重叠)

Question

假设它给出了一组具有不同区域的矩形,并且一些矩形可能重叠.目标是在矩形区域之间生成均匀的随机点.

Rectangle被定义为一对两点:

• (x1,y1) - 最左下角;
• (x2,y2) - 最右上角.

我在不重叠矩形之间均匀分布随机点的策略是, - 根据区域随机选择一个矩形(现有解决方案):

   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;
   }

然后在矩形内生成任意点:

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

但如果一些矩形可以重叠怎么办？

Answer 1

如果第一个预处理步骤足够快，这是一个简单且非常快速的解决方案（假设矩形的整数坐标小于 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)

这个想法是将矩形分成正方形。然后随机选择正方形并在该正方形内随机生成一个点。