18
$\begingroup$

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{r_1}) A + (\sqrt{r_1} (1 - r_2)) B + (r_2 \sqrt{r_1}) C$

where $r_1, r_2 \sim U[0, 1]$.

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

$\endgroup$
14
$\begingroup$

I would argue that if it is true for any triangle, it is true for all of them, as we can find an affine transformation between them. So I would pick my favorite triangle, which is $A=(0,0), B=(1,0), C=(0,1)$. Then the point is $(\sqrt{r_1}(1-r_2),r_2\sqrt{r_1})$ and we need to prove it is always within the triangle and evenly distributed. To be in the triangle we need $x,y\ge 0, x+y\le 1$, which is clear. Then show that the probability to be within an area $(0,x) \times (0,y)$ is $2xy$ by integration.

$\endgroup$
  • 2
    $\begingroup$ You mean 2xy, I think. $\endgroup$ – TonyK Jan 24 '11 at 9:19
  • $\begingroup$ @Tony K: Right. Fixed. $\endgroup$ – Ross Millikan Jan 24 '11 at 13:41
  • $\begingroup$ It's been quite a lot since I was doing this, but can someone post a full proof? Sry for necromancy, btw :) $\endgroup$ – ioreskovic Jun 26 '13 at 14:07
9
+100
$\begingroup$

Pick $A,B,C = (0,0),(1,0),(1,1)$. For any point $(x,y)$, we have that $(x,y)$ is in the triangle if and only if $0 < x < 1$ and $0 < y/x < 1$.

Now, we look for the distribution of $x$ and $y/x$.

Computing a few triangle areas, we can easily check that $P(0 < x < x_0) = x_0^2$. Hence $P(0 < x^2 < a) = P(0 < x < \sqrt a) = a$, so that $x^2$ is uniformly distributed in the unit interval.

Again with an area computations, we can check that $P(0 < y/x < k) = k$. Hence $y/x$ is also uniformly distributed in the unit interval.

Finally we have to check (again computing a simple area) that $P(0 < x < x_0 \land 0 < y/x < k) = x_0^2k$ which proves that $x^2$ and $y/x$ are independant.

So we have found that to generate a point uniformly in the triangle is the same as picking $x^2 = r_1$ and $y/x = r_2$ uniformly in the unit interval, and then form $(x,y) = (\sqrt r_1, r_2 \sqrt r_1)$, which is the barycenter of $(A,1- \sqrt {r_1})(B,\sqrt {r_1}(1-r_2))(C,\sqrt{r_1}r_2)$.

$\endgroup$
  • $\begingroup$ How to generalize it onto higher dimensions? What to do with arbitrary $n$-simplex? $\endgroup$ – Orient Jul 18 '14 at 17:54
  • $\begingroup$ If the dimension is $d$, first change your coordinates so that the simplex is formed by the points $(0,\ldots,0),(1,0,\ldots,0),\ldots,(1,\ldots,1,0),(1,\ldots,1)$. Then for the first coordinate, pick $x_1^d$ uniformly. Then pick $(x_2/x_1,x_3/x_1,\ldots,x_d/x_1)$ uniformly in the $d-1$-dimensional simplex (by induction) $\endgroup$ – mercio Jul 26 '14 at 14:47
  • $\begingroup$ merico, I think it is wrong. We need spatial uniform distribution. $\endgroup$ – Orient Jul 27 '14 at 6:25
  • $\begingroup$ One way to get random point inside of simplex $P = \{\mathbf{p}_i\}_{i = 1}^{d + 1}$ is to pick $\mathbf{c} = (c_1, c_2, ..., c_d, c_{d + 1}), c_i \sim U[0;1]$, then $\mathbf{c} \leftarrow -\log(\mathbf{c})$, then $c \leftarrow \displaystyle \frac{\mathbf{c}}{\sum \limits_{i = 1}^{d + 1} c_i}$, then random point is: $\displaystyle \sum \limits_{i = 1}^{d + 1}c_i \cdot \mathbf{p}_i$ (based on Dirichlet distribution and properties of affine transformations). $\endgroup$ – Orient Jul 27 '14 at 6:26
  • $\begingroup$ But the generalization of your approach itself is here math.stackexchange.com/questions/563129/… . $\endgroup$ – Orient Jul 27 '14 at 6:31
6
$\begingroup$

