Кривая по точкам

[vaprele07]

вот кривая по заданным точкам:

Код:

QPainterPath createPath(QPointF cord, QList<QPointF> points)
{
  while (points.count() % 3 != 0)
    points << points.at(points.count() - 1);
          
  QPainterPath path;
  path.moveTo(cord);
  int i = 0;
  while (i + 2 < points.count()){
    path.cubicTo(
      points.at(i), 
      points.at(i + 1), 
      points.at(i + 2)
    );
    i += 3;
  } 
  return path;     
}

Racheengel, объясни что в ней не так  :roll:

[Alex Forth]

В том то и дело, что это два принципиально разных подхода к построению сплайна: по контрольным точкам и по реальным.
Мне нужно было построение по реальным.

Чем они отличаются???

2vaprele07 Так как ты написал, ч-з каждые 3 точки будет излом.

[Racheengel]

vaprele07, мы пробовали подобный подход ранее. Он нас не устроил из-за того, что кривая получалась неравномерной, и заказчику это очень не нравилось. Пришлось искать альтернативные алгоритмы, мы нашли то что надо в исходниках Qwt 5 (сколько тут на него ни гнали, но свои плюсы в нем таки есть).

Alex Forth, отличаеюся они идеологией построения и задания начальных параметров. Возможно, один способ и можно привести к другому, но это будет слишком трудно...

[Alex Forth]

Alex Forth, отличаеюся они идеологией построения и задания начальных параметров. Возможно, один способ и можно привести к другому, но это будет слишком трудно...

Можно конкретнее, в чем разница?

[Racheengel]

Ну вот как тебе будет проще кривую построить:
задать массив координат (х.у) точек, через коротую она должна проходить,
или задать массив контрольных точек, которые находятся неизвестно где в пространстве, предварительно их просчитав?
Лично я вообще не понимаю, зачем нужны функции построение по контрольным точкам. КАК и ГДЕ их можно использовать?

[Alex Forth]

Вроде как понял - это разные задачи и не стоит их смешивать.
 Первый случай - это интерполяция. Это то что нам нужно для красивого отображения данных, снятых с датчика. Тут нам нужно нарисовать гладкую кривую, которая проходит ч-з все полученные точки.

Второй вариант, я так понял, - это аппроксимация. В этом случае у нас опять есть набор полученных в результате эксперимента точек. Также мы знаем общий вид зависимости, которая соответствует нашим точкам. Тут зависимость - это формула, но с неизвестными коэфициентами. Например y=Asin(bx+c). Для решения задачи нам необходимо найти все эти коэфициенты по известным точкам. Дополнительное условие - точки не обязательно точно соответствуют закономерности, так как датчики имеют некую погрешность.

[Racheengel]

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

А второй способ построения сплайнов - отрезками из 2-х точек (начало и конец), плюс еще одна или две контрольных. Меняя положение контрольных точек, меняется вид сплайна, но сказать, через какие точки он пройдет, заранее невозможно. В итоге сплайн, состоящих из таких вот кусочков, получается не гладкий, а с изломами в узлах. Лично мне вообще трудно найти применение такому подходу.

[Sergeich]

Рисовать сплайн между двумя точками хуевой тучей мелких отрезков не есть гуд. Рисовать надо кривыми Безье (cubicTo) - для их построения применяются оптимизированные алгоритмы и вычисления могут идти на хардварном уровне.
  Контрольные точки элементарно получаются из коэффициентов сплайна:
CP1 = P0 + 1/3*C
CP2 = P0 + 2/3*C + 1/3*B,
где CP1, CP2 - котрольные точки, P0 - точка от к-ой ты ведешь кривую, С и B - коээфициенты сплайна.
  Построение сплайна нагло пиздим (для использования в закрытых исходниках  :lol: ) из QwtSpline::buildNaturalSpline для незамкнутых кривых и из QwtSpline::buildPeriodicSpline для замкнутых. Вычисляем коэффициенты сплайнов x(t) и y(t), приняв t=0,1,2,... и по приведенным формулам получаем контрольные точки. Строим QPainterPath. Идем пить пиво
  Пример кода в аттаче.

