random - 通过将三角形分成更小的部分来对三角形进行均匀采样？

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

好的，我有一些想法并相信使用准随机数可以提高三角形覆盖范围的“均匀性”，而无需分割为更小的三角形。 Quasirandom sampling如 Wiki 文章所示，使用 Sobol 序列可以提供更好的覆盖范围。

这是使用标准 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)