Алгоритм Чайкина

Алгоритмы и структуры данных

Javascript

Графика

Содержание

Введение
Общие сведения
Реализация алгоритма

Введение

В данной статье рассмотрим Алгоритм Чайкина(Chaikin’s Algorithm) и реализуем его на языке JS(Javascript).

Общие сведения

Алгоритм Чайкина используется для сглаживания углов кривой, основная идея заключается в добавлении новых точек между существующими до тех пор пока кривая не станет достаточно плавной. Новые точки располагаются на 25% и 75% относительно длины прямой образованной между двумя оригинальными точками, как показано ниже:

25% и 75% относительно длины прямой

Новые точки на прямой выше образуются следующим образом:

L = P2 - P1, где L - длина прямой, P1 и P2 - оригинальные точки

P3 = P1 + L * 0.25, где 0.25 описанные выше 25%

P4 = P1 + L * 0.75, где 0.75 описанные выше 75%

Реализация алгоритма

Перед тем как перейти к реализации алгоритма Чайкина необходимо реализовать код, который будет использоваться для рисования кривой, он может выглядеть следующим образом:

123457891011121314

// Функция рисует линию по указанным точка.
function drawCurve(points) {
  const context = canvas.getContext("2d");
  context.lineWidth = 10;
  context.strokeStyle = "#4663C9"

  context.beginPath();
  context.moveTo(points[0].x, points[0].y);
  for (let index = 1; index < points.length; index++) {
    context.lineTo(points[index].x, points[index].y);
  }
  context.stroke();
}

Код выше принимает в качестве аргумента массив точек и затем рисует прямые между ними. Для тестирования нашей реализации возьмем следующую кривую:

Иллюстрирует кривую для тестирования алгоритма

Используя функцию drawCurve рисование кривой будет выглядеть следующим образом:

123456789

const points = [
  { x: 100, y: 100 },
  { x: 200, y: 100 },
  { x: 200, y: 200 },
  { x: 300, y: 200 },
  { x: 300, y: 100 },
  { x: 400, y: 100 }
]
drawCurve(points)

Используя формулу из предыдущего раздела реализуем функцию smoothing, которая создает две новые точки на каждую прямую образованную между оригинальными точками переданными в качестве аргумента функции smoothing:

1235678910121314151718192022232426272829

// Функция создает новые точки используя алгоритм Чайкина.
function smoothing(points) {
  const result = [points[0]]

  let index = 0
  const last_index = points.length - 1
  while (index < last_index) {
    const first = points[index]
    const second = points[index + 1]

    // Определение длины отрезка
    const dx = second.x - first.x
    const dy = second.y - first.y

    // 25% и 75% относительно длины полученного отрезка
    result.push({x: first.x + dx * 0.25, y: first.y + dy * 0.25})
    result.push({x: first.x + dx * 0.75, y: first.y + dy * 0.75})

    index++
  }

  result.push(points[last_index])
  return result
}

Доработаем функцию drawCurve, таким образом чтобы перед рисованием она вызывала smoothing для сглаживания кривой.

123467891112131415161718

// Функция рисует линию по указанным точка.
function drawCurve(points) {
  // Создание новых точек для сглаживания кривой
  points = smoothing(points)

  const context = canvas.getContext("2d");
  context.lineWidth = 10;
  context.strokeStyle = "#4663C9"

  context.beginPath();
  context.moveTo(points[0].x, points[0].y);
  for (let index = 1; index < points.length; index++) {
    context.lineTo(points[index].x, points[index].y);
  }
  context.stroke();
}

Новая версия функции drawCurve рисует следующую кривую:

Иллюстрирует кривую сглаженную алгоритмом Чайкина

На изображении выше кривая стала более плавной, но выглядит все еще ломанной. Для того, чтобы избавиться от резких углов на нашей кривой достаточно повторить алгоритм несколько раз увеличив количество точек для рисования кривой. Доработаем функцию drawCurve еще раз.

1234568910111314151617181920

// Функция рисует линию по указанным точка.
function drawCurve(points, smooth) {
  // Создание новых точек для сглаживания кривой
  for (let i = 0; i < smooth; i++) {
    points = smoothing(points)
  }

  const context = canvas.getContext("2d");
  context.lineWidth = 10;
  context.strokeStyle = "#4663C9"

  context.beginPath();
  context.moveTo(points[0].x, points[0].y);
  for (let index = 1; index < points.length; index++) {
    context.lineTo(points[index].x, points[index].y);
  }
  context.stroke();
}

Новый аргумент smooth управляет количеством итераций сглаживания, для получения плавной кривой 3 итерация будет достаточно.

123456789

const points = [
  { x: 100, y: 100 },
  { x: 200, y: 100 },
  { x: 200, y: 200 },
  { x: 300, y: 200 },
  { x: 300, y: 100 },
  { x: 400, y: 100 }
]
drawCurve(points, 3)

Результатом работы кода выше является следующая кривая:

Иллюстрирует кривую прошедшую несколько итераций алгоритмома Чайкина

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

Весь исходный код примеров к данной статье вы можете найти на GitHub.