通过将三角形分成更小的部分来均匀采样三角形？

Question

要均匀采样三角形ABC，我可以使用以下公式：

P = (1 - sqrt(r1)) * A + (sqrt(r1)*(1 - r2)) * B + (r2*sqrt(r1)) * C

其中 r1 和 r2 是介于 0 和 1 之间的随机数。您采集的样本越多越好。但是，如果我想获得更好的分布，同时保持较低的样本数量怎么办？

例如，如果我有一个正方形，我可以隐式地将它分成 N x N 网格，并在较小的网格正方形内生成一个随机样本。像这样：

float u = (x + rnd(seed)) / width;
float v = (y + rnd(seed)) / height;

重点是我强制采样以较低的采样分辨率覆盖整个网格。

如何用三角形实现这一点？我能想到的唯一方法是使用像 Triangle 这样的库将它明确地细分为多个三角形。但是有没有一种方法可以像使用正方形一样隐式地执行此操作，而不必实际划分三角形？

Answer 1

我建议使用泊松圆盘采样 (short academic paper link, pretty visualization link, wiki link, code link) 在三角形的边界框内生成配置，然后裁剪到三角形边界的区域。

我建议从简短的学术论文开始。这里的工作原理很容易理解。这个想法有许多种变体，因此请了解它并找到适合您的那个。

Answer 2

好的，我有一些想法并且相信使用准随机数可以提高 "uniformity" 三角形覆盖范围，而无需细分为更小的三角形。 Quasirandom sampling 使用 Sobol 序列可以提供更好的覆盖率，如 Wiki 文章中所述。

这是使用标准 RNG 的三角形中的 200 个点（无论它在 Python 中是什么）

这是从 Sobol 2D 序列中采样的 200 个点的图片

我看起来好多了。 Python 代码

import os
import math
import random

import numpy as np
import matplotlib.pyplot as plt

import sobol_seq

def trisample(A, B, C, r1, r2):
    s1 = math.sqrt(r1)

    x = A[0] * (1.0 - s1) + B[0] * (1.0 - r2) * s1 + C[0] * r2 * s1
    y = A[1] * (1.0 - s1) + B[1] * (1.0 - r2) * s1 + C[1] * r2 * s1

    return (x, y)

if __name__ == "__main__":
    N = 200

    A = (0.0, 0.0)
    B = (1.0, 0.0)
    C = (0.5, 1.0)

    seed = 1
    xx = list()
    yy = list()
    random.seed(312345)
    for k in range(0, N):

        pts, seed = sobol_seq.i4_sobol(2, seed)
        r1 = pts[0]
        r2 = pts[1]

        # uncomment if you want standard rng
        #r1 = random.random()
        #r2 = random.random()

        pt = trisample(A, B, C, r1, r2)
        xx.append(pt[0])
        yy.append(pt[1])

    plt.scatter(xx,  yy)
    plt.show()

    sys.exit(0)

通过将三角形分成更小的部分来均匀采样三角形？

Uniform sampling of a triangle by dividing it into smaller parts?

random

triangulation