在三角形中采样随机点 [英] sample random point in triangle

问题描述

假设您有一个任意三角形，其顶点为 A、B 和 C.这篇论文(第4.2节)说可以生成随机点，P，均匀地从三角形ABC内通过以下顶点的凸组合:

Suppose you have an arbitrary triangle with vertices A, B, and C. This paper (section 4.2) says that you can generate a random point, P, uniformly from within triangle ABC by the following convex combination of the vertices:

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

其中r1和r2统一由[0, 1]绘制，sqrt为正方形根函数.

where r1 and r2 are uniformly drawn from [0, 1], and sqrt is the square root function.

你如何证明在三角形ABC内均匀分布的采样点是正确的?

How do you justify that the sampled points that are uniformly distributed within triangle ABC?

编辑

正如对数学溢出问题的评论中指出的那样，Graphical Gems 讨论此算法.

As pointed out in a comment on the mathoverflow question, Graphical Gems discusses this algorithm.

推荐答案

你有一个从单位正方形到三角形的映射 P(r1,r2).均匀地选择 r1 和 r2 在单位正方形中给出一个随机点.三角形中的图像是根据映射 P 的雅可比行列式分布的，它是一个常数.因此图像分布也是均匀的.

You have a map P(r1,r2) from the unit square to your triangle. Choosing r1 and r2 uniformly gives a random point in the unit square. The image in the triangle is distributed according to the Jacobian determinant of the map P, which turns out to be a constant. Therefore the image distribution is also uniform.

实际上，要验证这一点，您只需要检查它的三重非共线点 A、B、C.仿射线性映射具有常数雅可比行列式，因此您可以应用其中之一将任意三元组移动到此标准位置，而不会影响分布.

Actually, to verify this you only need to check it for one triple of non-collinear points A,B,C. Affine linear maps have constant Jacobian so you can apply one of these to move an arbitrary triple into this standard position without affecting the distribution.

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

Finally, a word about "why": Consider the triangle as filled out by line segments parallel to the BC side. In the formula for P, the variable r1 selects which segment the point will lie on, while r2 determines where along the segment it will be. For uniformity, all points on a given segment should be treated equally (hence linear in r2). But for r1, since some segments are shorter than others, we need to favor the long segments in order to attain a uniform distribution. The sqrt(r1) in the formula accounts for this.

这篇关于在三角形中采样随机点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！