6

假设给定一组具有不同区域的矩形，并且一些矩形可能重叠。目标是在矩形区域之间生成一个均匀的随机点。

矩形被定义为一对两点：

  • (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))。

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

4

2 回答 2

2

如果第一个预处理步骤足够快（假设矩形是小于等于 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)

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

于 2018-04-05T04:50:36.350 回答
2

工业级解决方案将是

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

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

于 2018-04-05T12:32:37.257 回答