每日算法 — 使用java实现Sierpinski三角形：递归分形与混沌几何生成

引言

Sierpinski三角形（谢尔宾斯基三角形）是数学中最经典的分形图案之一。从一个实心三角形开始， recursively 挖去中心倒三角形，无限重复后便形成一个面积趋近于零、周长趋近于无穷大的奇妙图形。它不仅出现在纯数学中，也广泛见于自然界（如罗马花椰菜的截面）、计算机图形学和 even 电路设计。本文将用Java实现Sierpinski三角形的递归生成与混沌迭代两种算法，并深入解析其自相似性的数学本质。

算法原理

递归分治算法

Sierpinski三角形的核心递归思想：

1. 基线条件：当三角形边长小于某个阈值时，直接绘制填充三角形。
2. 递归步骤：取三角形三边中点，连接中点形成四个小三角形，挖去中心倒三角形，对剩余三个正三角形递归执行上述步骤。

经过 (n) 层递归后，图形包含 (3^n) 个最小三角形。

混沌游戏算法（Chaos Game）

一个令人惊奇的发现：随机过程也能生成确定性的分形。

1. 在三角形三个顶点中随机选择一个起点。
2. 随机选择三角形的某个顶点。
3. 移动到当前位置与所选顶点连线的中点。
4. 重复步骤2-3足够多次。

经过数千次迭代后，点的分布恰好形成Sierpinski三角形。这证明了分形的”吸引子”特性——随机过程被吸引到一个确定的几何结构上。

Java实现

import javax.swing.*;
import java.awt.*;
import java.awt.image.BufferedImage;
import java.util.Random;

public class SierpinskiTriangle extends JPanel {

    private static final int WIDTH = 800;
    private static final int HEIGHT = 700;
    private static final int RECURSION_DEPTH = 6; // 递归深度
    private BufferedImage canvas;
    private Random rand = new Random();

    public SierpinskiTriangle() {
        setPreferredSize(new Dimension(WIDTH, HEIGHT));
        canvas = new BufferedImage(WIDTH, HEIGHT, BufferedImage.TYPE_INT_RGB);
        Graphics2D g = canvas.createGraphics();
        g.setColor(Color.BLACK);
        g.fillRect(0, 0, WIDTH, HEIGHT);
        g.dispose();
    }

    /**
     * 绘制单个填充三角形
     */
    private void drawTriangle(Graphics2D g, int x1, int y1, int x2, int y2, int x3, int y3, Color color) {
        int[] xPoints = {x1, x2, x3};
        int[] yPoints = {y1, y2, y3};
        g.setColor(color);
        g.fillPolygon(xPoints, yPoints, 3);
        g.setColor(Color.BLACK);
        g.drawPolygon(xPoints, yPoints, 3);
    }

    /**
     * 递归生成Sierpinski三角形（挖空中心）
     * @param g 图形上下文
     * @param x1,y1 顶点1坐标
     * @param x2,y2 顶点2坐标
     * @param x3,y3 顶点3坐标
     * @param depth 当前递归深度
     */
    private void sierpinskiRecursive(Graphics2D g,
                                     int x1, int y1, int x2, int y2, int x3, int y3,
                                     int depth) {
        if (depth == 0) {
            // 基线条件：绘制填充三角形
            // 根据深度设置颜色，产生渐变效果
            int brightness = 100 + (RECURSION_DEPTH * 20);
            brightness = Math.min(255, brightness);
            drawTriangle(g, x1, y1, x2, y2, x3, y3,
                new Color(brightness, brightness / 2 + 50, 50));
            return;
        }

        // 计算三边中点
        int mx1 = (x1 + x2) / 2;
        int my1 = (y1 + y2) / 2;
        int mx2 = (x2 + x3) / 2;
        int my2 = (y2 + y3) / 2;
        int mx3 = (x1 + x3) / 2;
        int my3 = (y1 + y3) / 2;

        // 绘制中心倒三角形（挖空部分）
        drawTriangle(g, mx1, my1, mx2, my2, mx3, my3, Color.BLACK);

        // 对三个角上的小三角形递归
        sierpinskiRecursive(g, x1, y1, mx1, my1, mx3, my3, depth - 1);
        sierpinskiRecursive(g, mx1, my1, x2, y2, mx2, my2, depth - 1);
        sierpinskiRecursive(g, mx3, my3, mx2, my2, x3, y3, depth - 1);
    }

    /**
     * 混沌游戏算法生成Sierpinski三角形
     * @param iterations 迭代次数
     */
    private void chaosGame(int iterations) {
        // 定义三角形的三个顶点
        int[][] vertices = {
            {WIDTH / 2, 50},      // 顶点
            {50, HEIGHT - 50},    // 左下
            {WIDTH - 50, HEIGHT - 50} // 右下
        };

        // 随机选择初始点（在三角形内部）
        double x = WIDTH / 2.0;
        double y = HEIGHT / 2.0;

        // 前100次迭代不绘制（让点进入吸引子区域）
        for (int i = 0; i < 100; i++) {
            int vertex = rand.nextInt(3);
            x = (x + vertices[vertex][0]) / 2.0;
            y = (y + vertices[vertex][1]) / 2.0;
        }

        // 正式绘制
        for (int i = 0; i < iterations; i++) {
            int vertex = rand.nextInt(3);
            x = (x + vertices[vertex][0]) / 2.0;
            y = (y + vertices[vertex][1]) / 2.0;

            int px = (int) x;
            int py = (int) y;

            // 根据迭代进度设置颜色渐变
            float hue = (float) (i % 360) / 360f;
            int rgb = Color.HSBtoRGB(hue, 0.8f, 1.0f);
            if (px >= 0 && px < WIDTH && py >= 0 && py < HEIGHT) {
                canvas.setRGB(px, py, rgb);
            }
        }
    }

