将三角形细分为较小的部分，实现均匀采样？

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 这样的库将其显式地细分为许多三角形。但是否有一种类似于正方形的隐式方式可以实现这一点，而不必实际分割三角形呢？

- Moody

---

有点不太清楚你在问什么。所以你是在三角形ABC定义的平面上均匀采样，对吗？所以你有一个例程，调用它并返回点（x，y）。“但是如果我想减少样本数量怎么办？”你不能事先减少样本数量吗？为什么？ - Severin Pappadeux

我不想完全依靠随机抽样。这将需要大量的样本才能在整个三角形上获得良好的分布。 - Moody

那么你是在谈论方差缩减技术吗？ - sascha

@sascha 但是在三角分布中它是均匀的，那么从哪里采样的重要性在哪里？ - Severin Pappadeux

好的，如果您不需要很多样本，那么细分如何帮助您？您仍然要求在部分上是均匀的，对吧？基本上，如果您有一个大三角形中的100个样本。您将其细分为2个小三角形，并在每个部分中采样50个点。我不明白会有什么不同的行为。好的，让我们询问澄清 - 究竟是在这个三角形上计算了什么？您正在使用那些采样的坐标做某些事情，对吧？ - Severin Pappadeux

这些样本代表我从三角形投射的光线起源。是的，你说得对，将其分成两个三角形不会改变任何东西。但是，如果你将其分成1000个三角形，你就会强制在每个地方生成光线。例如，你会强制在三角形的边缘生成光线，而不是希望随机采样会在边缘生成光线。我希望这能澄清事情？ - Moody

Answer 1

好的，我有一些想法并相信使用准随机数可以改善三角形覆盖中“均匀性”，而无需将其细分为较小的三角形。使用Sobol序列的准随机抽样可以提供更好的覆盖率，如维基百科文章所示。

这里是使用标准RNG（Python中的任何内容）的200个三角形内的点

这里是从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)

- Severin Pappadeux

---

这是一个非常好的方法。它看起来就像我需要的一样。感谢您的帮助！ - Moody

Answer 2

我建议使用泊松盘采样（短学术论文链接, 漂亮的可视化链接, 维基链接, 代码链接）在三角形的边界框内生成一个配置，然后裁剪到三角形边界限定的区域。

我建议从短学术论文开始。这里的原理非常容易理解。有很多这种想法的变体在外面流传，所以掌握它并找到适合自己的那个。

- Richard

---

Richard，这不是关于在三角形中均匀采样的问题。@Moody使用了正确的公式来在三角形中均匀采样点，请查看https://dev59.com/Vm445IYBdhLWcg3wnrgi以及其中的参考文献。 - Severin Pappadeux