通过离散的傅里叶的方式来构造五角星

KataEpicyclesFourierDFT.java

import javax.swing.*;
import java.awt.*;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;


/**
 * 通过离散的傅里叶的方式来构造五角星。
 *
 * 其实可以构造任意图像, 参考资料：
 *
 *  1. 3Blue1Brown, 傅立叶介绍的视频, https://www.bilibili.com/video/BV1vt411N7Ti/
 *  2. coding train, #130 — Drawing with Fourier Transform and Epicycles, https://thecodingtrain.com/challenges/130-drawing-with-fourier-transform-and-epicycles
 *  3. Mathologer, Epicycles, complex Fourier series and Homer Simpson's orbit， https://www.youtube.com/watch?v=qS4H6PEcCCA
 *  4. GoldPlatedGoof, Fourier Analysis For The Rest Of Us， https://www.youtube.com/watch?v=2hfoX51f6sg
 *  5. mazonex, 傅立叶变换夯实基础系列视频（5）离散傅立叶变换， https://www.bilibili.com/video/BV1aT4y1J7JP/
 */
public class KataEpicyclesFourierDFT extends JPanel {


    static class FourierDraw extends JPanel {
        private final int scale = 1;

        private final List<Point<Double>> functionsPoints;

        private List<ComplexNum> functionsPointsDft;

        private final LinkedList<Point<Double>> fourierPoints = new LinkedList<>();
        private List<Point<Double>> fourierPointsToDraw = new ArrayList<>();

        private final List<Coefficient> coefficients = new ArrayList<>();
        private double theta = -1 * Math.PI;

        public FourierDraw() {
            functionsPoints = getFuncPoints();
            functionsPointsDft = dft(functionsPoints.stream().map(point -> new ComplexNum(point.x, point.y)).collect(Collectors.toList()));
            int n = functionsPoints.size();
            for (int i = 0; i < n; ++i) {
                Coefficient coefficient = new Coefficient(i, functionsPointsDft.get(i).x / n, functionsPointsDft.get(i).y / n);
                coefficients.add(coefficient);
            }
            coefficients.sort(Collections.reverseOrder());
            updateDataThread.start();
        }


        private final Thread updateDataThread = new Thread(new Runnable() {
            @Override
            public void run() {
                while (true) {
                    fourierPoints.clear();
                    double thetaStep = Math.PI * 2 / functionsPoints.size();
                    for (double theta = -1.0 * Math.PI; theta < Math.PI; theta += thetaStep) {
                        update(theta, FourierDraw.this);
                        try {
                            Thread.sleep(5);
                        } catch (Throwable ignored) {
                        }

                    }
                }
            }
        });


        public void update(double theta, Component component) {
            double xSum = 0;
            double ySum = 0;
            for (Coefficient coefficient : coefficients) {
                xSum += coefficient.getRadius() * Math.cos(coefficient.getIndex() * theta + coefficient.getArg());
                ySum += coefficient.getRadius() * Math.sin(coefficient.getIndex() * theta + coefficient.getArg());
            }
            fourierPoints.addFirst(new Point<>(xSum, ySum));
            this.theta = theta;
            fourierPointsToDraw = new ArrayList<>(fourierPoints);
            component.repaint();
        }


        public void paintComponent(Graphics g) {
            super.paintComponent(g);
            g.drawString("离散傅里叶&本轮", 10, getHeight() - 20);
            drawLine(g, getFuncPoints());
            g.setColor(Color.RED);
            drawLine(g, fourierPointsToDraw);

            if (coefficients.size() > 0) {
                g.setColor(Color.BLUE);
                double centerX = 0;
                double centerY = 0;
                for (Coefficient coefficient : coefficients) {
                    double radius = coefficient.getRadius();
                    g.setColor(Color.GRAY);
                    drawCircle(g, centerX, centerY, radius);
                    Point<Double> point = new Point<>(centerX, centerY);
                    double arg = coefficient.getArg();
                    double phi = theta * coefficient.getIndex() + arg;
                    centerX += radius * Math.cos(phi);
                    centerY += radius * Math.sin(phi);
                    g.setColor(Color.BLUE);
                    drawLine(g, point, new Point<>(centerX, centerY));
                }
                if (fourierPointsToDraw.size() > 0) {
                    drawLine(g, new Point<>(centerX, centerY), fourierPointsToDraw.get(0));
                }
            }
        }

        private void drawCircle(Graphics g, double x, double y, double radius) {
            Point<Integer> point = transform(new Point<>(x, y));
            int radiusScaled = (int) (radius * scale);
            g.drawOval(point.x - radiusScaled, point.y - radiusScaled, 2 * radiusScaled, 2 * radiusScaled);
        }


        private void drawLine(Graphics g, Collection<Point<Double>> points) {
            Point<Double> prevPoint = null;
            for (Point<Double> point : points) {
                if (prevPoint != null) {
                    drawLine(g, prevPoint, point);
                }
                prevPoint = point;
            }
        }

