Assignment 6: Monte Carlo

Due: 2:00pm, Thursday, October 1. Value: 30 pts. Submit to Sauron.

Suppose we want to determine the area of a complicated figure with several line segments. One way to do this is to divide the shape into several triangles, pull out a ruler, and apply the formula for a triangle's area b h / 2 to each triangle. But this can be quite complicated for a shape bounded by several line segments.

Another technique for determining the area of a figure uses randomness. Here, we'll draw a rectangle around the figure; the area of this rectangle is easy to determine using a ruler. Then we'll toss lots of points at random locations into the rectangle. If i of the k points fall into the figure in question, and the bounding rectangle has an area of A_rect, then the area of the figure is approximately (i / k) A_rect. If we try 10 points, and 3 fall inside the figure, then we would estimate the figure's area to be 30% of the rectangle's area. When the number of sample points is small, this isn't a very precise estimate; but it grows more accurate with many sample points. The advantage of the technique is that it works regardless of the shape whose area we're trying to estimate.

(This technique is called Monte Carlo estimation. Monte Carlo is a well-known gambling destination in Europe, and the technique is named after it because the technique depends on randomness.)

Your assignment is to write a program that reads a shape from the user (using the starter code described below) and then applies Monte Carlo estimation using 100 sample points. You should draw each of the 100 sample points as small circles, which should be green for those that lie in the shape and red for the others. You should then display the estimated area. Here is a sample run of the program, where we enter four points to arrive at the shape diagrammed on this page.

First point? 200,100          These points are the vertices for the yellow polygon.
Next point? 300,388           The code I provide below asks these questions and
Next point? 225,275           creates the polygon.
Next point? 100,400
Next point?                   An empty line terminates the input
The area is estimated to be 18000.0

I have already started this program to handle reading and displaying a shape from the user. To use this starter program, right-click the link MonteCarlo.java, select Save Link As… or Save Target As… from the pop-up menu, and save the file on your computer. Then select Open… from Jigsaw's File menu and open the file you just saved.

This program represents the user's shape using the GPolygon class. We have not seen this class yet, but its objects have the following two methods that are useful for this assignment.

GRectangle getBounds(): Returns the bounding box for this polygon, encapsulated in a GRectangle object. The GRectangle class provides getX, getY, getWidth, and getHeight methods to determine the rectangle's location and size.
boolean contains(double x, double y): Returns true if the point (x,y) lies inside this polygon.