I will end this series of posts on generating uniformly random points inside geometric shapes by considering regular polygons. Regular polygons are equilateral and equiangular. When the number of sides is equal to 4 we have a square (it is fairly easy to generate uniformly distributed random points inside a square). As the number of sides goes to infinity we have a circle (I already showed how to generate uniformly distributed random points inside a circle here).
For all the other regular polygons with \(n\) sides you could use the technique presented in this paper to generate uniformly distributed random points. The paper is by Myron Hlynka and Deborah Loach from the Department of Mathematics and Statistics at University of Windsor in Canada.
Friday 9 November 2012
Uniformly Distributed Random Points Inside a Circular Ring
I will continue my series of posts on generating uniformly distributed points within different shapes by considering a circular ring (a.k.a. annulus or doughnut). Just like my previous post we have the joint probability density function (PDF) of the \(x\) and \(y\) coordinate of the random points as:
$$ f_{X,Y}(x,y)=
\begin{cases}
\frac{1}{A}=\frac{1}{\pi (R_{c_2}^2-R_{c_1}^2)} & R_{c_1}^2 \leq x^2+y^2 \leq R_{c_2}^2 \\
0 & \text{otherwise}
\end{cases},$$
where \(R_{c_2}\) is the radius of the outer circle and \(R_{c_1}\) is the radius of the inner circle, and \(R_{c_1}<R_{c_2}\)
Using a similar technique as in the previous post we have:
$$ f_{R,\Theta}(r,\theta) = \frac{1}{2\pi} \times \frac{2r}{R_{c_2}^2-R_{c_1}^2} = f_\Theta(\theta)f_R(r) $$
where
$$f_\Theta(\theta) = \frac{1}{2\pi} \text{ for } 0 \leq \theta \leq 2\pi$$
and
$$f_R(r)=\frac{2r}{R_{c_2}^2-R_{c_1}^2} \text{ for } R_{c_1} \leq r \leq R_{c_2}.$$
Therefore, \(\Theta\) is uniformly distributed between \(0\) and \(2\pi\). The random variable \(R\) can be generated by first calculating its cumulative distribution function as
$$ F_R(r) = \int_{R_{c_1}}^r \frac{2\alpha}{R_{c_2}^2-R_{c_1}^2}d\alpha = \frac{r^2-R_{c_1}^2}{R_{c_2}^2-R_{c_1}^2}, $$
and then using a uniformly distributed random variable \(U\) over the interval \([0,1]\) to get
$$ U = \frac{R^2-R_{c_1}^2}{R_{c_2}^2-R_{c_1}^2} \implies R = \sqrt{(R_{c_2}^2-R_{c_1}^2)U + R_{c_1}^2}. $$
The following MATLAB code generates 1000 random numbers inside a circular ring with outer radius \(20\), and inner radius \(10\) centered at \(-30\), \(-40\).
Rc2 = 20;
Rc1 = 10;
Xc = -30;
Yc = -40;
theta = rand(1,n)*(2*pi);
r = sqrt((Rc2^2-Rc1^2)*rand(1,n)+Rc1^2);
x = Xc + r.*cos(theta);
y = Yc + r.*sin(theta);
plot(x,y,'.'); axis square
$$ f_{X,Y}(x,y)=
\begin{cases}
\frac{1}{A}=\frac{1}{\pi (R_{c_2}^2-R_{c_1}^2)} & R_{c_1}^2 \leq x^2+y^2 \leq R_{c_2}^2 \\
0 & \text{otherwise}
\end{cases},$$
where \(R_{c_2}\) is the radius of the outer circle and \(R_{c_1}\) is the radius of the inner circle, and \(R_{c_1}<R_{c_2}\)
Using a similar technique as in the previous post we have:
$$ f_{R,\Theta}(r,\theta) = \frac{1}{2\pi} \times \frac{2r}{R_{c_2}^2-R_{c_1}^2} = f_\Theta(\theta)f_R(r) $$
where
$$f_\Theta(\theta) = \frac{1}{2\pi} \text{ for } 0 \leq \theta \leq 2\pi$$
and
$$f_R(r)=\frac{2r}{R_{c_2}^2-R_{c_1}^2} \text{ for } R_{c_1} \leq r \leq R_{c_2}.$$
Therefore, \(\Theta\) is uniformly distributed between \(0\) and \(2\pi\). The random variable \(R\) can be generated by first calculating its cumulative distribution function as
$$ F_R(r) = \int_{R_{c_1}}^r \frac{2\alpha}{R_{c_2}^2-R_{c_1}^2}d\alpha = \frac{r^2-R_{c_1}^2}{R_{c_2}^2-R_{c_1}^2}, $$
and then using a uniformly distributed random variable \(U\) over the interval \([0,1]\) to get
$$ U = \frac{R^2-R_{c_1}^2}{R_{c_2}^2-R_{c_1}^2} \implies R = \sqrt{(R_{c_2}^2-R_{c_1}^2)U + R_{c_1}^2}. $$
The following MATLAB code generates 1000 random numbers inside a circular ring with outer radius \(20\), and inner radius \(10\) centered at \(-30\), \(-40\).
%**********************************************n = 10000;
Rc2 = 20;
Rc1 = 10;
Xc = -30;
Yc = -40;
theta = rand(1,n)*(2*pi);
r = sqrt((Rc2^2-Rc1^2)*rand(1,n)+Rc1^2);
x = Xc + r.*cos(theta);
y = Yc + r.*sin(theta);
plot(x,y,'.'); axis square
%**********************************************
Uniformly Distributed Random Points Inside a Circle (2)
So much for posting the answer in a few days! Sorry, I have been Very Very busy.
So here is the answer. Lets assume we have the Cartesian coordinate system with (\(x,y\)) representing the points. Then joint probability distribution function (PDF) of our random points inside the circle (i.e. the joint distribution of random variable \(X\) and random variable \(Y\) representing the \(x\) and \(y\) coordinate of the random point) is given by:
$$ f_{X,Y}(x,y)=
\begin{cases}
\frac{1}{A}=\frac{1}{\pi R_c^2} & x^2+y^2 \leq R_c^2 \\
0 & \text{otherwise}
\end{cases},$$
where \(R_c\) is the radius of the circle.
Now lets consider the polar coordinate system where \(r=g_1(x,y)= \sqrt{x^2+y^2}\) and \(\theta=g_2(x,y)=\arctan (y/x)\). Also, from inverting the functions \(g_1\) and \(g_2\) we have \(x=h_1(r,\theta)=r\cos \theta\) and \(y=h_2(r,\theta)=r\sin\theta\). Now calculating the Jacobian of the transformation we have:
$$ J(x,y)= \det
\begin{bmatrix}
\frac{\partial r}{\partial x}=\frac{x}{\sqrt{x^2+y^2}} & \frac{\partial r}{\partial y}=\frac{y}{\sqrt{x^2+y^2}} \\
\frac{\partial \theta}{\partial x}=\frac{-y}{x^2+y^2} & \frac{\partial \theta}{\partial y}=\frac{x}{x^2+y^2}
\end{bmatrix}= \frac{1}{\sqrt{x^2+y^2}}=\frac{1}{r}.$$
Also we have
$$ |J(r,\theta)|=\frac{1}{|J(x,y)|}$$
The joint PDF of random variables \(R\) and \(\Theta\) can then be calculated using the joint PDF of \(X\) and \(Y\) as:
$$ f_{R,\Theta}(r,\theta)= f_{X,Y}\left( h_1(r,\theta),h_2(r,\theta) \right) =
\begin{cases}
\frac{r}{\pi R_c^2} & 0 \leq \theta \leq 2\pi, 0 \leq r \leq R_c \\
0 & \text{otherwise}
\end{cases}.$$
We can rewrite the non zero part as:
$$ f_{R,\Theta}(r,\theta) = \frac{1}{2\pi} \times \frac{2r}{R_c^2} = f_\Theta(\theta)f_R(r) $$
where
$$f_\Theta(\theta) = \frac{1}{2\pi}$$
and
$$f_R(r)=\frac{2r}{R_c^2}.$$
Therefore, \(\Theta\) is uniformly distributed between \(0\) and \(2\pi\). The random variable \(R\) can be generated by first calculating its cumulative distribution function as
$$ F_R(r) = \int_0^r \frac{2\alpha}{R_c^2}d\alpha = \frac{r^2}{R_c^2}, $$
and then using a uniformly distributed random variable \(U\) over the interval \([0,1]\) to get
$$ U = \frac{R^2}{R_c^2} \implies R=R_c \sqrt{U}.$$
The following MATLAB code generates 1000 random numbers inside a circle with radius \(20\) centered at \(-30\), \(-40\).
If you don't understand how I did the PDF transformation see
I hope this helps someone out there.
So here is the answer. Lets assume we have the Cartesian coordinate system with (\(x,y\)) representing the points. Then joint probability distribution function (PDF) of our random points inside the circle (i.e. the joint distribution of random variable \(X\) and random variable \(Y\) representing the \(x\) and \(y\) coordinate of the random point) is given by:
$$ f_{X,Y}(x,y)=
\begin{cases}
\frac{1}{A}=\frac{1}{\pi R_c^2} & x^2+y^2 \leq R_c^2 \\
0 & \text{otherwise}
\end{cases},$$
where \(R_c\) is the radius of the circle.
Now lets consider the polar coordinate system where \(r=g_1(x,y)= \sqrt{x^2+y^2}\) and \(\theta=g_2(x,y)=\arctan (y/x)\). Also, from inverting the functions \(g_1\) and \(g_2\) we have \(x=h_1(r,\theta)=r\cos \theta\) and \(y=h_2(r,\theta)=r\sin\theta\). Now calculating the Jacobian of the transformation we have:
$$ J(x,y)= \det
\begin{bmatrix}
\frac{\partial r}{\partial x}=\frac{x}{\sqrt{x^2+y^2}} & \frac{\partial r}{\partial y}=\frac{y}{\sqrt{x^2+y^2}} \\
\frac{\partial \theta}{\partial x}=\frac{-y}{x^2+y^2} & \frac{\partial \theta}{\partial y}=\frac{x}{x^2+y^2}
\end{bmatrix}= \frac{1}{\sqrt{x^2+y^2}}=\frac{1}{r}.$$
Also we have
$$ |J(r,\theta)|=\frac{1}{|J(x,y)|}$$
The joint PDF of random variables \(R\) and \(\Theta\) can then be calculated using the joint PDF of \(X\) and \(Y\) as:
$$ f_{R,\Theta}(r,\theta)= f_{X,Y}\left( h_1(r,\theta),h_2(r,\theta) \right) =
\begin{cases}
\frac{r}{\pi R_c^2} & 0 \leq \theta \leq 2\pi, 0 \leq r \leq R_c \\
0 & \text{otherwise}
\end{cases}.$$
We can rewrite the non zero part as:
$$ f_{R,\Theta}(r,\theta) = \frac{1}{2\pi} \times \frac{2r}{R_c^2} = f_\Theta(\theta)f_R(r) $$
where
$$f_\Theta(\theta) = \frac{1}{2\pi}$$
and
$$f_R(r)=\frac{2r}{R_c^2}.$$
Therefore, \(\Theta\) is uniformly distributed between \(0\) and \(2\pi\). The random variable \(R\) can be generated by first calculating its cumulative distribution function as
$$ F_R(r) = \int_0^r \frac{2\alpha}{R_c^2}d\alpha = \frac{r^2}{R_c^2}, $$
and then using a uniformly distributed random variable \(U\) over the interval \([0,1]\) to get
$$ U = \frac{R^2}{R_c^2} \implies R=R_c \sqrt{U}.$$
The following MATLAB code generates 1000 random numbers inside a circle with radius \(20\) centered at \(-30\), \(-40\).
%**********************************************
n = 10000;
Rc = 20;
Xc = -30;
Yc = -40;
theta = rand(1,n)*(2*pi);
r = Rc*sqrt(rand(1,n));
x = Xc + r.*cos(theta);
y = Yc + r.*sin(theta);
plot(x,y,'.'); axis square;
%**********************************************
If you don't understand how I did the PDF transformation see
Chapter 6 (6.2.3 to be exact) or
Chapter 8 (8.3 to be exact).
I hope this helps someone out there.
Wednesday 9 May 2012
Uniformly Distributed Random Points Inside a Circle
So I just started my blog and I already posted my first blog. Now I want to get my hand dirty by posting some math!
The problem I want to consider here is generation of uniformly distributed random points inside different geometric shapes. The simplest shape to consider is a rectangle. In this case, the generation of uniformly distributed random points is trivial. Let \(l\) be the length of the square, \(w\) be the width, and the point \(p_c(x_c,y_c)\) be the center of the rectangle. Let \(p_i(X,Y)\) be a random point inside the rectangle. Here \(X\) and \(Y\) are random variables. For \(p_i\) to be uniformly distributed, \(X\) must be a uniform distribution over the interval \(\left[ l-\frac{x_c}{2}, l+\frac{x_c}{2} \right] \), and \(Y\) must be a uniform distribution over the interval \(\left[ w-\frac{y_c}{2}, w+\frac{y_c}{2} \right] \). Well this is fairly trivial.
Now lets consider a circle. The problem is not as trivial. We define a circle by its radius \(r_c\) and the point representing its center \(p_c(x_c,y_c)\). For simplicity lets assume the center of the circle is on the origin (i.e. \(p_c(0, 0)\) ). The first guess that people typically give (which is wrong) is to use polar coordinates with \(r\) and \(\theta\) uniformly distributed over \(\left[ 0, r_c \right] \) and \(\left[ 0, 2\pi \right] \), respectively. The reason this turn out to be wrong is because the area of a circle with radius \(\frac{r_c}{2}\) and the area of a ring (or doughnut) with width \(\frac{r_c}{2}\) are not the same. What is the correct answer? (I will post the answer with derivation in a few days!)
See the answer here.
The problem I want to consider here is generation of uniformly distributed random points inside different geometric shapes. The simplest shape to consider is a rectangle. In this case, the generation of uniformly distributed random points is trivial. Let \(l\) be the length of the square, \(w\) be the width, and the point \(p_c(x_c,y_c)\) be the center of the rectangle. Let \(p_i(X,Y)\) be a random point inside the rectangle. Here \(X\) and \(Y\) are random variables. For \(p_i\) to be uniformly distributed, \(X\) must be a uniform distribution over the interval \(\left[ l-\frac{x_c}{2}, l+\frac{x_c}{2} \right] \), and \(Y\) must be a uniform distribution over the interval \(\left[ w-\frac{y_c}{2}, w+\frac{y_c}{2} \right] \). Well this is fairly trivial.
Now lets consider a circle. The problem is not as trivial. We define a circle by its radius \(r_c\) and the point representing its center \(p_c(x_c,y_c)\). For simplicity lets assume the center of the circle is on the origin (i.e. \(p_c(0, 0)\) ). The first guess that people typically give (which is wrong) is to use polar coordinates with \(r\) and \(\theta\) uniformly distributed over \(\left[ 0, r_c \right] \) and \(\left[ 0, 2\pi \right] \), respectively. The reason this turn out to be wrong is because the area of a circle with radius \(\frac{r_c}{2}\) and the area of a ring (or doughnut) with width \(\frac{r_c}{2}\) are not the same. What is the correct answer? (I will post the answer with derivation in a few days!)
See the answer here.
My First Blog!
I finally took the plunge! I started a blog. I have been thinking about it for a while but never got around to it. So here we are.
The blog will be mostly on scientific stuff including my own research, life as a graduate student (I am currently a Third year PhD student), the mystifying academic world, and other topics that are of interest to me. If you would like to get to know me better you can view my personal/academic website here.
The blog will be mostly on scientific stuff including my own research, life as a graduate student (I am currently a Third year PhD student), the mystifying academic world, and other topics that are of interest to me. If you would like to get to know me better you can view my personal/academic website here.
Subscribe to:
Posts (Atom)