每日算法 — 使用java实现泊松盘采样：Bridson快速采样与均匀分布生成

泊松盘采样（Poisson Disk Sampling）生成空间中均匀分布且互不重叠的随机点集，任意两点间距不小于半径 $r$，同时避免传统网格采样的人工规律性。该算法广泛应用于纹理合成、物体分布、光照采样、地形生成等计算机图形学场景。Robert Bridson于2007年提出的 $O(n)$ 算法使其实时化成为可能。

算法原理

核心思想

1. 活性列表（Active List）：维护一个待处理的采样点队列
2. 局部随机探测：对每个活性点，在其环形区域 $[r, 2r]$ 内随机生成候选点
3. 冲突检测：候选点若与所有已有点距离 $\geq r$，则接受并加入活性列表
4. 活性失效：若某活性点周围 $k$ 次（通常 $k=30$）尝试均失败，则从活性列表移除

空间加速：背景网格

将空间划分为边长 $r/\sqrt{2}$ 的网格，每个网格最多容纳一个采样点。冲突检测只需检查候选点所在网格及其8邻域，将 $O(n)$ 距离计算降至 $O(1)$。

Java实现

import java.util.*;

/**
 * 二维泊松盘采样器（Bridson算法）
 * 生成均匀分布且最小间距为r的随机点集
 */
public class PoissonDiskSampler {

    private final double width, height;   // 采样区域
    private final double minDist;         // 最小间距 r
    private final int k;                  // 每点最大尝试次数
    private final Random random;

    // 背景网格：cellSize = r / sqrt(2)，每个格子最多一个点
    private final double cellSize;
    private final int gridW, gridH;
    private final List<double[]>[] grid;  // 每个格子存储点的索引
    private final List<double[]> points;  // 所有已采样点
    private final List<double[]> active;  // 活性列表

    @SuppressWarnings("unchecked")
    public PoissonDiskSampler(double width, double height, double minDist, int k, long seed) {
        this.width = width;
        this.height = height;
        this.minDist = minDist;
        this.k = k;
        this.random = new Random(seed);
        this.cellSize = minDist / Math.sqrt(2);
        this.gridW = (int) Math.ceil(width / cellSize);
        this.gridH = (int) Math.ceil(height / cellSize);
        this.grid = new ArrayList[gridW * gridH];
        for (int i = 0; i < grid.length; i++) grid[i] = new ArrayList<>();
        this.points = new ArrayList<>();
        this.active = new ArrayList<>();
    }

    /**
     * 执行采样，返回所有点坐标
     */
    public List<double[]> sample() {
        // 步骤1：随机放置第一个点
        double[] first = new double[]{random.nextDouble() * width, random.nextDouble() * height};
        addPoint(first);

        // 步骤2：迭代处理活性列表
        while (!active.isEmpty()) {
            // 随机选取一个活性点
            int idx = random.nextInt(active.size());
            double[] point = active.get(idx);
            boolean found = false;

            // 在环形区域 [r, 2r] 内尝试 k 次
            for (int i = 0; i < k; i++) {
                double[] candidate = generateCandidate(point);
                if (candidate != null && isValid(candidate)) {
                    addPoint(candidate);
                    found = true;
                    break;
                }
            }

            if (!found) {
                // 该点周围无可用空间，从活性列表移除
                active.remove(idx);
            }
        }
        return points;
    }

    /** 在点p的 [r, 2r] 环形区域内生成随机候选点 */
    private double[] generateCandidate(double[] p) {
        double angle = random.nextDouble() * 2 * Math.PI;
        double dist = minDist * (1 + random.nextDouble()); // [r, 2r]
        double x = p[0] + dist * Math.cos(angle);
        double y = p[1] + dist * Math.sin(angle);
        if (x < 0 || x >= width || y < 0 || y >= height) {
            return null;
        }
        return new double[]{x, y};
    }

    /** 检查候选点与邻近已有点的距离是否 >= r */
    private boolean isValid(double[] p) {
        int gx = (int) (p[0] / cellSize);
        int gy = (int) (p[1] / cellSize);

        // 只需检查周围5x5邻域（因为cellSize = r/sqrt(2)，两格外必 > r）
        for (int i = Math.max(0, gx - 2); i <= Math.min(gridW - 1, gx + 2); i++) {
            for (int j = Math.max(0, gy - 2); j <= Math.min(gridH - 1, gy + 2); j++) {
                for (double[] neighbor : grid[j * gridW + i]) {
                    double dx = p[0] - neighbor[0];
                    double dy = p[1] - neighbor[1];
                    if (dx * dx + dy * dy < minDist * minDist) {
                        return false; // 距离过近
                    }
                }
            }
        }
        return true;
    }

    /** 将点加入数据结构和活性列表 */
    private void addPoint(double[] p) {
        points.add(p);
        active.add(p);
        int gx = (int) (p[0] / cellSize);
        int gy = (int) (p[1] / cellSize);
        grid[gy * gridW + gx].add(p);
    }

    /** 计算采样密度（平均每单位面积点数） */
    public double getDensity() {
        return points.size() / (width * height);
    }

    /** 计算实际平均最近邻距离 */
    public double getAverageNearestDistance() {
        double total = 0;
        for (double[] p : points) {
            double minDistSq = Double.MAX_VALUE;
            for (double[] q : points) {
                if (p == q) continue;
                double dx = p[0] - q[0], dy = p[1] - q[1];
                minDistSq = Math.min(minDistSq, dx * dx + dy * dy);
            }
            total += Math.sqrt(minDistSq);
        }
        return total / points.size();
    }

    public static void main(String[] args) {
        // 在 100x100 区域内采样，最小间距 5
        PoissonDiskSampler sampler = new PoissonDiskSampler(100, 100, 5, 30, 42);
        List<double[]> samples = sampler.sample();

        System.out.printf("生成点数: %d%n", samples.size());
        System.out.printf("理论最大密度: %.4f%n", 2.0 / (Math.sqrt(3) * 5 * 5)); // 六方密堆积
        System.out.printf("实际采样密度: %.4f%n", sampler.getDensity());
        System.out.printf("平均最近邻距离: %.2f%n", sampler.getAverageNearestDistance());

        // 输出前10个点
        System.out.println("\n前10个采样点:");
        for (int i = 0; i < Math.min(10, samples.size()); i++) {
            double[] p = samples.get(i);
            System.out.printf("  (%.2f, %.2f)%n", p[0], p[1]);
        }
    }
}

算法特性对比

泊松盘采样在”自然感”与”均匀性”之间取得了最佳平衡，是游戏开发中树木、矿石、敌人分布的首选算法。

扩展应用

1. 三维空间：将背景网格扩展为三维，算法逻辑完全不变，用于体积云、粒子系统初始化
2. 加权泊松盘：根据密度图调整局部最小间距，实现山脉密集、平原稀疏的自然过渡
3. 渐进式采样：通过保留活性列表，支持运行时动态增删采样点，适用于开放世界流式加载
4. 边界约束：在 isValid 中加入多边形包含测试，可限制在任意形状区域内采样

泊松盘采样将严格的数学约束（最小间距）与高效的随机过程完美结合，是算法美学在图形学中的典范之作。