mirror of
https://github.com/Pomax/BezierInfo-2.git
synced 2025-09-08 23:50:43 +02:00
55 lines
4.5 KiB
Markdown
55 lines
4.5 KiB
Markdown
# Алгоритм де Кастельжо
|
||
|
||
Для зарисовки кривой Безье, мы можем пробежаться по всем значениям `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>
|