    /**
     * 计算Sierpinski三角形的分形维数相关统计
     */
    public static void printFractalStats() {
        System.out.println("=== Sierpinski三角形数学特性 ===");
        System.out.println("分形维数（豪斯多夫维数）: D = log(3) / log(2) ≈ 1.585");
        System.out.println("解释：每次迭代将边长缩小为1/2，产生3个自相似副本");
        System.out.println();

        for (int n = 1; n <= 8; n++) {
            long triangles = (long) Math.pow(3, n);
            double sideRatio = Math.pow(0.5, n);
            double areaRatio = Math.pow(0.75, n); // 每次剩余面积为原来的3/4
            System.out.printf("深度 %d: 三角形数量 = %d, 边长比例 = %.4f, 面积比例 = %.6f%n",
                n, triangles, sideRatio, areaRatio);
        }

        System.out.println("\n当 n → ∞ 时，面积 → 0，但周长 → ∞");
        System.out.println("这是一个典型的分形：具有无限细节、自相似性、非整数维数");
    }

    @Override
    protected void paintComponent(Graphics g) {
        super.paintComponent(g);
        g.drawImage(canvas, 0, 0, this);
    }

    /**
     * 生成递归版本并保存
     */
    public void generateRecursive() {
        Graphics2D g = canvas.createGraphics();
        g.setColor(Color.BLACK);
        g.fillRect(0, 0, WIDTH, HEIGHT);

        // 定义初始大三角形
        int x1 = WIDTH / 2, y1 = 50;
        int x2 = 50, y2 = HEIGHT - 50;
        int x3 = WIDTH - 50, y3 = HEIGHT - 50;

        // 先绘制背景填充三角形
        drawTriangle(g, x1, y1, x2, y2, x3, y3, new Color(30, 30, 60));

        // 递归挖空
        sierpinskiRecursive(g, x1, y1, x2, y2, x3, y3, RECURSION_DEPTH);
        g.dispose();
        repaint();
    }

    /**
     * 生成混沌游戏版本
     */
    public void generateChaosGame() {
        Graphics2D g = canvas.createGraphics();
        g.setColor(Color.BLACK);
        g.fillRect(0, 0, WIDTH, HEIGHT);
        g.dispose();

        chaosGame(500000); // 50万次迭代
        repaint();
    }

    public static void main(String[] args) {
        // 打印数学统计
        printFractalStats();

        // 创建GUI窗口
        SwingUtilities.invokeLater(() -> {
            JFrame frame = new JFrame("Sierpinski三角形 - Java分形生成");
            frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

            SierpinskiTriangle panel = new SierpinskiTriangle();
            frame.add(panel, BorderLayout.CENTER);

            // 控制按钮
            JPanel buttonPanel = new JPanel();
            JButton recursiveBtn = new JButton("递归生成");
            JButton chaosBtn = new JButton("混沌游戏");
            JButton statsBtn = new JButton("打印统计");

            recursiveBtn.addActionListener(e -> panel.generateRecursive());
            chaosBtn.addActionListener(e -> panel.generateChaosGame());
            statsBtn.addActionListener(e -> printFractalStats());

            buttonPanel.add(recursiveBtn);
            buttonPanel.add(chaosBtn);
            buttonPanel.add(statsBtn);
            frame.add(buttonPanel, BorderLayout.SOUTH);

            frame.pack();
            frame.setLocationRelativeTo(null);
            frame.setVisible(true);

            // 默认显示递归版本
            panel.generateRecursive();
        });
    }
}

复杂度分析

数学特性

• 面积收敛：初始面积 (A_0)，经过 (n) 次迭代后面积为 (A_0 \cdot (3/4)^n)，当 (n \to \infty) 时面积趋近于0。
• 周长发散：每次迭代边数变为3倍，边长变为1/2，总周长变为原来的 (3/2) 倍，因此周长随迭代次数指数增长。
• 自相似性：任意放大Sierpinski三角形的局部，都能看到与整体相同的结构。

应用场景

1. 计算机图形学：分形山脉、云朵、树木等自然景物的程序化生成。
2. 天线设计：Sierpinski分形天线具有多频段特性，广泛用于移动通信。
3. 集成电路：利用分形结构在有限面积内最大化导线长度，优化电路性能。
4. 数据压缩：分形的自相似性可用于图像压缩（如分形图像编码）。
5. 艺术创作：生成具有数学美感的视觉图案，用于数字艺术和纹理设计。
6. 教学演示：直观展示递归、分形、混沌理论和 attractor 概念。

总结

Sierpinski三角形以最简洁的递归规则，生成了蕴含无限复杂性的几何图案。从递归分治到混沌游戏，两种截然不同的算法却能生成完全相同的结构——这正是分形数学的深刻之处：确定性规则可以产生看似随机的复杂性，而随机过程也能被吸引到确定的几何形态上。掌握Sierpinski三角形的生成算法，不仅是学习递归和图形编程的绝佳练习，更是理解分形世界的一扇窗口。