Пользователь
54,0
рейтинг
21 октября 2011 в 12:56

Разработка → Интерполяция: рисуем гладкие графики средствами PHP и GD

PHP*
Распространенной задачей для программиста является рисование графиков. Входными данными является массив точек (xi;yi). Как правило, мы знаем только некоторые значения — в определенных точках графика. Чтобы построить непрерывный график кривой необходимо прибегнуть к интерполяции или аппроксимации.



Интерполяция — построение кривой, проходящей через заданные точки.
Аппроксимация — приближение кривой к исходной, но не обязательно проходящей через заданные точки.

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


Литература


Е.П. Кузьмин, Д.В. Иванов Алгоритмические основы компьютерной графики (лекция №4)
Интерполяция сплайнами
Оригинальная статья Акимы
Сравнение кубического и сплайна Акимы
Bezier Curves Made Simple

Википедия:
Многочлен Лагранжа.
Кубический сплайн
Кривые Безье
Владислав Росс @gag_fenix
карма
169,8
рейтинг 54,0
Пользователь
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (23)

  • +6
    P.S. Я знаю, что реализации C-spline уже есть для PHP, например в pChart, но сплайна Акимы и кривой Безье я нигде не нашел. С антиалиасингом в PHP тоже весьма тухло. Так что библиотекаа может быть весьма полезной.
    • 0
      Если сделать imageantialias ( resource $image, bool $enabled ) — линии будут с антиалиасингом.
      • 0
        Только линии, и только толщиной в один пиксель. Я лично, когда хочу антиалиаснг, использую pChart wiki.pchart.net
    • 0
      > например в pChart, но сплайна Акимы и кривой Безье я нигде не нашел
      В чистом виде там есть и Безье. Но, чтобы им рисовались графики — неа.
      wiki.pchart.net/doc.draw.bezier.html

      > Так что библиотекаа может быть весьма полезной.
      Если собирайтесь выкладывать код под GPL, то не плохо было бы запилить это все в pDraw.class, а затем опубликовать патч на форуме pChart'a.
  • 0
    Тем временем ChartDirector продолжает «продаваться» и рисовать графики быстрее и красивее :-)
    • +1
      a) он платный
      б) он поддерживает только интерполяцию сплайнами (видимо, кубическими)
      • 0
        Зато он на С. Он быстрый. У него есть API и модули практически под все распространенные языки.
        ОДин минус — цена
      • +1
        Иногда проще купить и использовать. Когда присутсвует разнообразие графиков или непредсказуемость требований, то 99 у.е за лицензию дешевле, чем оплата труда программиста, день работы которого меньше 50у.е. не стоит. Купив готовое проверенное решение платишь за подключение и настройку (пара дней максимум при готовых данных). Разрабатывая на основе своих наработок платишь за создание, подключение, настройку, оптимизацию. Труд программера в любом случае дороже выходит.
  • +2
    Под какой лиценизией вы выпускаете данный код?
    Планируете ли выложить его на какой-нибудь github?
    • 0
      Думаю, что GPL всех устроит. А вы что посоветуете?
      Библиотеку перенесу с хоумпаги, как только выполню todo list. С GitHub не работал, надо разобраться,
      • 0
        www.opensource.org/licenses/BSD-3-Clause — мне вот эта по нраву. Но я не настаиваю, вы же автор, вам и выбирать.
      • +1
        > GPL всех устроит

        Очень смелое заявление.

        Советую посмотреть, почему стоит выбрать более свободную BSD-like, а не GPL -> lionet.livejournal.com/31952.html
  • 0
    В «экселе» (вообще-то OOCalc и google docs) часто строю скользящее среднее и по ней кусочно-линейная.
  • 0
    А почему координаты в массиве array(x1 => y1)? Это не позволяет построить две точки с одинаковой X, что в свою очередь ограничивает исключительно графиками (а можно было бы рисовать произвольные кривые)
    • 0
      Насколько я понял, произвольные кривые может рисовать только метод Безье.
      Кубические многочлены, на которых строятся сплайны, не могут иметь 2 разных значения в одной точке X.
      • 0
        Возможно, но хотя бы Безье — ведь уже хорошо.
        • 0
          Ок — исправим :)
  • +1
    Я бы предложил взамен вот это. У него есть несоколько преимуществ и один недостаток:
    + не зависит от серверного языка
    + совершенно не нагружает сервер
    + на много больше возможностей
    — это не картинка, и соответственно теряет те свойства что имеют изображения
    • 0
      Если вам не надо кешировать картинки и есть определённая нагрузка то да, лучше JavaScript (Flash) решения.
  • +1
    Эх, помню, как реализовывал все это на Паскале более 10 лет назад :) Даже собрал потом все, что нашел, в архичвчик и выложил на своем сайтике на nador.ru.
  • +1
    Спасибо! Как раз искал что-то вроде сплайна Акимы. Теперь знаю, как это называется.
  • 0
    Для реализации сглаживания я рисовал кривую в отдельной картинке, затем применял размытие по Гауссу с помощью функции imageconvolution и уже потом накладывал картинку на оси.
  • 0
    Отличная библиотека, спасибо!

    Только вот в сплайне Акимы я разобрался, только разбив функцию на полдюжины других :-)
    Если интересует, могу скинуть переделанный код (правда, он на С++)

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.