Problem
I developed a program that creates and displays a Newton fractal based on a complex polynomial.
For example, the complex polynomial:
which is what is given as input in the code, will produce an image similar to this one:
Basically what happens is that the program finds the function’s derivative, uses it to perform Newton’s method, and then gets the result from Newton’s method to color in the pixels of a BufferedImage, each of which represents a point on the complex plane. Each color represents a solution (a.k.a. “root” or “zero”) of the polynomial that a point inside that color will converge to through Newton’s method, and the different color shades represent how many iterations of Newton’s method it takes for the resulting series of points to converge, with a darker shade indicating a greater number of iterations.
This program works fine. The issue I’m having is that each time I change the polynomial function, I also have to manually insert the solutions of said polynomial into the zeros array, which (unsurprisingly?) has become somewhat tedious. But as far as I know, I have to do so in order for the program to know which solutions the points converge to.
Is there any way to modify the code such that I don’t have to re-enter the polynomial’s solutions, such as calculating them beforehand?
import java.awt.Color;
import java.awt.Dimension;
import java.awt.Graphics;
import java.awt.image.BufferedImage;
import java.util.function.Function;
import java.util.ArrayList;
import java.util.List;
import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.SwingUtilities;
public class FractalGenerator {
private BufferedImage img;
private int imageWidth = 500, imageHeight = imageWidth;
private double xMin = -2, xMax = 2, yMin = -2, yMax = 2;
private final ComplexNumber[] zeros;
private Function<ComplexNumber, ComplexNumber> function, preDerivative, derivative;
public FractalGenerator() {
double h = 1E-8;
function = z -> z.pow(3).subtract(1, 0);
preDerivative = function.compose((ComplexNumber c) -> c.add(h, 0));
derivative = c -> preDerivative.apply(c).subtract(function.apply(c)).divide(h);
zeros = new ComplexNumber[] {new ComplexNumber(1, 0),
new ComplexNumber(-.5, Math.sqrt(3)/2),
new ComplexNumber(-.5, -Math.sqrt(3)/2)};
createImage();
createAndShowGUI();
}
private void createAndShowGUI() {
SwingUtilities.invokeLater(() -> {
JFrame frame = new JFrame();
JPanel panel = new JPanel() {
@Override
protected void paintComponent(Graphics g) {
super.paintComponent(g);
g.drawImage(img, 0, 0, this);
}
@Override
public Dimension getPreferredSize() {
return new Dimension(imageWidth, imageHeight);
}
};
frame.add(panel);
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
frame.pack();
frame.setVisible(true);
});
}
private void createImage() {
double reductionFactor = .96;
double graphWidth = xMax - xMin, graphHeight = yMax - yMin;
img = new BufferedImage(imageWidth, imageHeight, BufferedImage.TYPE_INT_RGB);
Graphics g = img.getGraphics();
for (int y = 0; y < imageHeight; y++) {
double graphY = yMax - y * graphHeight /(double) imageHeight;
for (int x = 0; x < imageWidth; x++) {
double graphX = xMin + x * graphWidth / (double) imageWidth;
int[] arr = applyNewtonMethod(graphX, graphY);
if (arr[0] == -1)
g.setColor(Color.black);
else {
Color color = getColor(arr[0]);
int red = color.getRed(), green = color.getGreen(), blue = color.getBlue();
for (int i = 0; i < arr[1]; i++) {
red = (int) (red * reductionFactor);
green = (int) (green * reductionFactor);
blue = (int) (blue * reductionFactor);
}
g.setColor(new Color(red, green, blue));
}
g.drawLine(x, y, x, y);
}
}
}
private int[] applyNewtonMethod(double x, double y) {
ComplexNumber c = new ComplexNumber(x, y);
double tolerance = 1E-6;
int iterations = 1, max = 512;
while (iterations < max) {
c = c.subtract(function.apply(c).divide(derivative.apply(c)));
for (int k = 0; k < zeros.length; k++) {
ComplexNumber z = zeros[k], difference = c.subtract(z);
if (Math.abs(difference.getReal()) < tolerance && Math.abs(difference.getImaginary()) < tolerance)
return new int[] {k, iterations};
}
iterations++;
}
return new int[] {-1};
}
private Color getColor(int num) {
switch (num) {
case 0: return Color.red;
case 1: return Color.green;
case 2: return Color.blue;
case 3: return Color.yellow;
case 4: return Color.magenta;
case 5: return Color.cyan;
case 6: return Color.white;
case 7: return new Color(139, 69, 19);
case 8: return new Color(255, 165, 0);
case 9: return new Color(255, 192, 203);
default: return Color.black;
}
}
public static void main(String[] args) {
new FractalGenerator();
}
}
Here’s ComplexNumber.java for convenience:
public class ComplexNumber {
double real, imaginary;
public ComplexNumber(double real, double imaginary) {
this.real = real;
this.imaginary = imaginary;
}
public ComplexNumber add(double real, double imaginary) {
return new ComplexNumber(this.real + real, this.imaginary + imaginary);
}
public ComplexNumber add(ComplexNumber c) {
return new ComplexNumber(this.real + c.real, this.imaginary + c.imaginary);
}
public ComplexNumber subtract(double real, double imaginary) {
return new ComplexNumber(this.real - real, this.imaginary - imaginary);
}
public ComplexNumber subtract(ComplexNumber c) {
return new ComplexNumber(this.real - c.real, this.imaginary - c.imaginary);
}
public ComplexNumber multiply(double scalar) {
return new ComplexNumber(real * scalar, imaginary * scalar);
}
public ComplexNumber multiply(ComplexNumber c) {
return new ComplexNumber(real * c.real - imaginary * c.imaginary, real * c.imaginary + imaginary * c.real);
}
public ComplexNumber divide(double scalar) {
return multiply(1.0 / scalar);
}
public ComplexNumber divide(ComplexNumber c) {
return multiply(c.getConjugate()).multiply(1.0 / (c.real * c.real + c.imaginary * c.imaginary));
}
public ComplexNumber getConjugate() {
return new ComplexNumber(real, imaginary * -1);
}
public ComplexNumber pow(int exp) {
ComplexNumber c = new ComplexNumber(real, imaginary);
for (int k = 1; k < exp; k++) {
c = multiply(c);
}
return c;
}
public ComplexNumber exp() {
return new ComplexNumber(Math.exp(real) * Math.cos(imaginary), Math.exp(real) * Math.sin(imaginary));
}
public static ComplexNumber exp(ComplexNumber c) {
return c.exp();
}
public ComplexNumber cos() {
return exp(multiply(new ComplexNumber(0, 1))).add(exp(multiply(new ComplexNumber(0, -1)))).divide(2);
}
public static ComplexNumber cos(ComplexNumber c) {
return c.cos();
}
public ComplexNumber sin() {
return exp(multiply(new ComplexNumber(0, 1))).subtract(exp(multiply(new ComplexNumber(0, -1)))).divide(new ComplexNumber(0, 2));
}
public static ComplexNumber sin(ComplexNumber c) {
return c.sin();
}
public ComplexNumber tan() {
return sin().divide(cos());
}
public static ComplexNumber tan(ComplexNumber c) {
return c.sin().divide(c.cos());
}
public double getReal() {
return real;
}
public double getImaginary() {
return imaginary;
}
@Override
public String toString() {
return "" + real + (imaginary >= 0 ? "+" : "") + imaginary + "i";
}
}
Solution
for (int i = 0; i < arr[1]; i++) {
red = (int) (red * reductionFactor);
green = (int) (green * reductionFactor);
blue = (int) (blue * reductionFactor);
}
That loop could be avoided with
double pixelReductionFactor = Math.pow(reductionFactor, arr[1]);
red = (int) (red * pixelReductionFactor);
green = (int) (green * pixelReductionFactor);
blue = (int) (blue * pixelReductionFactor);
Although perhaps it would be nicer still to interpolate in a more uniform colour space than RGB. In my Newton fractal code (golfed, I’m afraid), I use Color.HSBtoRGB.
while (iterations < max) {
c = c.subtract(function.apply(c).divide(derivative.apply(c)));
for (int k = 0; k < zeros.length; k++) {
ComplexNumber z = zeros[k], difference = c.subtract(z);
if (Math.abs(difference.getReal()) < tolerance && Math.abs(difference.getImaginary()) < tolerance)
return new int[] {k, iterations};
}
iterations++;
}
If you want to avoid hard-coding the zeroes, the easy approach is to check for convergence to itself. With a tiny bit of optimisation this becomes
while (iterations < max) {
ComplexNumber difference = function.apply(c).divide(derivative.apply(c));
if (Math.abs(difference.getReal()) < tolerance && Math.abs(difference.getImaginary()) < tolerance)
// TODO Find k
return new int[] {k, iterations};
}
iterations++;
c = c.subtract(difference);
}
Since this approach starts without a list of zeroes, it must build it up as it goes. The TODO would search a list for a zero within 2 * tolerance, and if there is none it would add c (or perhaps better c.add(difference.divide(2))) to the list.