[Alex Forth]

Звучит конечно круто!
Но хочу заметить, что на наиболее распространный девайс для отображения графиков - это монитор, который, увы, является растровым девайсом. Следовательно от кучи отрезков никуда не деться. Единственного помошника я вижу в видеокарте. Вполне возможно, что она умеет на своем процессоре произвести все вычисления и сгенерить все эти отрезки. Если кто знает, как все это сделать на прикладном уровне, то я снимаю шляпу
Кривая Безье  третего порядка, как и кубический сплайн, основывается но полиноме третего порядка. Посему я очень сильно сомневаюсь в том, что тут есть какая-то разница в затратах на расчет.
Насколько я знаю, контрольные точки в кривых Безье используются для задания направления выпуклости кривой. Это все просто замечательно, но зачем нам такая возможность для интерполяции???
Посему мой выбор - сплайны!  

[Sergeich]

Насколько я знаю, контрольные точки в кривых Безье используются для задания направления выпуклости кривой. Это все просто замечательно, но зачем нам такая возможность для интерполяции???
Посему мой выбор - сплайны!

Мда... Кубический сплайн - это несколько кривых 3-ого порядка, соединенные вместе, в точках соединения требуется равенство первой и второй производной. Кубический сплайн Безье - это несколько кривых Безье 3-ого порядка, соединенных вместе и требующих  опять же равенства первых и вторых производных в точках соединения. Полином третьего порядка записывается в виде: At^3 + Bt^2 + Ct + P0, кривая Безье: P0(1-t)^3 + P1(1-t)^2*t + P2(1-t)*t^2+P3*t^3. Очевидно, что между их коэффициентами существует взаимооднозначное соответствие. Поэтому НИКАКОЙ РАЗНИЦЫ МЕЖДУ НИМИ НИХУЯ НЕТУ, кроме формы записи.
Только в случае если ты нашел коэффициенты сплайна, при растеризации ты должен сам рассчитывать промежуточные точки между опорными с каким-то хитро выбираемым шагом, чтобы все это выглядело как гладкая кривая. Если же ты переведешь рассчитанные коэффициенты в коэффициенты кривой Безье (aka контрольные точки) - всеми расчетами за тебя будет заниматься библиотека, плюс ты получишь стандартное переносимое представление кривой, к-ое можно сохранить хоть в SVG, хоть в PostScript.

[Alex Forth]

Только в случае если ты нашел коэффициенты сплайна, при растеризации ты должен сам рассчитывать промежуточные точки между опорными с каким-то хитро выбираемым шагом,

Ничего хитрого, ч-з пиксель и вперед. Наверняка библиотесная  реализация кривых безье также делает.

Если же ты переведешь рассчитанные коэффициенты в коэффициенты кривой Безье (aka контрольные точки) - всеми расчетами за тебя будет заниматься библиотека,

Библиотечные реализации сплайнов тоже есть. Да и работы там - лабораторная для студента.

ты получишь стандартное переносимое представление кривой, к-ое можно сохранить хоть в SVG, хоть в PostScript.

За SVG и PS зачет.   О них я как-то не вспомнил. Я привык данные от датчиков в файлы лить. Картинки при это генерить не приходилось.

[Sergeich]

Только в случае если ты нашел коэффициенты сплайна, при растеризации ты должен сам рассчитывать промежуточные точки между опорными с каким-то хитро выбираемым шагом,

Ничего хитрого, ч-з пиксель и вперед. Наверняка библиотесная  реализация кривых безье также делает.

Оно не так уж просто. "Жизнь намного разнообразнее"(с) Посмотри, например, реализацию в qbezier.cpp (flattenBezierWithoutInflections(QBezier &bez, QPolygonF &p))

