How many stacks are required to implement the iterative version of De Casteljau's algorithm?

Question

I guess only 1 stack wouldn't be enough, because the following logic doesn't look very viable to me:

De-Casteljau's-algorithm

Answer 1

Everything can be done with a stack.

De Casteljau's algorithm is an iterative algorithm that replaces:

{a,b,c,d,...,z}

with:

{a'=lerp(a,b), b'=lerp(b,c), c'=lerp(c,d), ..., y'=lerp(y,z)}

and runs that reduction until there is only one value left.

Using a stack, we take the two bottom stack elements, lerp them (based on some ratio value), and then overwrite the bottom element with the resulting value. We move up one spot, and repeat, move and repeat, move and repeat, until we reach the top of the stack. Then we discard the topmost element. To find the final point, we run that algorithm until the stack is size 1.

So, in pseudo-code:

reduceOnce(stack, ratio):
  n = stack.length
  for(i = 0 to n-1):
    stack[i] = (1-ratio) * stack[i] + ratio * stack[i+1]
  stack.pop()

stackReduce(stack, ratio):
  while(stack size > 1):
    reduceOnce(stack, ratio)

And done: one stack needed.