如何在含重叠区域的矩形集合中均匀生成随机点？

Great question! When dealing with overlapping rectangles, the core problem with your existing non-overlapping approach is that overlapping regions get counted multiple times—so if you just weight by individual rectangle areas, points in overlaps will be sampled more frequently than they should be for a uniform distribution. Here are two practical approaches to fix this:

方法一：预处理合并为无重叠子矩形（高效多次采样） #

This approach works best if you need to generate many random points. We first split the union of all rectangles into a set of non-overlapping sub-rectangles, then use your familiar area-weighted selection on this new set.

步骤拆解： #

1. 收集所有关键坐标：

   • 收集所有矩形的x1和x2坐标，去重后排序；同理处理所有y1和y2坐标。
   • 这些坐标会把平面分割成大量微小的轴对齐矩形，每个小矩形要么完全处于原矩形的并集范围内，要么完全在范围外。

2. 筛选有效子矩形：

   • 遍历每个微小矩形，检查它是否被至少一个原矩形覆盖。
   • 保留所有被覆盖的微小矩形，它们就构成了无重叠的子矩形集合。

3. 采样（复用无重叠逻辑）：

   • 计算所有有效子矩形的总面积。
   • 生成一个0到总面积之间的随机数r。
   • 累加子矩形的面积，直到累加值超过r，这个子矩形就是选中的目标。
   • 在选中的子矩形内生成均匀随机点：
     • x = 子矩形.x1 + 随机数 * (子矩形.x2 - 子矩形.x1)
     • y = 子矩形.y1 + 随机数 * (子矩形.y2 - 子矩形.y1)

示例代码（Java风格）： #

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;

class Rectangle {
    double x1, y1, x2, y2;
    public Rectangle(double x1, double y1, double x2, double y2) {
        this.x1 = x1; this.y1 = y1; this.x2 = x2; this.y2 = y2;
    }
    public double getArea() {
        return (x2 - x1) * (y2 - y1);
    }
    public boolean contains(double x, double y) {
        return x >= x1 && x < x2 && y >= y1 && y < y2;
    }
}

public class OverlappingRectSampler {
    private List<Rectangle> nonOverlappingSubRects;
    private double totalArea;
    private Random random = new Random();

    public OverlappingRectSampler(List<Rectangle> originalRects) {
        this.nonOverlappingSubRects = generateNonOverlappingSubRects(originalRects);
        this.totalArea = nonOverlappingSubRects.stream().mapToDouble(Rectangle::getArea).sum();
    }

    private List<Rectangle> generateNonOverlappingSubRects(List<Rectangle> originalRects) {
        List<Double> xCoords = new ArrayList<>();
        List<Double> yCoords = new ArrayList<>();

        // 收集所有唯一的x、y坐标
        for (Rectangle rect : originalRects) {
            xCoords.add(rect.x1);
            xCoords.add(rect.x2);
            yCoords.add(rect.y1);
            yCoords.add(rect.y2);
        }
        Collections.sort(xCoords);
        Collections.sort(yCoords);

        List<Rectangle> subRects = new ArrayList<>();

        // 遍历网格中的微小矩形
        for (int i = 0; i < xCoords.size() - 1; i++) {
            double xLeft = xCoords.get(i);
            double xRight = xCoords.get(i+1);
            if (xRight <= xLeft) continue; // 跳过零宽度的矩形

            for (int j = 0; j < yCoords.size() - 1; j++) {
                double yBottom = yCoords.get(j);
                double yTop = yCoords.get(j+1);
                if (yTop <= yBottom) continue; // 跳过零高度的矩形

                Rectangle tinyRect = new Rectangle(xLeft, yBottom, xRight, yTop);
                // 检查该微小矩形是否被原矩形覆盖
                boolean isCovered = false;
                for (Rectangle rect : originalRects) {
                    if (rect.contains((xLeft + xRight)/2, (yBottom + yTop)/2)) {
                        isCovered = true;
                        break;
                    }
                }
                if (isCovered) {
                    subRects.add(tinyRect);
                }
            }
        }
        return subRects;
    }

    public double[] samplePoint() {
        double r = random.nextDouble() * totalArea;
        double accumulatedArea = 0;

        for (Rectangle rect : nonOverlappingSubRects) {
            accumulatedArea += rect.getArea();
            if (accumulatedArea >= r) {
                double x = rect.x1 + random.nextDouble() * (rect.x2 - rect.x1);
                double y = rect.y1 + random.nextDouble() * (rect.y2 - rect.y1);
                return new double[]{x, y};
            }
        }
        // 兜底逻辑（正常不会走到这里）
        return new double[]{0, 0};
    }
}

方法二：拒绝采样（简单实现，适合少量采样） #

If you don't need to generate thousands of points, rejection sampling is way simpler to code. The idea is straightforward:

1. 找到能包含所有原矩形的包围盒。
2. 在包围盒内生成随机点。
3. 检查该点是否在任意一个原矩形内，若是则保留；若不是则重复生成，直到得到有效点。

示例代码（Java风格）： #

public class RejectionSampler {
    private List<Rectangle> rects;
    private double minX, maxX, minY, maxY;
    private Random random = new Random();

    public RejectionSampler(List<Rectangle> rects) {
        this.rects = rects;
        // 计算包围盒
        minX = rects.stream().mapToDouble(r -> r.x1).min().orElse(0);
        maxX = rects.stream().mapToDouble(r -> r.x2).max().orElse(0);
        minY = rects.stream().mapToDouble(r -> r.y1).min().orElse(0);
        maxY = rects.stream().mapToDouble(r -> r.y2).max().orElse(0);
    }

    public double[] samplePoint() {
        while (true) {
            double x = minX + random.nextDouble() * (maxX - minX);
            double y = minY + random.nextDouble() * (maxY - minY);
            // 检查点是否在任意矩形内
            for (Rectangle rect : rects) {
                if (rect.contains(x, y)) {
                    return new double[]{x, y};
                }
            }
        }
    }
}

注意事项： #

• 如果原矩形的并集面积远小于包围盒面积（比如几个小矩形分散在很大的空间里），拒绝采样的效率会很低。
• 它非常适合采样次数少，或者原矩形几乎填满包围盒的场景。

内容的提问来源于stack exchange，提问作者Zhandos