# Алгоритм де Кастельжо

Для зарисовки кривой Безье, мы можем пробежаться по всем значениям `t` от 0 до 1 и скомпилировать вывод базовой функции с подставленными весами для каждого значения. К сожалению, чем замысловатее кривая, тем дороже обходиться это обчисление. Вместо этого, мы можем воспользоваться *Алгоритмом де Кастельжо* для прорисовки кривых. Этот алгоритм позволяет прорисовывать кривые базируясь на геометрических вычислениях и довольно прост в применении. На деле, настолько прост, что его можно воплотить при помощи карандаша и линейки.

Вместо использования функции математического анализа для нахождения значений `x/y` для `t`, давайте сделаем следующее:

- Примем `t` за пропорцию(чем оно и является). t=0 будет 0% вдоль линии, t=1, соответсвенно, 100% вдоль линии.
- Возьмем все линии между заданными контрольными точками. Для кривой `n`-го порядка это `n` линий
- Разместим маркеры вдоль линий, соответсвенно значению `t`. Так, если `t` 0.2, разместим маркер на 20% от начала, и, соответственно, 80% от конца.
- Теперь соединим полученные точки линиями. Это дает нам `n-1` линий.
- Далее разместим маркеры на новых линиях, соответсвенно тому-же значению `t`.
- Продолжим повторять два предыдущих шага, пока на выводе у нас останется всего одна линия. Маркер `t` на этой линии будет соответствовать точке для `t` на нашей кривой.

Чтобы проверить это в действии, ведите ползунок под ниже представленным графиком слева направо и наоборот, задавая разные значения `t` для иллюстрации геометрического построения.

<graphics-element title="Прохождение кривой с использованием алгоритма де Кастельжо" src="./decasteljau.js">
  <input type="range" min="0" max="1" step="0.01" value="0" class="slide-control">
</graphics-element>

<div class="howtocode">

### Имплементация Алгоритма де Кастельжо

Запишем согласно предложенному алгоритму:

```
function drawCurvePoint(points[], t):
  if(points.length==1):
    draw(points[0])
  else:
    newpoints=array(points.size-1)
    for(i=0; i<newpoints.length; i++):
      newpoints[i] = (1-t) * points[i] + t * points[i+1]
    drawCurvePoint(newpoints, t)
```

Готово, алгоритм воплощен. Помимо того факта, что зачастую мы не располагаем роскошью перенагрузки оператора "+", так давайте совместим вычисление для значений `x` и `y`:

```
function drawCurvePoint(points[], t):
  if(points.length==1):
    draw(points[0])
  else:
    newpoints=array(points.size-1)
    for(i=0; i<newpoints.length; i++):
      x = (1-t) * points[i].x + t * points[i+1].x
      y = (1-t) * points[i].y + t * points[i+1].y
      newpoints[i] = new point(x,y)
    drawCurvePoint(newpoints, t)
```

И что это делает? Это зарисует точку на график, если длинна вводной points составляет всего одну точку. В противном случае — это создает новый список для вводной, составленный из "маркеров", обчисленых пропорционально значению <i>t</i> между поточного списка точек вводной и вызовет саму себя с новой вводной.

</div>