recursion - 了解 Postscript 中的递归 Koch 雪花函数

Question

我在 PostScript 中有以下程序，但我很难理解。

/kochR
 {
   2 copy ge {dup 0 rlineto}
     {
       3 div
       2 copy kochR
       60 rotate
       2 copy kochR
       -120 rotate
       2 copy kochR
       60 rotate
       2  copy kochR
      } ifelse
     pop pop
  } def

0 0 moveto
27 81 kochR
0 27 moveto
9 81 kochR
0 54 moveto
3 81 kochR
0 81 moveto
1 81 kochR
stroke

我对上述程序的问题是:

什么2 copy ge { dup 0 rlineto }这里的意思？

怎么样ifelse在这里工作，什么条件？

什么3 div在这里做什么？

2 copy KochR有什么用语句在这里执行？

Answer 1

What does 2 copy ge { dup 0 rlineto } mean here?

作为 if 的 THEN 子句或 ifelse运算符，它的意思是“if (stack(top-1) > stack(top)) draw_horizo​​ntal_line((current_x, current_y) -> (current_x + stack(top), current_y)。过程体 { dup 0 rlineto }是递归:决定何时停止以及做什么而不是递归的部分。 rlineto 绘制一条相对线。相对于当前点，即。当前点是最后一个路径构造运算符(如 moveto ， lineto ，但不是 rotate ，而不是 stroke )离开了它。

How does ifelse work here and what is the condition?

ifelse始终以相同的方式工作: booleantype procedure-body procedure-body ifelse:如果 bool 值为真，则执行第一个过程体，否则执行第二个。条件是 gt 的 bool 值结果运算符应用于堆栈上的 2 个数字。自 gt消耗其参数，前置 2 copy表示 gt时数据不丢失这样做。

What does 3 div do here?

由于第二个参数(栈顶)控制图形的整体大小，它也控制由所有子调用的组合绘图命令表示的部分图形的“大小”。 3 div意味着在每个递归级别，图形的“大小”都小于其父级的“大小”，小 1/3。在叶子调用中，条件 a >= b 成立，b 用作组成图像的各个线段的长度。这意味着 a 本身不是行长度，而是一个阈值。一旦 b 在下降到 b/3、b/9、b/27、b/81 时遇到或越过阈值 a，那么就该关闭克隆机并让每个人拿起铅笔。

What does the 2 copy KochR statement perform here?

该行执行对 kochR 过程的递归调用，使用相同的阈值和从传递给当前调用的两个参数减小的大小。使用 2 copy意味着这两个值一直在堆栈上直到 pop pop再往下。

这是对 C 的粗略翻译，假设有一个可用的图形库来实现 Adob​​e Image Model(也称为 Stencil-Mask 或 Path-Paint 模型)。参数似乎分别是线段的大小和图形的整体大小。因此，最大递归级别由等式 a >= b * (1/3)^R 间接控制。

void kochR(double a, double b) {
    if (a >= b) {
        // line from currentpoint to currentpoint+(b,0)
        // ie. line of length b along current x-axis
        rlineto(b, 0);
    } else {
        b /= 3;
        kochR(a, b); // recurse with reduced length
        rotate(60);  // rotate x-axis CCW by 60 degrees
        kochR(a, b);
        rotate(-120); // rotate x-axis CW by 120 degrees
        kochR(a, b);
        rotate(60);
        kochR(a, b);
    }
}

int main(void) {
    moveto(0,0);
    kochR(27, 81);
    moveto(0, 27);
    kochR(9, 81);
    moveto(0, 54);
    kochR(3, 81);
    moveto(0, 81);
    kochR(1, 81);
    stroke();
}

所以你应该可以从这里看到所有 2 copy东西是一种手段后记必须“保持活力”2个未命名的变量。每行对应一个过程调用，它消耗堆栈中的 2 个变量。您应该能够看到最后的 pop pop如果您还省略了最后的 2 copy，则没有必要从最后一个“程序调用”。从 postscript 编程的角度来看，这都是非常基本的东西。但是递归有界的方式非常复杂。

顺便说一句，如果你喜欢这些分形(我喜欢)，你绝对必须看到 http://en.wikipedia.org/wiki/L-system .太棒了。

一种实现 Adob​​e 图像模型的流行 C 库是 Cairo Graphics ，但我会将创建工作程序的任务留给读者作为练习。 :)