Last active
November 2, 2022 07:52
-
-
Save fftlxyz/a8c12ec5012fffddbb5921802a3b34e8 to your computer and use it in GitHub Desktop.
通过离散的傅里叶的方式来构造五角星
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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); | |
} | |
} | |
Author
fftlxyz
commented
Nov 2, 2022
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment