Привет,

Задача состоит вот в чем. У меня есть ломаная линия полученная от перемещений курсора. На выходе хочу получить гладкую кривую.
Но таких кривых будет много с большим количеством точек, поэтому нужно упрощать количество точек.
Приведу иллюстрацию отдаленно напоминающую чего я хочу добиться:

На картинке ломаная преобразована в кубическую кривую. А мне нужно в итоге получить квадратическую кривую(с 3 точками), её проще рисовать. Такого витка получить не получиться но основную идею я надеюсь вы уловили.

Просто сгладить ломаную с помощью алгоритма Cardinall B-Spline мне не достаточно так как он выдает кубические кривые для каждого из отрезков в ломаной. В итоге это все будет жутко жрать ресурсы.

Вобщем я в поисках эффективного алгоритма который сочитает в себе и сглаживание подобно Cardinall B-Spline, и упрощение количества отрезков.

По сути этот процесс обратный к растеризации кривой учитывая небольшое отклонение.

Если кто-то сталкивался с подобной задачей подскажите где копать.

ПС. На отличное решение данной задачи можно поглядеть в Adobe Flash(у меня CS4)

Это сообщение отредактировал(а) SwordOfDeath - 31.1.2011, 15:15

Да все тот же сплайн Безье, локальный. Хороший результат по гладкости дает использование направлений соседних "внешних" отрезков для сглаживания "внутреннего". Коэффициент выбрать по вкусу (т.е. абс. величину производной). Это даже как-то называется по умному, но я не помню. А точки предварительно нужно прореживать, например, полигональной аппроксимацией. 
А чтобы избавиться от дрожи еще и предварительно сгладить, гауссовым фильтром, например.
Нормально написанный код работает быстро и никаких особых ресурсов не жрет.

Спасибо, буду копать... Пока себе смутно представляю как сюда гауса применить О_О

Да легко. Простейший случай - берем окно размером 3 точки, фильтр будет такой {0.25, 0.5, 0.25}. Сглаживаем точки линии с таким фильтром. При этом предполагается, что точки более-менее эквидистантны. Если сильно не так, нужно ресемлировать.

Спасибо... Теперь до меня дошло = )

Для меня не важна скорость алгоритма сглаживания... даже наоборот лучше часть сложности отрисовки перебросить на сглаживание и аппроксимацию. И скорее всего тут не ресамплингом буду делать... а коэффициенты от расстояния...

Кажется все в голове прояснилось...
Как жаль что математику не учил =\

Нашел алгоритмы которые я искал!

Алгоритмы аппроксимации:
http://www.softsurfer.com/Archive/algorith...orithm_0205.htm
Алгоритм построения кривой из ломаной
http://en.wikipedia.org/wiki/Levenberg%E2%...uardt_algorithm
реализация LM на C:
http://www.messen-und-deuten.de/lmfit/lmfit.html

Видео:
http://www.youtube.com/watch?v=v63NAzQE7Bw

Вот это именно тот результат на который я рассчитывал.

Это сообщение отредактировал(а) SwordOfDeath - 1.2.2011, 18:41