Распространенной задачей для программиста является рисование графиков. Входными данными является массив точек (xi;yi). Как правило, мы знаем только некоторые значения — в определенных точках графика. Чтобы построить непрерывный график кривой необходимо прибегнуть к интерполяции или аппроксимации.
Интерполяция — построение кривой, проходящей через заданные точки.
Аппроксимация — приближение кривой к исходной, но не обязательно проходящей через заданные точки.
В этом топике я хочу продемонстрировать свою библиотеку для PHP, которая производит интерполяцию с помощью многочлена Лагранжа, C-сплайна и сплайна Акимы, а также аппроксимацию кривой Безье. Дополнительно в ней реализована отрисовка отрезка со сглаживанием (антиалиасингом).
Кратко рассмотрим методы интерполяция и аппроксимации.
Первое, что приходит в голову — соединить точки отрезками:
Самое лучшее решение по быстродействию, однако полученный график получается ломанный — это не то, что нам нужно.
Многочлен степени n для n+1 точек. Формула его весьма проста:
Прост в реализации, но обладает двумя серьезными недостатками:
1) требует значительного объема вычислений
2) непредсказуемо ведет себя между заданными точками (узлами)
Кубический сплайн лишен недостатков предыдущего метода. Для каждого интервала между узлами задается многочлен степени не выше 3, при этом первая и вторая производная функции должна быть непрерывна. Это с одной стороны, упрощает вычисления, а с другой — позволяет избежать резких скачков кривизны.
Реализацию кубического сплайна я портировал из С#-кода, взятого из Википедии.
У кубических сплайнов есть недостаток: в районе точки, далеко отстоящей от соседей, такие сплайны могут делать неожиданные «выбросы». Эту проблему можно решить использованием сплайнов, предложенных Хироши Акима. Обратите внимание — сплайн Акимы более устойчив:
Реализацию сплайна Акимы я портировал из C-кода программы для debian aspline Дэвида Фрея.
Иногда полезно не проводить кривую через заданные точки, а использовать их как опорные. Поможет нам в этом метод кривых Безье (код я портировал из C# примера Толга Бирдала). Кривая проходит через первую и последнюю точки
Проводилось для графика размером 500х500 без отрисовки на сервере Xeon 5560 2.8ГГц, число экспериментов = 1000. Среднее время выполнения, с:
Из приведенной таблицы можно сделать следующие выводы:
1) Время расчета многочлена Лагранжа быстро растет при возрастании количества точек.
2) Сплайн Акимы работает быстрее кубического.
3) Построение кривой Безье медленнее сплайнов.
Сначала подумайте: нужно ли вам вообще проводить кривую между точками? Если точек мало, может быть лучше использовать таблицу? Если вы имеете дело со статистическими данными по диапазонам группировки (например, средняя температура по месяцам по многолетним данным), то лучше использовать гистограмму.
Если вам необходимо провести кривую через известные точки — я бы рекомендовал использовать сплайн Акимы. Если сами точки не играют большой роли, то я бы аппроксимировал график кривой Безье.
Построение кривой в библиотеке gd можно осуществлять отрезками. Для этого кривая разбивается на участки с определенным шагом (минимум 1 пиксел) и между началом и концом участка проводим отрезок функцией imageline. Однако такой отрезок PHP отрисует без антиалиасинга. На помощь приходит алгоритм рисования отрезка с экранным сглаживанием — алгоритм Ву. Алгоритм Ву умеет отрисовывать только отрезки под углом ±45°, поэтому в остальных случаях его приходится «поворачивать». На рисунке приведен график функции sin(x) без антиалиасинга, а ниже ничего — с антиалиасингом.
Для каждого метода интерполяции/аппроксимации я написал отдельный класс: LagrangePolynomial, CubicSpline, AkimaSpline, BezierCurve. У каждого класса есть 3 публичных метода:
setCoords(&координаты, шаг, [x_min, [x_max]]) — задает исходные координаты и параметры построения кривой, возвращает false в случае ошибки
process() — возвращает массив координат для построения кривой
getError() — возвращает сообщение об ошибке
Координаты передаются в виде массива array(x1 => y1, x2 => y2… xn => yn)
Для построения графика реализован вспомогательный класс Plot. Его возможности весьма скромные (например, нет масштабирования — график строится 1:1), поэтому вместо него вы можете использовать другой класс или нативные функции PHP. Методы:
В конструктор поступает массив координат.
drawLine(изображение, цвет, [x0, [y0]]) — рисует ломанную линию, изображение — идентификатор ресурса, цвет должен быть задан imagecolorallocate, x0 и y0 — смещение начала координат (по умолчанию — в левом нижнем углу изображения)
drawAALine(изображение, цвет, [x0, [y0]]) — рисует ломанную линию с антиалиасингом отрезков, параметры аналогично drawLine
drawDots(изображение, цвет, [x0, [y0, [размер]]]) — рисует точки без соединения отрезками, параметры аналогично drawLine, размер — диаметр точек
drawAxis(изображение, цвет, [x0, [y0, [1кв]]]) — рисует оси, параметры аналогично drawLine, если 1кв=true (по умолчанию), оси рисуются только для первого квадранта — в положительную сторону
Пример (функция sin(x)):
Скачать библиотеку и демо версия
Е.П. Кузьмин, Д.В. Иванов Алгоритмические основы компьютерной графики (лекция №4)
Интерполяция сплайнами
Оригинальная статья Акимы
Сравнение кубического и сплайна Акимы
Bezier Curves Made Simple
Википедия:
Многочлен Лагранжа.
Кубический сплайн
Кривые Безье
Интерполяция — построение кривой, проходящей через заданные точки.
Аппроксимация — приближение кривой к исходной, но не обязательно проходящей через заданные точки.
В этом топике я хочу продемонстрировать свою библиотеку для PHP, которая производит интерполяцию с помощью многочлена Лагранжа, C-сплайна и сплайна Акимы, а также аппроксимацию кривой Безье. Дополнительно в ней реализована отрисовка отрезка со сглаживанием (антиалиасингом).
Кратко рассмотрим методы интерполяция и аппроксимации.
Кусочно-линейная интерполяция
Первое, что приходит в голову — соединить точки отрезками:
Самое лучшее решение по быстродействию, однако полученный график получается ломанный — это не то, что нам нужно.
Интерполяционный многочлен Лагранжа
Многочлен степени n для n+1 точек. Формула его весьма проста:
Прост в реализации, но обладает двумя серьезными недостатками:
1) требует значительного объема вычислений
2) непредсказуемо ведет себя между заданными точками (узлами)
Кубический сплайн (c-spline)
Кубический сплайн лишен недостатков предыдущего метода. Для каждого интервала между узлами задается многочлен степени не выше 3, при этом первая и вторая производная функции должна быть непрерывна. Это с одной стороны, упрощает вычисления, а с другой — позволяет избежать резких скачков кривизны.
Реализацию кубического сплайна я портировал из С#-кода, взятого из Википедии.
Сплайн Акимы
У кубических сплайнов есть недостаток: в районе точки, далеко отстоящей от соседей, такие сплайны могут делать неожиданные «выбросы». Эту проблему можно решить использованием сплайнов, предложенных Хироши Акима. Обратите внимание — сплайн Акимы более устойчив:
Реализацию сплайна Акимы я портировал из C-кода программы для debian aspline Дэвида Фрея.
Аппроксимация кривой Безье
Иногда полезно не проводить кривую через заданные точки, а использовать их как опорные. Поможет нам в этом метод кривых Безье (код я портировал из C# примера Толга Бирдала). Кривая проходит через первую и последнюю точки
Тестирование производительности
Проводилось для графика размером 500х500 без отрисовки на сервере Xeon 5560 2.8ГГц, число экспериментов = 1000. Среднее время выполнения, с:
| Кол-во точек: | 5 | 15 | 50 |
| Многочлен Лагранжа | 1.789 | 5.664 | 20.446 |
| Кубический сплайн | 0.153 | 0.230 | 0.313 |
| Сплайн Акимы | 0.017 | 0.024 | 0.049 |
| Кривая Безье | 0.244 | 0.276 | 0.304 |
Из приведенной таблицы можно сделать следующие выводы:
1) Время расчета многочлена Лагранжа быстро растет при возрастании количества точек.
2) Сплайн Акимы работает быстрее кубического.
3) Построение кривой Безье медленнее сплайнов.
Выбор метода
Сначала подумайте: нужно ли вам вообще проводить кривую между точками? Если точек мало, может быть лучше использовать таблицу? Если вы имеете дело со статистическими данными по диапазонам группировки (например, средняя температура по месяцам по многолетним данным), то лучше использовать гистограмму.
Если вам необходимо провести кривую через известные точки — я бы рекомендовал использовать сплайн Акимы. Если сами точки не играют большой роли, то я бы аппроксимировал график кривой Безье.
Антиалиасинг
Построение кривой в библиотеке gd можно осуществлять отрезками. Для этого кривая разбивается на участки с определенным шагом (минимум 1 пиксел) и между началом и концом участка проводим отрезок функцией imageline. Однако такой отрезок PHP отрисует без антиалиасинга. На помощь приходит алгоритм рисования отрезка с экранным сглаживанием — алгоритм Ву. Алгоритм Ву умеет отрисовывать только отрезки под углом ±45°, поэтому в остальных случаях его приходится «поворачивать». На рисунке приведен график функции sin(x) без антиалиасинга, а ниже ничего — с антиалиасингом.
Библиотека
Для каждого метода интерполяции/аппроксимации я написал отдельный класс: LagrangePolynomial, CubicSpline, AkimaSpline, BezierCurve. У каждого класса есть 3 публичных метода:
setCoords(&координаты, шаг, [x_min, [x_max]]) — задает исходные координаты и параметры построения кривой, возвращает false в случае ошибки
process() — возвращает массив координат для построения кривой
getError() — возвращает сообщение об ошибке
Координаты передаются в виде массива array(x1 => y1, x2 => y2… xn => yn)
Для построения графика реализован вспомогательный класс Plot. Его возможности весьма скромные (например, нет масштабирования — график строится 1:1), поэтому вместо него вы можете использовать другой класс или нативные функции PHP. Методы:
В конструктор поступает массив координат.
drawLine(изображение, цвет, [x0, [y0]]) — рисует ломанную линию, изображение — идентификатор ресурса, цвет должен быть задан imagecolorallocate, x0 и y0 — смещение начала координат (по умолчанию — в левом нижнем углу изображения)
drawAALine(изображение, цвет, [x0, [y0]]) — рисует ломанную линию с антиалиасингом отрезков, параметры аналогично drawLine
drawDots(изображение, цвет, [x0, [y0, [размер]]]) — рисует точки без соединения отрезками, параметры аналогично drawLine, размер — диаметр точек
drawAxis(изображение, цвет, [x0, [y0, [1кв]]]) — рисует оси, параметры аналогично drawLine, если 1кв=true (по умолчанию), оси рисуются только для первого квадранта — в положительную сторону
Пример (функция sin(x)):
<?php
//Для удобства зададим размеры заранее
define('GRAPH_WIDTH', 490);
define('GRAPH_HEIGHT', 150);
//Общий абстрактный класс SmoothCurve
include_once ('SmoothCurve.class.php');
//Класс кубического сплайна
include_once ('CubicSpline.class.php');
//Можно также использовать
//include_once ('AkimaSpline.class.php');
//include_once ('BezierCurve.class.php');
//Вспомогательный класс для рисования графиков
//Вместо него можно использовать свой или родные функции PHP
include_once ('Plot.class.php');
//Задаем координаты в массиве array(x1 => y1, x2 => y2 ... xn => yn)
$testCoords[-215] = -24.2705098312;
$testCoords[-180] = 28.5316954889;
$testCoords[-145] = -9.27050983125;
$testCoords[-110] = -17.6335575688;
$testCoords[-75] = 30;
$testCoords[-40] = -17.6335575688;
$testCoords[-5] = -9.27050983125;
$testCoords[30] = 28.5316954889;
$testCoords[65] = -24.2705098312;
$testCoords[100] = 0;
$testCoords[135] = 24.2705098312;
$testCoords[170] = -28.5316954889;
$testCoords[205] = 9.27050983125;
$testCoords[240] = 17.6335575688;
$testCoords[275] = -30;
//Создаем truecolor изображение (для антиалисинга)
$im = imagecreatetruecolor(GRAPH_WIDTH, GRAPH_HEIGHT);
//Задаем цвета
$bgColor = imagecolorallocate($im, 224, 223, 223);
$textColor = imagecolorallocate($im, 0, 0, 0);
$axisColor = imagecolorallocate($im, 64, 64, 64);
$dotColor = imagecolorallocate($im, 192, 64, 64);
$graphColor = imagecolorallocate($im, 64, 64, 192);
//Фон
imagefill($im, 0, 0, $bgColor);
//Создаем объект графика
$testGraph = new Plot($testCoords);
//Опционально: рисуем известные точки
//Передавая GRAPH_WIDTH / 2 и GRAPH_HEIGHT / 2 мы смещаем начало координат в центр изображения
$testGraph->drawDots($im, $dotColor, GRAPH_WIDTH / 2, GRAPH_HEIGHT / 2, 5);
//Создаем объект сплайна
$curve = new CubicSpline();
//Передаем ему координаты, шаг просчета = 5
$curve->setCoords($testCoords, 5);
if(!$curve->getError())
{
//Расчет координат кривой
$curveCoords = $curve->process();
if($r)
{
//Еще один объект графика
$curveGraph = new Plot($curveCoords);
//Отрисовываем кривую
$curveGraph->drawLine($im, $graphColor, GRAPH_WIDTH / 2, GRAPH_HEIGHT / 2);
}
}
//Отдаем пользователю
header("Content-type: image/png");
imagepng($im);
imagedestroy($im);
?>
Скачать библиотеку и демо версия
TODO
- Можно объединить setCoords и process() в один метод — в их разделении нет никакой пользы.
- Улучшить обработку ошибок.
- Антиалиасинг иногда работает не очень хорошо — на вертикальных линиях с малым шагом видна «лесенка».
- Разрешить несколько значений Y для одного X для кривой Безье.
- Объект Plot нужно сделать многоразовым — не передавать координаты в конструктор, как сейчас.
- Добавить комментарии в коде и документацию
Литература
Е.П. Кузьмин, Д.В. Иванов Алгоритмические основы компьютерной графики (лекция №4)
Интерполяция сплайнами
Оригинальная статья Акимы
Сравнение кубического и сплайна Акимы
Bezier Curves Made Simple
Википедия:
Многочлен Лагранжа.
Кубический сплайн
Кривые Безье