Если же ты переведешь рассчитанные коэффициенты в коэффициенты кривой Безье (aka контрольные точки) - всеми расчетами за тебя будет заниматься библиотека

Библиотечные реализации сплайнов тоже есть. Да и работы там - лабораторная для студента.

Имелись в виду не реализации построения сплайна ( вычисления его коэффициентов ), а реализация рендеринга, к-ая с учетом произвольной ширины кривой, произвольного шаблона штриховки и антиалиасинга, вообщем-то нетривиальна.

[kotofay]

В GDI+ есть отрисовка как по контрольным точкам так и по узлам.
Для винды только

[BaltikS]

Сергееич, мне понравился твой пример с сплайном. Попытался переписать функцию для периодического сплайна. Но не вышло. QPainterPath пустой. Видимо что то с коэф. не так. Привожу пример переписанной функции:

Код:

bool buildPeriodicSpline( int size, double* t, double* p, double* a, double* b, double* c )
{
	int i;
	//  set up tridiagonal equation system; use coefficient
	//  vectors as temporary buffers
	double* h = new double[size-1];
	double* d = new double[size-1];
	double* s = new double[size];
	for (i = 0; i < size - 1; i++) 
	{
		h[i] = t[i+1] - t[i];
		if (h[i] <= 0) {
			//h[i] = 0.1;
			delete[] h;
			return false;
		}
	}

	const int imax = size - 2;
	double htmp = h[imax];
	double dy1 = (p[0] - p[imax]) / htmp;
	for (i = 1; i < imax; i++)
	{
		b[i] = c[i] = h[i];
		a[i] = 2.0 * (htmp + h[i]);

		const double dy2 = (p[i+1] - p[i]) / h[i];
		d[i] = 6.0 * ( dy1 - dy2);
		dy1 = dy2;
		htmp = h[i];
	}

	//
	// solve it
	//

	// L-U Factorization
	a[0] = sqrt(a[0]);
	c[0] = h[imax] / a[0];
	double sum = 0;

	for(i = 1; i < imax - 1;i++)
	{
		b[i] /= a[i];
		if (i > 0)
			c[i] = - c[i-1] * b[i-1] / a[i]; 
		a[i+1] = sqrt(a[i+1] - b[i]*b[i]);
		sum += c[i]*c[i];
	}
	b[imax-1] = (b[imax-1] - c[imax-2]*b[imax-2])/a[imax-1];
	a[imax] = sqrt(a[imax] - b[imax-1]*b[imax-1] - sum);
	//a[imax] = sqrt(a[imax] - (b[imax-1] - sum)*(b[imax-1] - sum));

	// forward elimination
	//double* s = new double[size];
	s[0] = d[0] / a[0];
	sum = 0;
	for ( i = 1; i < imax; i++)
	{
		s[i] = (d[i] - b[i-1]*s[i-1]) / a[i];
		sum+=c[i-1]*s[i-1];
	}
	s[imax] = (d[imax] - b[imax-1]*s[imax-1] - sum) / a[imax];

	// backward elimination
	s[imax] = - s[imax] / a[imax];
	s[imax-1] = -(s[imax-1]+b[imax-1]*s[imax]) / a[imax-1];
	for (i = imax-2; i >=0; i--)
		s[i] = - (s[i] + b[i] * s[i+1]+c[i]*s[imax]) / a[i];
	

	//
	// Finally, determine the spline coefficients
	//
	s[size-1] = s[0];
	for (i = 0; i < size - 1; i++)
	{
		a[i] = ( s[i+1] - s[i] ) / ( 6.0 * h[i]);
		b[i] = 0.5 * s[i];
		c[i] = ( p[i+1] - p[i] ) / h[i] 
		- (s[i+1] + 2.0 * s[i] ) * h[i] / 6.0; 
	}

	return true;
}

[Sergeich]

Добавил к предыдущему коду построение периодических сплайнов, они строятся если последняя точка QPolygonF совпадает с первой. Код в аттаче.