书名：代码本色：用编程模拟自然系统
作者：Daniel Shiffman
译者：周晗彬
ISBN：978-7-115-36947-5
第8章目录

8.4　科赫曲线和ArrayList技术

• 递归函数是构建分形图案的一种技术。
• 然而，如果你想把上面的康托尔集变成单个对象，能独立地移动，该怎么做？递归函数简单优雅，但它只能产生图案，无法把图案当作对象。
• 有一种技术能让我们在产生分形图案的同时，还能把图案的各个部分当作对象，那就是把递归和ArrayList结合在一起。

1、科赫曲线规则

另一个有名的分形图案，它是由瑞典数学家海里格·冯·科赫于1904年提出的，下面列出了它的规则。（它的初始状态和康托尔集一样，都是一条线段。）

它的结果如下：

2、“怪物”曲线

• 科赫曲线（即Koch Curve，和其他分形图案通常被称为“数学怪物”。因为分形经过无数次递归之后，将会出现一个奇怪的悖论：假设起始长度是1，第一次迭代后，科赫曲线的长度将会变成原来的4/3（每个线段的长度都是起始长度的1/3）；再做一次迭代，长度会变成原来的16/9；经过无数次迭代之后，科赫曲线的长度会接近无穷大。然而，它依然能被这个狭小的空间（屏幕）容纳。
• 由于我们工作在有限的像素空间内，因此并不需要考虑这个悖论。我们必须限制科赫规则的递归作用次数，以避免程序耗尽内存或崩溃。

3、对象实现

• 前面我们用递归实现了康托尔集，在这里我们依然可以用递归实现科赫曲线。但我们打算稍稍改变其中的实现方式：把科赫曲线的每个线段当作单独的对象。
• 这么做会增添很多新的设计思路，比如，我们可以让这些线段对象单独移动，参与物理模拟。除此之外，我们还可以用随机颜色和线条宽度绘制每个线段对象。
• 为了把每个线段当作单独的对象，我们必须先设计这些对象：对象存放了哪些数据，以及对象有什么功能？

4、科赫曲线实现

• 科赫曲线是一系列相互连接的线段。我们打算用KochLine对象表示这些线段。每个科赫线段都有一个起点（a）和终点（b）。这些点都是向量对象。其中的线段可以用Processing的line()函数绘制。

class KochLine {
  PVector a;   线段的起点和终点
  PVector b;

  KochLine(PVector start, PVector end) {
    a = start.get();
    b = end.get();
  }

  void display() {
    stroke(0);
    line(a.x, a.y, b.x, b.y);    在起点和终点之间画一条线段
  }

• 有了KochLine类之后，我们就可以开始实现主程序了。我们需要用一个数据结构存放曲线中的KochLine对象，ArrayList是一个合理的选择。
  ArrayList<KochLine> lines;

5、setup()函数

• setup()函数负责ArrayList实例的创建和初始化。
  我们应该在ArrayList中加入一个初始线段，线段从0开始，横向贯穿Sketch屏幕。

void setup() {
    size(600, 300);
    lines = new ArrayList<KochLine>(); 创建ArrayList对象
    PVector start = new PVector(0, 200); 屏幕的左边
    PVector end = new PVector(width, 200); 屏幕的右边
    lines.add(new KochLine(start, end)); 第一个KochLine对象
}

6、draw()函数

void draw() {
    background(255);
    for (KochLine l : lines) {
        l.display();
    }
}

这就是代码框架，回顾一下到目前为止我们实现了什么。

• KochLine类　 表示点A到点B之间的线段。
• ArrayList　 KochLine对象组成的列表。

7、实现科赫规则和递归过程

你还记得生命游戏中细胞自动机的实现吗？

• 在生命游戏的模拟过程中，我们始终保持两个状态列表：当前代和下一代的细胞状态。在一次迭代完成后，我们就把下一代状态变成当前代，再开始新一代的计算。
• 本例可以使用类似的技术，用一个ArrayList跟踪当前的KochLine对象集（在程序开始时，只有一个KochLine对象集），用第二个ArrayList存放由科赫规则产生的新KochLine对象。

• 每一个KochLine对象都会产生4个新的KochLine对象，我们应该把这些新对象放到下一代ArrayList中。当前ArrayList遍历完成之后，下一代ArrayList就会成为当前的ArrayList。

  
  

void generate() {
    ArrayList next = new ArrayList<KochLine>();　　　创建下一代ArrayList对象……
    for (KochLine l : lines) {　　　……对当前的每一个线段
        next.add(new KochLine(???, ???));　　　添加4条新线段（我们必须计算这些新线段的位置）
        next.add(new KochLine(???, ???));
        next.add(new KochLine(???, ???));
        next.add(new KochLine(???, ???));
    }
    lines = next;　　　现在我们只关心新的ArrayList
}

• 通过一次次调用generate()函数（比如，每次鼠标按下时），我们递归地把科赫曲线规则作用在当前的KochLine对象上。当然，上面的代码并没有实现科赫规则。科赫规则将一条线段分解成4条线段。我们可以用一些简单的算术和三角函数完成计算。由于KochLine对象用到了向量，因此这是一个实践向量运算的绝好机会。我们先来找出KochLine对象的分解点。

  
  

• 从上图可以看出，为了产生新的KochLine对象，我们需要找到5个点（图中的a、b、c、d和e），然后根据这些点创建线段（线段ab、cb、cd和de）。

• 如何找到这几个点？现在我们有了KochLine对象，何不让它帮我们计算这些点？

void generate() {
    ArrayList next = new ArrayList<KochLine>();
    for (KochLine l : lines) {
        PVector a = l.kochA();　　　KochLine对象有5个函数，每个函数都返回一个根据科赫规则产生
        PVector b = l.kochB();
        PVector c = l.kochC();
        PVector d = l.kochD();
        PVector e = l.kochE();
        next.add(new KochLine(a, b));
        next.add(new KochLine(b, c));
        next.add(new KochLine(c, d));
        next.add(new KochLine(d, e));
    }
    lines = next;
}

• 现在我们需要在KochLine类中实现这5个函数，每个函数分别返回图8-16中的某个点。我们先搞定kochA()函数和kochE()函数，它们分别返回原始线段的起点和终点。

• 下面计算点B和点D，点B位于线段的1/3处，而点D位于线段的2/3处。它们的方向都是由起点指向终点，长度分别为原始线段长度的1/3和2/3。

  
  

PVector kochB() {
    PVector v = PVector.sub(end, start); 从起点到终点的PVector向量
    v.div(3); 将长度缩短为1/3
    v.add(start); 向量加上起点，得到新的点
    return v;
}
PVector kochD() {
    PVector v = PVector.sub(end, start);
    v.mult(2/3.0); 和前面的计算步骤一样，但我们需要移动2/3的长度
    v.add(start);
    return v;
}

• 点C是最难计算的。但如果你知道等边三角形的内角都是60度，事情将会变得简单。我们只要将一个1/3长度的向量旋转60度，再从点B沿着这个向量移动，就能得到点C！

  
  

PVector kochC() {
    PVector a = start.get(); 从起点开始
    PVector v = PVector.sub(end, start);
    v.div(3); 移动1/3长度到点B
    a.add(v);
    v.rotate(-radians(60)); 将以上向量旋转60度
    a.add(v); 沿着这个向量移动到点C
    return a;
}

8、结果

• 将上述代码整合在一起，如果我们在step()函数中调用5次generate()函数，就能得到以下结果。