Эффективное сглаживание линии и/или упрощение

Я создаю приложение для рисования в Actionscript (хотя мой вопрос не связан с Actionscript). Основная идея состоит в том, чтобы начать рисовать при нажатии мыши и отслеживать движения мыши. Чего я хочу достичь:

уменьшить "шум" мыши и
создавать более плавные линии.

Прямо сейчас, (1) проблематично, потому что я получаю тысячи движений мыши в течение нескольких секунд. Из-за (1) линия может выглядеть неровно. Какова текущая идея: когда пользователь заканчивает рисовать линию, я сохраняю все движения в массиве и уменьшаю их (медианный порог), а затем использую сплайн-алгоритм для воссоздания линии.

Любые лучшие подходы?

Ответ 1

См. Эффективная подгонка по кривой Сары Фрискен. Также доступно на странице автора.

Ответ 2

(натолкнулся на ваш вопрос, ища то же самое, и случилось соединить что-то свое)

http://willowsystems.github.com/jSignature/#/about/linesmoothing/

(SEO-совместимая ссылка к тому же: http://willowsystems.github.com/jSignature/%2523%252Fabout%252Flinesmoothing%252F.html)

Вы описываете проблему в два раза. 1. Вы хотите "упростить" данные захвата. 2. Вы хотите нарисовать красивую линию ( "подгонка кривой" ) внутри точек.

Simplify.js, цитируемый выше, действительно хорош, но он дает вам только очки. Для jSignature нам нужен суперэффективный, не отстающий алгоритм подгонки кривой.

См. ссылку выше для объяснения одного (нашего) подхода к фитингу (Безье или кубический) кривых между точками. Это позволяет вам удерживать линию, которую пользователь рисовал, и просто отставать от соединения последних двух координат, или вы можете упростить и перерисовать всю эту строку.

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

Демонстрационная ссылка использует 4-пиксельный пропуск при перемещении мыши. Это грубо, но хорошо для "упрощения" данных в режиме реального времени. Если у вас есть роскошь захватить весь ход и перерисовать его, конечно, используйте simplify.js.

Ответ 3

У Майка Бостока есть несколько хороших примеров здесь Упрощение линий. Он указывает, что алгоритм Douglas-Peucker хорошо известен. Однако Visvalingam выглядит более эффективным.