|
|
Title | Use Newton's method on the equation Z^n - 1 to draw fractals in Visual Basic .NET |
Description | This example shows how to use Newton's method on the equation Z^n - 1 to draw fractals in Visual Basic .NET. |
Keywords | Newton's method, polynomial, root, function, fractal, VB .NET |
Categories | Algorithms, Graphics, VB.NET |
|
|
Newton's method calculates the roots of equations. In other words, it finds the values of X for which F(X) = 0. For more information on the part of the code that calculates Newton's method, see Use Newton's method to find the roots of an equation in Visual Basic .NET.
To draw a fractal, the program applies Newton's method to complex numbers in a region of the complex plane. It then colors each point in the region to indicate the root of the equation to which Newton's method leads for that point.
For example, the equation Z^4 - 1 has four roots (values of Z that make the equation zero): 1, -1, i, and -i.
To make the calculations easier to understand, the program uses the following Complex class.
|
|
Private Class Complex
Public Re As Double
Public Im As Double
Public Sub New(ByVal real_part As Double, ByVal _
imaginary_part As
Double)
Re = real_part
Im = imaginary_part
End Sub
Public Function Clone() As Complex
Return New Complex(Re, Im)
End Function
Public Function MagnitudeSquared() As Double
Return Re * Re + Im * Im
End Function
Public Function Magnitude() As Double
Return Sqrt(MagnitudeSquared)
End Function
Public Function Times(ByVal x As Complex) As Complex
Return New Complex(Re * x.Re - Im * x.Im, Re * x.Im _
+ Im * x.Re)
End Function
Public Function Times(ByVal new_re As Double, ByVal _
new_im As Double) As
Complex
Return New Complex(Re * new_re - Im * new_im, Re * _
new_im + Im *
new_re)
End Function
Public Function Plus(ByVal x As Complex) As Complex
Return New Complex(Re + x.Re, Im + x.Im)
End Function
Public Function Plus(ByVal new_re As Double, ByVal _
new_im As Double) As
Complex
Return New Complex(Re + new_re, Im + new_im)
End Function
Public Function DividedBy(ByVal denominator As Complex) _
As Complex
Dim conjugate As New Complex(denominator.Re, _
-denominator.Im)
denominator = denominator.Times(conjugate)
Dim numerator As Complex = Me.Times(conjugate)
numerator.Re /= denominator.Re
numerator.Im /= denominator.Re
Return numerator
End Function
Public Function IsCloseTo(ByVal x As Complex) As Boolean
Return Abs(Re - x.Re) + Abs(Im - x.Im) < 0.001
End Function
Public Overrides Function ToString() As String
If Im < 0 Then
Return Re.ToString() & " - " & _
Abs(Im).ToString() & "i"
Else
Return Re.ToString() & " + " & Im.ToString() & _
"i"
End If
End Function
End Class
|
|
The following code shows how the program calculates the function Z^N - 1 and
its derivative N * Z^(N - 1).
|
|
Private Const NUM_ROOTS As Integer = 7
Private m_Roots(NUM_ROOTS) As Complex
' The function.
' F(x) = x^NUM_ROOTS - 1.
Private Function F(ByVal x As Complex) As Complex
Dim result As Complex = x.Clone() ' x.
' x^NUM_ROOTS.
For i As Integer = 1 To NUM_ROOTS - 1
result = result.Times(x)
Next i
' x^NUM_ROOTS - 1.
Return result.Plus(-1, 0)
End Function
' The function's derivative.
' dFdx(x) = NUM_ROOTS * x^(NUM_ROOTS - 1).
Private Function dFdx(ByVal x As Complex) As Complex
Dim result As Complex = x.Clone() ' x.
' x^(NUM_ROOTS - 1).
For i As Integer = 1 To NUM_ROOTS - 2
result = result.Times(x)
Next i
' NUM_ROOTS * x^(NUM_ROOTS - 1).
Return result.Times(NUM_ROOTS, 0)
End Function
|
|
The following code draws the fractal. The code loops over the points in an
area and uses Newton's method to find a root of the equation starting with
that point as its initial guess. It then looks through a list of the
equation's roots to see which one it found and plots the point with a
corresponding color.
|
|
' Draw the fractal.
Private Sub DrawFractal()
' Do nothing when the form is initially created.
If Not m_FormVisible Then Exit Sub
' Do nothing if the canvas has zero size.
If picCanvas.ClientSize.Width < 1 Or _
picCanvas.ClientSize.Height < 1 Then Exit Sub
' Create the Bitmap and Graphic objects.
If Not (m_Graphics Is Nothing) Then
picCanvas.Image = Nothing
m_Graphics.Dispose()
m_Bitmap.Dispose()
End If
m_Bitmap = New Bitmap(picCanvas.ClientSize.Width,
picCanvas.ClientSize.Height)
m_Graphics = Graphics.FromImage(m_Bitmap)
' Clear the bitmap.
m_Graphics.Clear(Me.BackColor)
picCanvas.Image = m_Bitmap
picCanvas.Refresh()
' Work until the epsilon squared < this.
Const CUTOFF As Single = 0.0000001
' Adjust the coordinate bounds to fit picCanvas.
AdjustAspect()
Dim clr As Integer
Dim x0, x, epsilon As Complex
Dim dx, dy As Double
' dx and dy are the changes in the real
' and imaginary parts across pixels.
Dim wid As Integer = picCanvas.ClientSize.Width
Dim hgt As Integer = picCanvas.ClientSize.Height
dx = (m_Wxmax - m_Wxmin) / (wid - 1)
dy = (m_Wymax - m_Wymin) / (hgt - 1)
' Calculate the values.
x0 = New Complex(m_Wxmin, 0)
For i As Integer = 0 To wid - 1
x0.Im = m_Wymin
For j As Integer = 0 To hgt - 1
x = x0
Const MAX_ITER As Integer = 200
Dim iter As Integer = 0
Do
iter += 1
If iter > MAX_ITER Then Exit Do
epsilon = F(x).DividedBy(dFdx(x)).Times(-1, _
0)
x = x.Plus(epsilon)
Loop While epsilon.MagnitudeSquared() > CUTOFF
' Set which root this is.
If iter > MAX_ITER Then
clr = 0 ' Black.
Else
' Find the root.
clr = 1 ' White.
For r As Integer = 0 To _
m_Roots.GetUpperBound(0)
If x.IsCloseTo(m_Roots(r)) Then
clr = r + 2 ' +2 to skip black and
' white.
Exit For
End If
Next r
End If
' Set the pixel's color.
m_Bitmap.SetPixel(i, j, m_Colors(clr))
' Move to the next point.
x0.Im += dy
Next j
x0.Re += dx
' Let the user know we're not dead.
If i Mod 10 = 0 Then picCanvas.Refresh()
Next i
' Update the image.
picCanvas.Refresh()
Me.Text = "Newton's Method (" & _
Format$(m_Wxmin) & ", " & _
Format$(m_Wymin) & ")-(" & _
Format$(m_Wxmax) & ", " & _
Format$(m_Wymax) & ")"
End Sub
|
|
See the code for additional details.
For more information on Newton's method, see Eric W. Weisstein's article Newton's Method from MathWorld--A Wolfram Web Resource.
|
|
|
|
|
|