Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Сглаживание ломаной с помощью кривой Безье

Автор: evilguard 20.3.2007, 20:29

У меня есть координаты точек ломаной. Использую библиотеку QT для GUI - там есть свой графический движок, и в частности такая функция:
http://doc.trolltech.com/4.1/qpainterpath.html#cubicTo
В функцию в качестве аргументов задаются 3 точки c1, c2 и endPoint. Функция чертит кривую из текущей точки в endPoint, c1 и c2 используются для задания кривизны. Вопрос, как с помощью этого инструментария сгладить ломаную в плавную линию? Надо каким-то образом задать параметры c1 и c2, чтобы производные двух кривых в общей точке совпадали.

Автор: SoWa 20.3.2007, 20:51

Код функции в студию!
А то алгоритмов можно кучу придумать, чтобы кривизну придавать. И производная в декартовых координатах - не предел мечты. Может там с полярными неплохо можно поколдовать?

Или там кода как раз нету?

Автор: evilguard 20.3.2007, 21:13

SoWa
В смысле, а код функции разве нужен? Это же вроде как стандартно для кривой безье - две опорные точки и две управляющие.
Код порылся не нашел. Я имел в виду, используя данную функцию, то есть что-то типа:

Код


//points - контейнер точек ломаной, которую надо сгладить
moveTo(points[0])
for (i=1; i<points.size(); i++)
   cubicTo(c1[i], c2[i], points[i]);

мы можем подобрав координаты управляющих точек кривой безье сгладить ломаную в том числе и в точках перелома.
вопрос в том как подобрать параметры c1 и c2.

Автор: Earnest 20.3.2007, 22:19

Опорные точки можно по-разному трактовать. Так что кто знает, как там они считают. Кстати то, что там по ссылке нарисовано, как-то странно выглядит... Мне кажется удобным использовать опорные точки так, чтобы они вместе с началом-концом задавали четырехугольник, в который кривая некоторым образом вписывается. Эти точки вычисляются как начало (конец) + касательный вектор, амплитуда которого определяет высоту горба. Если хочешь, могу привести все вычисления с нуля (на С++).

Автор: MBo 20.3.2007, 22:20

Рассчитай какие-либо кубические сплайны (да хоть Кэтмулл-Рома, раз гладкости по первой производной хватит), и переведи их в форму Безье (в базис полиномов Бернштейна)

Автор: Earnest 20.3.2007, 22:34

Да, действительно, чтобы кривая гладко и красиво прошла через все точки, не стоит строить отдельные кривые между каждой парой точек - получишь кучу ничем не вызванных извивов. Лучше сплайны. И в форму Безье их вовсе не обязательно переводить - чем сплайны-то хуже.

Автор: evilguard 20.3.2007, 23:00

Проблема в инструментарии, используемого мной API - он мне дан в виде такой функции - cubicTo. Проверил ее - вроде она строит настоящую кривую Безье, то есть вписанную в четырехугольник, образованный точками currentpoint, c1, c2 и endpoint, и по окончании перемещает текущую точку в endpoint. Кривая касается отрезков. Так что в библиотеке все нормально.
В принципе я понял примерно как это сделать, надо находить координаты точек c1 и c2 так, чтобы для одной опорной точки соседние управляющие точки лежали на одной прямой. Это еще пол-беды, то есть мы только направление вектора определили, а как правильно подобрать амплитуду?

Earnest
Код конечно можно, спасибо, но мне нужно использовать инструментарий библиотеки QT - то есть ту функцию.

Автор: evilguard 20.3.2007, 23:26

http://keep4u.ru/full/070320/91c47d9797242da533/jpg
Вот рисунок, с небольшой иллюстрацией. Точки А1, А2, А3 - точки ломаной, которую хочу сгладить. Данная ломаная сглаживается двумя кривыми - (А1, с1, с2, А2) и (А2, с3, с4, А3). Надо то есть найти подходящие координаты точек с1, с2, с3, с4. Я делал так(в painte) - с2 лежит на биссектрисе между векторами А2А1 и А3А2, с3 лежит на биссектрисе А1А2 и А2А3. Тогда точки с2 и с3 будут лежать на одной прямой. Это все можно алгоритмизировать. То есть направление - по биссектриссе. Но как найти амплитуду, то есть расстояние от А2 до с2 или с3. В этом проблема.

Автор: MBo 21.3.2007, 08:04

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

Для использования готового графического примитива

>Но как найти амплитуду, то есть расстояние от А2 до с2 или с3. В этом проблема.

Ты прочитал о сплайнах Кэтмулл-Рома? (их я взял для примера, как весьма простые)

Добавлено @ 08:07
Вот еще несложный метод:
http://www.antigrain.com/research/bezier_interpolation/index.html#PAGE_BEZIER_INTERPOLATION

Автор: Earnest 21.3.2007, 08:44

Цитата(evilguard @ 21.3.2007, 00:00

)

Это еще пол-беды, то есть мы только направление вектора определили, а как правильно подобрать амплитуду?

Ага, хорошо, меня картинка там нарисованная сбила.
Амлитуда определяется огранолептически - шоб красиво было. Я обычно использую треть отрезка, соединяющего начало и конец - это когда речь об одном отрезке. У соседних сегментов вектора производных должны быть противоположны и равны по амплитуде. Стало быть надо как-то усреднять.

В ссылке MBo вроде примерно это и есть.

Автор: evilguard 21.3.2007, 09:08

Спасибо за ссылку! Отличный метод! Буду использовать его. Единственно его надо дополнить, в случае построения ломаной а не полигона первую и последнюю точку надо будет рассматривать отдельно.