Title: Solve Geometric Problems with C#

[This is a promo piece by Packt, the publisher of my book The Modern C# Challenge. It includes two of the 100 example problems and solutions in the book.]

Solve Geometric Problems with C#

Learn how to solve C# geometric problems in this article by Rod Stephens, a software developer, consultant, instructor, and author. Rod's popular C# Helper and VB Helper websites receive millions of hits per year and contain thousands of tips, tricks, and example programs for C# and Visual Basic developers. Do you wish to test your geometric programming skills?

If your answer is yes, this is the article for you. [This article was taken from Rod's book The Modern C# Challenge. Some of its chapters] ask you to calculate values such as π or the area below a curve. Others demonstrate useful techniques such as Monte Carlo algorithms. This article will look at two of the prominent geometric programming skills, the Monte Carlo π and Newton's π. You can also download the example solutions to see additional details and to experiment with the programs at https://github.com/PacktPublishing/The-Modern-CSharp-Challenge/tree/master/Chapter02.

So, let's get started!

1. Monte Carlo π

A Monte Carlo algorithm uses randomness to approximate the solution to a problem. Often, using more random samples gives you a more accurate approximated solution or gives a greater probability that the solution is correct.

For this problem, use a Monte Carlo algorithm to approximate π. To do this, generate random points in the square (0 ≤ X, Y ≤ 1) and then see how many fall within a circle centered in that square.

Solution:

// Use Monte Carlo simulation to estimate pi. private double MonteCarloPi(long numPoints) { Random rand = new Random(); // Make a bitmap to show points. int wid = pointsPictureBox.ClientSize.Width; int hgt = pointsPictureBox.ClientSize.Height; Bitmap bm = new Bitmap(wid, hgt); using (Graphics gr = Graphics.FromImage(bm)) { gr.Clear(Color.White); gr.DrawEllipse(Pens.Black, 0, 0, wid - 1, hgt - 1); } // Make the random points. int numHits = 0; for (int i = 0; i < numPoints; i++) { // Make a random point 0 <= x < 1. double x = rand.NextDouble(); double y = rand.NextDouble(); // See how far the point is from (0.5, 0.5). double dx = x - 0.5; double dy = y - 0.5; if (dx * dx + dy * dy < 0.25) numHits++; // Plots up to 10,000 points. if (i < 10000) { int ix = (int)(wid * x); int iy = (int)(hgt * y); if (dx * dx + dy * dy < 0.25) bm.SetPixel(ix, iy, Color.Gray); else bm.SetPixel(ix, iy, Color.Black); } } // Display the plotted points. pointsPictureBox.Image = bm; // Get the hit fraction. double fraction = numHits / (double)numPoints; // Estimate pi. return 4.0 * fraction; }

The method starts by creating a Random object that it can use to generate random numbers. It then creates a bitmap to fit the program's PictureBox, associates a Graphics object with it, clears the bitmap, and draws a circle centered in the bitmap.

Next, the code uses a loop to generate the desired number of random points within the square 0 ≤ X, Y < 1. The NextDouble method of the Random class returns a value between 0 and 1, so generating the point's X and Y coordinates is relatively easy.

The code then determines whether the point lies within the circle that fills the square 0 ≤ X, Y ≤ 1. To do this, the method calculates the distance from the random point to the center of the circle (0.5, 0.5). It then determines whether that distance is less than the circle's radius.

Actually, the code doesn't really find the distance between the point and (0.5, 0.5). To do this, it would use the distance formula to find the distance and then use the following equation to determine whether the result is less than the circle's radius 0.5:

Calculating square roots is relatively slow, however, so the program squares both sides of the equation and uses the following equation instead:

The value 0.5 squared is 0.25, so the program actually tests whether:

The program then plots the point on the bitmap in either gray or black, depending on whether the point lies within the circle. The code also uses the numHits variable to keep track of the number of points that lie within the circle.

After it finishes generating points, the code makes its approximation for π. The square 0 ≤ X, Y ≤ 1 has an area of 1.0 and the circle should have the area π R² where R is the circle's radius. In this example, R is 0.5, so the fraction of points that fall inside the circle should be the following:

If you solve this equation for π, you get the following:

The code gets the fraction of the points that fell within the circle, multiples that by 4.0, and returns the result as its estimate for π.

The following screenshot shows the MonteCarloPi example solution approximating π. After generating 10,000 random points, its approximation for π is off by around 1%. Using more points produces better approximations for π. The result with one million points is correct within about 0.1 0.2%, and the result with 100 million points is correct to within around 0.01%:

2. Newton's π/h2>

Various mathematicians have developed many different ways to approximate π over the years. Sir Isaac Newton devised the following formula to calculate π:

Use Newton's method to approximate π. Let the user enter the number of terms to calculate. Display the approximation and its error. How does this value compare to the fraction 355/113? Do you need to use checked blocks to protect the code?

Solution:

The following code implements Newton's method for calculating π:

// Use Newton's formula to calculate pi. private double NewtonPi(int numTerms) { double total = 0; for (int i = 0; i < numTerms; i++) { total += Factorial(2 * i) / Math.Pow(2, 4 * i + 1) / (Factorial(i) * Factorial(i)) / (2 * i + 1); } double result = 6 * total; Debug.Assert(!double.IsInfinity(result)); return result; }

This method simply loops over the desired number of terms, calculates the appropriate term values, and adds them to the result. To allow the program to work with larger values, it uses the following Factorial method:

// Return number! private double Factorial(int number) { double total = 1; for (int i = 2; i <= number; i++) total *= i; return total; }

This is a normal factorial, except it stores its total in a double variable, which can hold larger values than a long variable can.

The value 355/113 is approximately 3.1415929, which is remarkably close to π. Newton's method converges very quickly on values close to π, only needing nine terms before it is more accurate than 355/113.

This method runs into problems when numTerms is greater than 86. In that case, the value Factorial(2 * i) is too big to fit in a double variable. Because the problem occurs in a double variable instead of an integer, a checked block won't detect the problem.

As is the case with integers, C# doesn't notify you if the value doesn't fit in a double variable. Instead, it sets the variable equal to one of the special values double.Infinity or double.NegativeInfinity. The NewtonPi method uses a Debug.Assert statement to see if this happened.

The lesson to be learned here is that you should use the double.IsInfinity method to check double variables for overflow to infinity or negative infinity if that might be an issue.

Some double calculations, such as total = Math.Sqrt(-1), may result in the special value double.NaN, which stands for Not a Number. You can use the double.IsNaN method to check for that situation.

If you found this article interesting, you can explore The Modern C# Challenge to learn advanced C# concepts and techniques such as building caches, cryptography, and parallel programming by solving interesting programming challenges. The Modern C# Challenge helps you to walk through challenges in C# and explore the .NET Framework in order to develop program logic for real-world applications.