# uniform random point in triangle

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$?

-

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.

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

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)$.

-
How to generalize it onto higher dimensions? What to do with arbitrary $n$-simplex? – Orient Jul 18 '14 at 17:54
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) – mercio Jul 26 '14 at 14:47
merico, I think it is wrong. We need spatial uniform distribution. – Orient Jul 27 '14 at 6:25
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). – Orient Jul 27 '14 at 6:26
But the generalization of your approach itself is here math.stackexchange.com/questions/563129/… . – Orient Jul 27 '14 at 6:31

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$

-