т.е. есть кривая состоящая из точек, а надо её наилучшим образом сапроксимировать меньшим кол-вом точек. 
http://www.ziegelmann.org/ziegelmann/Mark%...proximation.htm
http://ru.wikipedia.org/wiki/%D0%90%D0%BB%...%B5%D1%80%D0%B0
что то типа такого.

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

Это сообщение отредактировал(а) mrgloom - 19.9.2012, 13:31

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

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

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

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

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


Присоединённый файл ( Кол-во скачиваний: 10 )
 PolyApprox.rar 2,09 Kb

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


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


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

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

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