Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
Perhaps books.google.com/… will help you. –  Shai Covo Jan 24 '11 at 12:48

3 Answers 3

up vote 9 down vote accepted

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.

share|improve this answer
1  
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)$.

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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