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

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

Форум программистов > Алгоритмы > аппроксимировать меньшим кол-вом точек

Автор: mrgloom 19.9.2012, 13:23

т.е. есть кривая состоящая из точек, а надо её наилучшим образом сапроксимировать меньшим кол-вом точек.
http://www.ziegelmann.org/ziegelmann/Mark%20Ziegelmann-Dateien/Linear%20Curve%20Approximation.htm
http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A0%D0%B0%D0%BC%D0%B5%D1%80%D0%B0-%D0%94%D1%83%D0%B3%D0%BB%D0%B0%D1%81%D0%B0-%D0%9F%D0%B5%D0%BA%D0%B5%D1%80%D0%B0
что то типа такого.

интересуют алгоритмы и библиотеки.

Автор: baldina 19.9.2012, 13:33

правильно поставленный вопрос содержит ответ: используй CNOP.
что касается алгоритма, идея прям на той странице и изложена:
1. задать требуемую точность (если не задавать, замкнутые объекты будут вырождаться в треугольники, а незамкнутые - в прямые)
2. выкинуть/добавить точки таким образом, что бы минимизировать число точек при удовлетворении заданной точности. принцип простой: выкидываются все точки, лежащие на отрезке (в пределах точности), кроме крайних.

Автор: mrgloom 19.9.2012, 14:21

дело в том, что тут
http://www.ziegelmann.info/Mark%20Ziegelmann-Dateien/Linear%20Curve%20Approximation-Dateien/corsica200_s.gif
там где участок кривой прямой на нём нету точек, т.е. он просто заменяется отрезком, у меня могут быть довольно большие такие прямые отрезки, но мне надо что на этих отрезках кол-во точек просто уменьшилось ,а не стало =0.

Автор: baldina 19.9.2012, 14:47

Цитата(mrgloom @ 19.9.2012, 14:21

)

мне надо что на этих отрезках кол-во точек просто уменьшилось ,а не стало =0

сколько должно быть промежуточных точек?
нельзя ли избавиться от промежуточных точек, а потом, при необходимости, добавить?
меня очень занимает вопрос, зачем оставлять промежуточные точки

Добавлено через 2 минуты и 27 секунд
если прямолинейные участки должны иметь предельную длину, можно наряду с критерием точности ввести критерий максимального расстояния, и при его превышении точки не удалять.

Автор: Earnest 19.9.2012, 16:03

Дуглас-Пекер легко модифицируется на предмет максимального расстояния между точками. Просто добавляешь еще одно условие кроме проверки дистанции. На самом деле, это простой и быстрый алгоритм. Есть код, надо?
Но! если исходная кривая не гладкая (содержит мусор), то результат будет не очень. Лучше бы сначала отфильтровать (сгладить), а потом редуцировать.

Автор: mrgloom 20.9.2012, 09:57

мне просто надо чтобы плотность точек была примерно одинаковая(ибо я занимаюсь наложением 2-х наборов точек), это конечно не возможно,ибо там где кривизна больше там нужно больше точек для описания.

последний пост вроде похож на правду, попробую.

вот еще похожее
http://www.unseen-academy.de/snippet_timeconst_spline.html

еще непонятно как сами кривые делить.
т.е. у меня например есть от алгоритма канни контуры(алгоритм помоему не обещает однопиксельную толщину?) или просто контуры которые которые там пересекаются и т.д.
так вот скорее всего их надо предобработать, т.е. все точки сочленения где число соседей >2 являются особыми точками сочленения, а всё что между ними это кривые.

Автор: Earnest 20.9.2012, 12:49

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