Интерполацията чертае гладки графики с помощта на PHP и GD

Често срещана задача за програмиста е да чертае графики. Входните данни са масив от точки (xi;yi). По правило знаем само някои стойности - в определени точки на графиката. За да изградите графика на непрекъсната крива, трябва да прибегнете доинтерполацияилиапроксимация.

гладки

Интерполация - построяване на крива, минаваща през дадени точки. Апроксимация - приближаване на кривата до оригинала, но не е задължително да минава през дадените точки.

В тази нишка искам да покажа моята PHP библиотека, която извършва интерполация с полином на Лагранж, C-сплайн и сплайн на Акима, както и апроксимация на кривата на Безие. Освен това, той реализира изобразяване на сегмент с изглаждане (анти-алиасинг).

Нека разгледаме накратко методите за интерполация и приближение.

Частично линейна интерполация

Първото нещо, което идва на ум, е да свържете точките със сегменти:

гладки

Най-доброто решение по отношение на скоростта, но получената графика се оказва счупена - това не е това, от което се нуждаем.

Интерполационен полином на Лагранж

Полином от степен n за n+1 точки. Формулата му е съвсем проста:

Лесен за изпълнение, но има два сериозни недостатъка: 1) изисква значително количество изчисления 2) държи се непредвидимо между дадени точки (възли)

гладки

Кубичен сплайн (c-сплайн)

Кубичният сплайн е лишен от недостатъците на предишния метод. За всеки интервал между възлите се определя полином със степен най-много 3, докато първата и втората производна на функцията трябва да са непрекъснати. От една страна, това опростява изчисленията, а от друга страна ви позволява да избегнете острискокове на кривината.

графики

Пренесох изпълнението на кубичния сплайн от C# кода, взет от Wikipedia.

Сплайн Акима

Кубичните сплайни имат недостатък: в района на точка, която е далеч от своите съседи, такива сплайнове могат да направят неочаквани „емисии“. Този проблем може да бъде решен с помощта на сплайни, предложени от Хироши Акима. Имайте предвид, че сплайнът на Akima е по-стабилен:

гладки

Пренесох внедряването на сплайн на Akima от C кода на debian aspline на Дейвид Фрей.

Апроксимация на кривата на Безие

Понякога е полезно да не чертаете крива през дадени точки, а да ги използвате като референтни точки. Методът на кривите на Безие ще ни помогне в това (пренесох кода от C # примера на Tolg Birdal). Кривата минава през първата и последната точка

гладки

Тестване на производителността

Проведено за графика 500x500 без рендиране на Xeon 5560 2.8GHz сървър, брой експерименти = 1000. Средно време за изпълнение, s:

Брой точки:51550
Полином на Лагранж1,7895,66420,446
кубичен сплайн0,1530,2300,313
Сплайн Акима0,0170,0240,049
крива на Безие0,2440,2760,304
От горната таблица могат да се направят следните заключения: 1) Времето за изчисляване на полинома на Лагранж нараства бързо с увеличаване на броя на точките. 2) Сплайнът на Акима е по-бърз от кубичния. 3) Изграждането на крива на Безие е по-бавно от сплайновете.

Избор на метод

Ако трябва да начертаете крива през известни точки, бих препоръчал да използвате сплайн на Акима. Ако самите точкине играят голяма роля, тогава бих приближил сюжета с крива на Безие.

Антиалиасинг

Изграждането на крива в gd библиотеката може да се извърши чрез сегменти. За да направите това, кривата се разделя на участъци с определена стъпка (поне 1 пиксел) и между началото и края на участъка изчертаваме сегмент с помощта на функцията imageline. PHP обаче ще изобрази такъв сегмент без анти-алиасинг. На помощ идва алгоритъмът Wu за изчертаване на сегмент с изглаждане на екрана. Алгоритъмът на Wu може да чертае само сегменти под ъгъл от ±45 °, така че в други случаи трябва да се "завърти". Фигурата показва графика на функцията sin (x) без антиалиасинг и нищо по-долу - с антиалиасинг.

чертае

Библиотека

За всеки метод на интерполация/апроксимация написах отделен клас: LagrangePolynomial, CubicSpline, AkimaSpline, BezierCurve. Всеки клас има 3 публични метода: setCoords(&coordinates, step, [x_min, [x_max]]) — задава първоначалните координати и параметри за конструиране на кривата, връща false в случай на грешка process() — връща масив от координати за конструиране на кривата getError() — връща съобщение за грешка Координатите се прехвърлят като масив масив (x1 => y1, x2 => y2… xn => yn)

За начертаване на графика е имплементиран спомагателен клас Plot. Неговите възможности са много скромни (например, няма мащабиране - графиката се изчертава 1:1), така че можете да използвате друг клас или собствени PHP функции вместо това. Методи: Конструкторът получава масив от координати. drawLine(image, color, [x0, [y0]]) - рисува полилиния, image - идентификатор на ресурс, цветът трябва да бъде зададен на imagecolorallocate, x0 и y0 - отместване на началото (по подразбиране - в долния ляв ъгъл на изображението) drawAALine(image, color, [x0, [y0]]) -чертае полилиния с антиалиасинг на сегменти, параметри подобни на drawLine drawDots(image, color, [x0, [y0, [size]]]]) — рисува точки без свързващи сегменти, параметри подобни на drawLine, размер — диаметър на точката първия квадрант - в положителна посока

Пример (функция sin(x):

//За удобство нека зададем размерите предварително 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 ;

//Създаване на изображение с истински цветове (за антиалиасинг) $im =imagecreatetruecolor(GRAPH_W >, 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 -> рисуване на точки ($im, $dotColor, GRAPH_W >/ 2, GRAPH_HEIGHT / 2, 5);

//Създаване на сплайн обект $curve = new CubicSpline ( ) ; //Подаваме му координати, стъпка на изобразяване = 5 $curve -> setCoords ($testCoords, 5); if ( ! $curve -> getError ( ) ) < //Изчисляване на координатите на крива $curveCoords = $curve -> процес(); ако ( $r ) < //Друг обект на диаграма $curveGraph = нов график ($curveCoords) ; //Чертане на крива $curveGraph -> drawLine ($im, $graphColor, GRAPH_W >/ 2, GRAPH_HEIGHT / 2); > >

//Дайте на потребителя заглавие ( "Content-type: image/png" ); imagepng ($im); imagedestroy ($im); ?>