javascript - 迭代与递归 : Calculate point position in sequence for known iteration

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 个连续的点)？

我知道给定迭代的 Angular 和长度值可以很容易地用类似下面的东西计算出来:

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

分子的扩展来 self 的 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>