ASU NSF RET Program
Lab (2) - Monte Carlo Simulation and Estimating Area of Shapes
Instructor: Dr. Rahman Tashakkori, CS @ Appalachian State University

In Lab(1) you learned about Excel basics. You were able to modify the cells using a formula and display your data as graphs. In this activity, we will utilize some other utilities of Excel. As we illustrated in the demo in class, Monte Carlo Simulations in various forms are used to determine the outcome the solution to problems that may not have a solution or their solutions are not easy to find.

Activity (1) - Producing a Circle of an Arbitrary Radius
How do we draw a circle using Scatter Plot option with data points that are generated on the edge of the circle?

By definition a point on a circle of radius defined by Radius is always Radius distance away from the center of the circle. Also, we know that in 2-D Cartesian Coordinate where a point is defined by its x and y coordinates, the relation:

Radius2 = x2 + y 2

We want to draw a circle in Excel using the Scatter Plot option. Thus, we need to generate some data points on the circle that are equally spaced and connect these points to get the circle. To do this we will generate the points that are spaced based on their angles. Then we will use the angle and radius to get the x and y values.

Basically, we generate the points in polar coordinate and translate them to x and y values. We know the a circle is 360 degree, so we create some angles between 0 to 360 some small degrees apart. For example we will generate angles between 0 and 360 that are 5 degree apart:
0 5 10 15 20 25 .... 350 355 360.

How do we generate this set of angles in Excel?
Open an Excel file, in Cell A4, type 0, and in A5 type 5. Highlight both of these cells using the left button, once highlighted, drag the small square at the bottom right-hand-side of the highlighted square and drag it down until you get 360. We have used the automatic fill option in which Excel uses the patters of the first two cells to fill the rest. here the patters was that the two points were 5 units apart and thus the rest of the points are created that way.

Label Cell A2 by typing Radius in that cell and name the Cell B2 as Radius. Now that you have named the cell Radius type 4 in that cell for our Radius.

Now we have defined a Radius and generated some angles between 0 to 360 in column A. We will generate x and y values based on these angles.

To generate, the values for x, go to B4 and there type the formula to generate x:

Note that we have multiplied the angle by Pi/180 to convert to Radian which is the default used in Excel. Since cos(0) is 1, if you press enter, you should get a value that is the same as the Radius. In Cell C4, compute the value for y by typing:

Since sin(0) is 0, then the y value is 0 for this one.

Now highlight B4 and C4 and drag the small square at the bottom right-hand-side all the way to the end to copy the formula to all the cells up to 360. A small part of the spread sheet is shown below.

Now that we have the set of x and y data points, let's plot them in a Scatter Plot. Highlight all the x and y data points and click on Insert at the top, and plot them as a Scatter Plot. You will get a plot that looks like this.

After a little cleaning, by modifying the format for the x and y axes, we can get the appears more like a circle.

Then modify the min and max on both x and y axes.

And we can even use the mouse to make the drawing area a perfect square to get:

To re-cap, we were able to draw a circle by following these steps:
1) Defined a radius for the circle and named a Cell as Radius and set that to a value. Here we chose radius to be 4.
2) Generated some angles that were equally spaced between 0 and 360. Here we generated angles between 0 and 360 every 5 degree intervals and stored them in Column A
3) Computed x values using x = Radius*cos(angle) and stored them in Column B
4) Computed y values using y = Radius*sin(angle) and stored them in Column C
5) Plotted the x and y values as a Scatter Plot
6) Modified the format of the x and y axes and played with the frame to get a nice looking circle.

Now that we created a circle, let's do something interesting with it. Assume for the moment that we didn't know what the value of PI was. Since area of circle is defined as:

If we somehow we could find the area of circle, then we could use: PI = ACircle/Radius2

So, how do we estimate the area of a circle? Look at the last image we displayed above. You have a square that tightly surround the circle. Hint, we know the area of that square, it is ASquare =Radius*Radius. If we know the ratio of the area of the circle to that of the square, then we can multiply that by the area of square, and find the area of the circle. Something like this:

ACircle = (Ratio of circle to square)*area of square

We will drop random points on the square and will count those that have fallen on the circle. If we do a good job in creating random points in the square then we get a get a ratio of the number that fell on the circle to that fell on the square.

(Number of points on the Square / Number of points on the Circle) = (Area of Square / Area of Circle)
(NSquare / NCircle ) = (ASquare / ACircle )

and we can use this to find the area of circle:

ACircle = (NCircle / NSquare )*ASquare
PI = 4* (NCircle / NSquare )

Let's try to drop some random points on the 4-by-4 square we had in the plot above, and since we already have a circle there, count the number of points.

Our points must have x values between -4 to 4 and y values between -4 to 4. To generate a random point between -4 to 4, we utilize the random generator in Excel that produces a random number between 0 and 1 and then scale the number to the -4 to 4 range.

You can clearly see that in this formula when rand() is 0, then the x will be -Radius, which is -4. And if the rand() is 1, then x = -Radius + 2Radius = Radius, which is 4. So we managed to scale the random numbers between 0 and 1 to that between -4 and 4.

3) Highlight D4 and E4 and then copy these two all the way to Row 23.
4) Now we have 20 random x and y values and we need to get them into the plots. Right click on the boarder of the plot, and on the boundary of the plot, right click on Select Data to add the new data on the same plot:

5) In the new screen that looks like this:

We need to add a new Series, so click on Add Series, to get a frame like this:

Then on Series X values, click on the small box with a red mark in the middle on the right-hand-side of the blank field and then go to the spreadsheet and highlight from D4 to D23, and once done click on the small box again to go back to the spreadsheet.
Repeat the same thing for the Series Y Values, and this time highlight E4 to E23.
Then click on Ok, once done.
This will produce a plot like this:

But we don't want the dots inside to be connected, so right click on one of the lines and click on Format Data Series, then click on Line Color, and then choose No Line, then click on Close. The new plot will look like this:

We have created 20 points, out of which 14 are inside. So the estimate for area is:
PI = (14/20)*4 = 1.42*4 = 2.8
Not a good estimate, but remember we have only used 20 data points.

With 2000 data points, I got 3.124.

Going Beyond

This is a powerful technique and can be used to measure the area of unknown shapes. I have used a slightly different version of the technique to measure the area of an unknown shape. To do this, I have put the unknown shape on a regular 8.5-by-11 paper and took a picture. Then save the picture as a JPEG file. I am hoping that I can bring this to Excel and, then drop random points on the two and calculate the ratio of the points on the unknown shape to the total number of points. I can use this ratio to compute the area of unknown shape.

I used 50 random points and came up with something like this:

How do we do this? Any guess?

Step 1: The paper is 8.5 on x and 11 on y, so we can generate random numbers for x between 0 to 8.5. Also we can generate random numbers between 0 to 11.

Step 2: We plotted the points in a Scatter Plot.

Then I used the Format Chart Area --> Fill Option --> Picture or texture fill.
Then I used File to find the image I had taken from the paper and the unknown shape and set the transparency level to 60%. Then clicked on Close.

Step 3: Click in the middle of the plot, Format Plot Area --> No Fill --> Close.

Now you should see a plots with the image as its background. You can count the points on the unknown area and estimate the area of the unknown shape.

We hope you enjoyed this lab.