迭代与递归：按顺序计算已知迭代的点位置

Question

我有一个递归函数，它接受一个点 {x,y} 并递归地计算序列中的下一个点。

看起来有点像这样：

var DECAY = 0.75;
var LENGTH = 150;
var ANGLE = 0.52;

getNextPoint(0, 0, ANGLE, LENGTH);

function getNextPoint (x, y, a, l) {

    l *= DECAY;
    a += ANGLE; 

    var x1 = x - Math.cos(a) * l;
    var y1 = y - Math.sin(a) * l;

    //We now have 2 points, draw lines etc.

    getNextPoint(x1, y1, a, l); 
}

如何在给定已知迭代的情况下计算一个点（或 2 个连续的点）？

我知道给定迭代的角度和长度值可以很容易地用下面的方法计算出来：

var a = ANGLE * iteration;
var l = LENGTH * Math.pow(DECAY, iteration);

但我仍然需要知道 iteration - 1 点的位置才能将这些值应用于？

Answer 1

将其视为复数。 z = x + i*y 是你的观点。 b = cos(a)*l + i*sin(a)*l是一些参数，c = cos(ANGLE)*DECAY + i*sin(ANGLE)*DECAY是一个常量。

最初你有 z0 = 0 和 b0 = c*LENGTH/DECAY。在你做的每个递归中

b(k+1) = b(k)*c
z(k+1) = z(k) - b

所以你有

b1 = b0*c  = c^2*LENGTH/DECAY
z1 = z0-b1 = -b1 = -c^2*LENGTH/DECAY
b2 = b1*c  = c^3*LENGTH/DECAY
z2 = z1-b2 = -(c^2+c^3)*LENGTH/DECAY
⋮
zn = -(c^2+c^3+⋯+c^(n+1))*LENGTH/DECAY

如果你ask Wolfram Alpha它会告诉你

c^2+c^3+⋯+c^(n+1) = c^2*(c^n - 1)/(c - 1)

如果你乘以复数共轭，你可以使分母为实数。然后你可以把整个事情变成一个实数公式。所以让我们写

c = cr + i*ci        cr = cos(ANGLE)*DECAY  ci = sin(ANGLE)*DECAY
d = c^n = dr + i*di  dr = cos(n*ANGLE)*pow(DECAY, n)  di = …

然后我们有

  c^2*(d - 1)*(cr - i*ci - 1)/((cr + i*ci - 1)*(cr - i*ci - 1))
= ((cr + i*ci)*(cr + i*ci)*(dr + i*di - 1)*(cr - i*ci - 1)) /
  ((cr - 1)*(cr - 1)*ci*ci)
= ((cr^3*dr + cr*ci^2*dr - cr^2*ci*di - ci^3*di - cr^3 - cr*ci^2
    - cr^2*dr + ci^2*dr + 2*cr*ci*di + cr^2 - ci^2) +
   (cr^2*ci*dr + ci^3*dr + cr^3*di + cr*ci^2*di - cr^2*ci - ci^3
    - 2*cr*ci*dr - cr^2*di + ci^2*di + 2*cr*ci))/((cr - 1)*(cr - 1)*ci*ci)

xn = -(cr^3*dr + cr*ci^2*dr - cr^2*ci*di - ci^3*di - cr^3 - cr*ci^2
       - cr^2*dr + ci^2*dr + 2*cr*ci*di + cr^2 - ci^2) /
      ((cr - 1)*(cr - 1)*ci*ci) * LENGTH / DECAY
yn = -(cr^2*ci*dr + ci^3*dr + cr^3*di + cr*ci^2*di - cr^2*ci - ci^3
       - 2*cr*ci*dr - cr^2*di + ci^2*di + 2*cr*ci) /
      ((cr - 1)*(cr - 1)*ci*ci) * LENGTH / DECAY

分子的扩展来自我的 CAS；很可能你可以把这个写得更短一些，但我不想为了尝试而手动将这四个项相乘。

这是一个演示所有这些的工作示例：

var ctxt = document.getElementById("MvG1").getContext("2d");
var sin = Math.sin, cos = Math.cos, pow = Math.pow;

var DECAY = 0.75;
var LENGTH = 150;
var ANGLE = 0.52;

var cr = cos(ANGLE)*DECAY, ci = sin(ANGLE)*DECAY;
var cr2 = cr*cr, ci2 = ci*ci, cr3 = cr2*cr, ci3 = ci2*ci;
var f = - LENGTH / DECAY / ((cr - 1)*(cr - 1)*ci*ci)

ctxt.beginPath();
ctxt.moveTo(100,450);

for (var n = 0; n < 20; ++n) {
  var da = pow(DECAY, n), dr = cos(n*ANGLE)*da, di = sin(n*ANGLE)*da;
  var xn, yn;
  xn = (cr3*dr + cr*ci2*dr - cr2*ci*di - ci3*di - cr3 - cr*ci2
        - cr2*dr + ci2*dr + 2*cr*ci*di + cr2 - ci2)*f;
  yn = (cr2*ci*dr + ci3*dr + cr3*di + cr*ci2*di - cr2*ci - ci3
        - 2*cr*ci*dr - cr2*di + ci2*di + 2*cr*ci)*f;
  console.log([xn,yn]);
  ctxt.lineTo(0.1*xn + 100, 0.1*yn + 450);
}

ctxt.stroke();

<canvas id="MvG1" width="300" height="500"></canvas>

迭代与递归：按顺序计算已知迭代的点位置

Iteration vs Recursion: Calculate point position in sequence for known iteration

javascript

math

recursion

iteration

sequence