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

Для зарисовки кривой Безье, мы можем пробежаться по всем значениям 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 для иллюстрации геометрического построения.

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

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

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 составляет всего одну точку. В противном случае — это создает новый список для вводной, составленный из "маркеров", обчисленых пропорционально значению t между поточного списка точек вводной и вызовет саму себя с новой вводной.

4.5 KiB Raw Permalink Blame History Unescape Escape

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

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

4.5 KiB

Raw Permalink Blame History