        private void drawLine(Graphics g, Point<Double> p1, Point<Double> p2) {
            Point<Integer> lastPoint = transform(p1);
            Point<Integer> currentPoint = transform(p2);
            g.drawLine(lastPoint.x, lastPoint.y, currentPoint.x, currentPoint.y);
        }

        public Point<Integer> transform(Point<Double> point) {
            int x = (int) Math.round(point.x * scale);
            int y = (int) Math.round(-point.y * scale);
            x += getWidth() / 2;
            y += getHeight() / 2;
            return new Point<>(x, y);
        }

        private List<Point<Double>> getFuncPoints() {
            int n = 5;
            double step = 1;
            double angleStep = 2 * Math.PI / n;
            double radius = 300;
            List<Point<Double>> polygonsPoints = new ArrayList<>();
            double startAngle = Math.PI / 2;
            for (int i = 0; i < n; ++i) {
                double angle = startAngle + angleStep * i;
                double x = Math.cos(angle) * radius;
                double y = Math.sin(angle) * radius;
                polygonsPoints.add(new Point<>(x, y));
            }
            List<Point<Double>> pentagramPoints = new ArrayList<>();
            int startPointIndex = 0;
            for (int i = 0; i < n; ++i) {
                int nextPointIndex = (startPointIndex + 2) % n;
                Point<Double> startPoint = polygonsPoints.get(startPointIndex);
                Point<Double> endPoint = polygonsPoints.get(nextPointIndex);
                double k = (endPoint.y - startPoint.y) / (endPoint.x - startPoint.x);
                double xDiff = endPoint.x - startPoint.x;
                int pointsToSample = (int) (Math.abs(xDiff / step));
                double xStep = xDiff > 0 ? step : -1.0 * step;
                for (int j = 0; j < pointsToSample; ++j) {
                    Point<Double> point = new Point<>();
                    point.x = startPoint.x + xStep * j;
                    point.y = k * (xStep * j) + startPoint.y;
                    pentagramPoints.add(point);
                }
                startPointIndex = nextPointIndex;
            }
            return pentagramPoints;
        }
    }

    private final FourierDraw fourierDraw = new FourierDraw();

    public KataEpicyclesFourierDFT() {
        super(new BorderLayout());
        add(BorderLayout.CENTER, fourierDraw);
    }


    static class Point<T> {
        T x;
        T y;

        public Point(T x, T y) {
            this.x = x;
            this.y = y;
        }

        public Point() {
        }
    }


    static class ComplexNum {
        double x;
        double y;

        public ComplexNum(double x, double y) {
            this.x = x;
            this.y = y;
        }

        public static ComplexNum multiply(ComplexNum first, ComplexNum second) {
            double x = first.x * second.x - first.y * second.y;
            double y = first.x * second.y + first.y * second.x;
            return new ComplexNum(x, y);
        }

        public static ComplexNum add(ComplexNum first, ComplexNum second) {
            double x = first.x + second.x;
            double y = first.y + second.y;
            return new ComplexNum(x, y);
        }
    }


    static class Coefficient implements Comparable {

        private int index;
        private double x;
        private double y;

        Coefficient(int index, double x, double y) {
            this.index = index;
            this.x = x;
            this.y = y;
        }

        public double getRadius() {
            return Math.sqrt(x * x + y * y);
        }

        public double getArg() {
            return Math.atan2(y, x);
        }

        public int getIndex() {
            return index;
        }

        public void setIndex(int index) {
            this.index = index;
        }

        public double getX() {
            return x;
        }

        public void setX(double x) {
            this.x = x;
        }

        public double getY() {
            return y;
        }

        public void setY(double y) {
            this.y = y;
        }


        @Override
        public int compareTo(Object o) {
            if (o == null) {
                return -1;
            }
            return Double.compare(this.getRadius(), ((Coefficient) o).getRadius());
        }
    }


    static List<ComplexNum> dft(List<ComplexNum> input) {
        List<ComplexNum> result = new ArrayList<>();
        int n = input.size();
        for (int i = 0; i < n; ++i) {
            ComplexNum xi = new ComplexNum(0, 0);
            for (int j = 0; j < n; ++j) {
                double phi = Math.PI * 2 * i * j / n;
                xi = ComplexNum.add(xi, ComplexNum.multiply(input.get(j), new ComplexNum(Math.cos(phi), -1 * Math.sin(phi))));
            }
            result.add(xi);
        }
        return result;
    }


    public static void main(String[] args) throws Exception {
        KataEpicyclesFourierDFT kataFourierSeries2 = new KataEpicyclesFourierDFT();

        JFrame frame = new JFrame();
        frame.setTitle("离散傅里叶转换(DFT)");
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.add(kataFourierSeries2);
        frame.setSize(600, 650);
        frame.setVisible(true);
    }
}