小编典典

三角形中的样本随机点

algorithm

假设你有一个顶点的三角形任意ABC本文(第4.2节)说,您可以通过以下顶点的凸组合P从三角形内均匀生成一个随机点ABC

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

其中r1r2是从中统一得出的[0, 1]sqrt是平方根函数。

您如何证明在三角形内 均匀分布 的采样点ABC呢?

编辑

正如对mathoverflow问题的评论中指出的那样, Graphical
Gems讨论了该算法


阅读 911

收藏
2020-07-28

共1个答案

小编典典

您具有从单位正方形到三角形的映射P(r1,r2)。均匀选择r1和r2会在单位平方中给出一个随机点。三角形中的图像根据映射P的雅可比行列式进行分布,结果证明它是一个常数。因此,图像分布也均匀。

实际上,要验证这一点,您只需要检查三分之一的非共线点A,B,C。仿射线性图具有恒定的Jacobian值,因此您可以应用其中的一个将任意三元组移到该标准位置,而不会影响分布。

最后,一个关于“为什么”的词:考虑由平行于BC边的线段填充的三角形。在P的公式中,变量r1选择该点将位于哪个线段,而r2确定该点在该线段上的位置。为了均匀起见,应平等对待给定线段上的所有点(因此在r2中为线性)。但是对于r1,由于某些片段比其他片段短,我们需要偏爱较长的片段,以实现均匀分布。公式中的sqrt(r1)对此进行了说明。

2020-07-28