假设你有一个顶点的三角形任意A,B和C。本文(第4.2节)说,您可以通过以下顶点的凸组合P从三角形内均匀生成一个随机点ABC:
A
B
C
P
ABC
P = (1 - sqrt(r1)) * A + (sqrt(r1) * (1 - r2)) * B + (sqrt(r1) * r2) * C
其中r1和r2是从中统一得出的[0, 1],sqrt是平方根函数。
r1
r2
[0, 1]
sqrt
您如何证明在三角形内 均匀分布 的采样点ABC呢?
编辑
正如对mathoverflow问题的评论中指出的那样, Graphical Gems讨论了该算法。
您具有从单位正方形到三角形的映射P(r1,r2)。均匀选择r1和r2会在单位平方中给出一个随机点。三角形中的图像根据映射P的雅可比行列式进行分布,结果证明它是一个常数。因此,图像分布也均匀。
实际上,要验证这一点,您只需要检查三分之一的非共线点A,B,C。仿射线性图具有恒定的Jacobian值,因此您可以应用其中的一个将任意三元组移到该标准位置,而不会影响分布。
最后,一个关于“为什么”的词:考虑由平行于BC边的线段填充的三角形。在P的公式中,变量r1选择该点将位于哪个线段,而r2确定该点在该线段上的位置。为了均匀起见,应平等对待给定线段上的所有点(因此在r2中为线性)。但是对于r1,由于某些片段比其他片段短,我们需要偏爱较长的片段,以实现均匀分布。公式中的sqrt(r1)对此进行了说明。