

/**

In this task 2 of project 1 you will implement the inverse fast Fourier transform and perform second order (n=2) NAME_1 low pass filtering in the frequency domain. You should reuse your implementation of the fast Fourier transform from the previous task of this project (P1_1).

In the filterImage() method add your code for the second order (n=2) NAME_1 low pass filtering.

Implement the inverse fast Fourier transform in the method inverseFourierTransfrom().

You may use methods declared in the class Complex.java for your convenience.

The solution file is provided for qualitative comparison. It was generated with d0=10, i.e., with the command

java P1_2 10

Output could be different because of differences in floating point arithmetic and differences in the way the rescaling is performed. 

**/

import java.time.Instant;
import java.time.Duration;
public class P1_2 {
	public P1_2(double d0) {
		Img img = new Img("ic512.png");
		Instant start = Instant.now();
		filterImage(img, d0);
		Instant stop = Instant.now();
		System.out.println("Elapsed time: "+Duration.between(start, stop).getSeconds()+"s");
		img.save();
	}

    public void filterImage(Img i, double d0) {
		Complex[] F = fastFourierTransfrom(i);
		
    // Perform NAME_1 low-pass filtering
    int width = i.width;
    int height = i.height;
    int centerX = width / 2;
    int centerY = height / 2;
    double n = 2.0; // Order of the NAME_1 filter

    for (int y = 0; y < height; y++) {
        for (int x = 0; x < width; x++) {
            int dx = x - centerX;
            int dy = y - centerY;
            double distance = Math.sqrt(dx * dx + dy * dy);
            double h = 1.0 / (1.0 + Math.pow(distance / d0, 2 * n));
            F[x + y * width].mul(h);
        }
    }

		inverseFastFourierTransfrom(F, i);
    }

    public Complex[] fastFourierTransfrom(Img i) {
    int width = i.width;
    int height = i.height;

    Complex[] F = new Complex[width * height];
    for (int x = 0; x < F.length; x++)
        F[x] = new Complex(i.img[x] & 0xFF, 0);

    // row
    for (int y = 0; y < height; y++) {
        Complex[] row = new Complex[width];
        for (int x = 0; x < width; x++) {
            row[x] = F[y * width + x];
        }
        row = fft(row);
        for (int x = 0; x < width; x++) {
            F[y * width + x] = row[x];
        }
    }

    // column
    for (int x = 0; x < width; x++) {
        Complex[] column = new Complex[height];
        for (int y = 0; y < height; y++) {
            column[y] = F[y * width + x]