I'm starting with the argument provided by @Ross Millikan. Let $A=(0,0),\ B=(1,0),\ C=(0,1)$. Then the point chosen according to the given equation is $P=(X,Y)=(\sqrt{r_1}(1-r_2),r_2\sqrt{r_1})$. Now clearly, $0\leq X,Y \leq 1$ and $X+Y\leq \sqrt{r_1}\leq 1$. Now the problem is to show that $\mathbb{P}(X\leq x, Y\leq y)=2xy,\ \forall 0\leq x,y\leq 1$ with $x+y\leq 1$. Now, \begin{equation*} \begin{split} \mathbb{P}(X\leq x, Y\leq y)=& \mathbb{P}(\sqrt{r_1}(1-r_2)\leq x, r_2\sqrt{r_1}\leq y)\\ \ =&\int_{0}^1 \mathbb{P}(\sqrt{r}(1-r_2)\leq x, r_2\sqrt{r}\leq y|r_1=r)f_{r_1}(r)dr\\ \ =&\int_{0}^1 \mathbb{P}(1-\frac{x}{\sqrt{r}}\leq r_2\leq \frac{y}{\sqrt{r}})I_{[0,1]}(r)dr\ \mbox{(Since, $r_1, r_2$ are i.i.d $\mathcal{U}[0,1]$})\\ \end{split} \end{equation*} Now to find the region of integration we note that $$1-\frac{x}{\sqrt{r}}\leq r_2\leq \frac{y}{\sqrt{r}}\ \Rightarrow\ 0\leq r\leq(x+y)^2$$ Also, if $x\leq y$ then $$ r\in (0,x^2)\ \Rightarrow\ 1-\frac{x}{\sqrt{r}}\leq 0,\ \frac{y}{\sqrt{r}}\geq 1 \\ r\in (x^2,y^2)\ \Rightarrow\ 1-\frac{x}{\sqrt{r}}\geq 0,\ \frac{y}{\sqrt{r}}\geq 1 \\ r\in (y^2,(x+y)^2)\ \Rightarrow\ 1-\frac{x}{\sqrt{r}}\geq 0,\ \frac{y}{\sqrt{r}}\leq 1 \\$$ and if $y\leq x$ then $$ r\in (0,y^2)\ \Rightarrow\ 1-\frac{x}{\sqrt{r}}\leq 0,\ \frac{y}{\sqrt{r}}\geq 1 \\ r\in (y^2,x^2)\ \Rightarrow\ 1-\frac{x}{\sqrt{r}}\leq 0,\ \frac{y}{\sqrt{r}}\leq 1 \\ r\in (x^2,(x+y)^2)\ \Rightarrow\ 1-\frac{x}{\sqrt{r}}\geq 0,\ \frac{y}{\sqrt{r}}\leq 1 \\$$

Then if $x\leq 1$ the integral becomes $$\int_{0}^{x^2}1 dr+\int_{x^2}^{y^2}\frac{x}{\sqrt{r}} dr+ \int_{y^2}^{(x+y)^2}\left(\frac{x+y}{\sqrt{r}}-1\right) dr=2xy$$ Similarly, if $y\leq x$ the integral becomes $$\int_{0}^{y^2}1 dr+\int_{y^2}^{x^2}\frac{y}{\sqrt{r}} dr+ \int_{x^2}^{(x+y)^2}\left(\frac{x+y}{\sqrt{r}}-1\right) dr=2xy$$ Hence the point $P$ is uniformly distributed on the surface of the triangle $ABC$. $\hspace{3cm}\ \Box$

$\endgroup$
1
$\begingroup$

Note that these points, when random, will be uniformly distributed in a nicely random way, but if you loop through r1 and r2 with an increment (say .01) your resulting points will have unusual artifacts and not look randomly distributed. One end of the triangle may have few points.

I determined this with code ( Note that similar code, using math.Random() looks fine).

 FillTriangleWithPointsBarycentric
  if r1 and r2 are uniform random numbers between 0 and 1 then
 This math produces a uniform distribution (note √ means sqrt of)
 d = (1.0−√r1)*vector1 + √r1*(1.0−r2)*vector2+√r1 * r2 * vector3
 But rather than using a uniform random number, just loop through them and the result does not look good.
  @param {THREE.Vector3} vector1
 @param {THREE.Vector3} vector2
 @param {THREE.Vector3} vector3
 @param {Array<number>} output input/output points > [x0,y0,z0,x1,y1,z1,...xn,yn,zn] displayable in point cloud
 @returns {void}

FillTriangleWithPointsBarycentric(vector1, vector2, vector3, output) {

let triangle = new THREE.Triangle(vector1, vector2, vector3);
let area = triangle.getArea();
console.log('Area is ' + area);
area = Math.sqrt(area);
console.log('sqrt Area is ' + area);
let increment = 0.1 / area;
for (let r1 = 0; r1 <= 1; r1 += increment) {
  for (let r2 = 0; r2 <= 1; r2 += increment  ) {
    // of course this is javascript we have to write this out instead of
    // using only one line
    let sqrtR = Math.sqrt(r1);
    let A = (1 - sqrtR);
    let B = (sqrtR * (1 - r2));
    let C = (sqrtR * r2);
    let x = A * vector1.x + B * vector2.x + C * vector3.x;
    let y = A * vector1.y + B * vector2.y + C * vector3.y;
    let z = A * vector1.z + B * vector2.z + C * vector3.z;
    output.push(x, y, z);

  }
}
$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.