在矩形区域内均匀生成随机点（有些矩形可能重叠）

Question

假设有一组面积不同的矩形，其中一些矩形可能重叠。目标是在矩形区域内生成均匀随机点。

矩形被定义为两个点的对：

- (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)).

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

- Zhandos

---

如果一个点包含在多个重叠的矩形中，对你有何影响？ - Jim Mischel

因为它破坏了统一性。 - Zhandos

你需要更好地解释一下。什么的一致性？ - Jim Mischel

@JimMischel 目标是在矩形区域内均匀生成随机点。 - Zhandos

在边界矩形中均匀地随机选择一个点，重复此过程直到它位于其中一个小矩形内。 - peterchen

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)

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

- Rusty Rob

---

如果有太多的正方形，请查看线扫描矩形：https://www.topcoder.com/community/data-science/data-science-tutorials/line-sweep-algorithms/ - Rusty Rob

Answer 2

一个工业级的解决方案是：

1. 将所有矩形合并为正交多边形。这些多边形不重叠。
2. 将步骤1中得到的多边形分解为非重叠的矩形。
3. 在这些非重叠的矩形中均匀选择您的点。

如果您用任何类型的三角剖分（如梯形分解后跟随三角剖分）替换第二步，然后从最终的三角形集中选择点，则此方法适用于任何可能重叠的多边形输入。

- AnT stands with Russia