Доброго дня!

Такая задача: 

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

Нужно упростить ее (получить новую ломанную) так, чтобы полученная ломанная была максимально приближена к оригиналу и состояла из m точек (2 <= m <=n).


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

Mastkir, я подобного сам не делал, но появилась следующая мысль:

на основании этой кривой строишь кривую Безье. Она будет непрерывна. Затем эту кривую поделить на участки с одинаковой длиной, так, чтобы их было m штук. Затем находим точки на кривой, которые так делят кривую и строят по ним ломаную.

Это не так легко реализовать, но больше ничего другого в голову не лезет...

JackYF, я думал примерно о таком способе (тока без построения кривой Безье - можно просто найти точки на ломанной, которые делят ее на m-1 отрезков, и находятся на ломанной через требуемый шаг).

Данный способ не годится например для ситуации, когда все точки (допустим, тысяча) находятся на одной прямой, и только одна точка рядом с прямой,  (пусть это будет 500-ая точка) и требуется сократить колличество точек до 5. Если делать описанным способом, получится прямая. Однако если выбрать в качестве требуемых точек 2 точки по краям, ту которая находится рядом с прямой, и две соседние от нее точки, то получившаяся ломанная будет выглядеть точно так-же, как и оригинал.

Мне щас кажется, больше подошел бы какой нибудь способ, связанный с расстановкой весов для каждой точки, чтобы веса определяли "степень полезности точки" - после сортировки оставить точки с максимальными весами, и все. Только придумать критерий определения весов, не могу :(. Очевидно, он должен быть связан с расстояниями и углами до соседних точек.

Есть простой алгоритм полигональной апроксимации. Правда, граничным условием там является точность приближения (т.е. максимальное расстояние до старой линии).  Скорее всего, можно его преобразовать так, чтобы удовлетворялось условие на число точек.
Алгоритм выглядит так:
берем первую и последнюю точки (если линия замкнутая, то первую и предпоследнюю);
находим вершину (среди остальных), максимально отстоящую от отрезка соединяющего эти вершины;
если отстояние этой самой далекой точки < eps, выкидываем все промежуточные точки;
в противном случае точно также рассматриваем 2 полученных промежутка: между первой и найденной, затем между найденной и последней.
В результате получится ломаная, гарантировано отстоящая от заданной не далее чем на eps. Причем на плавных участках точек будет меньше, на извилистых - больше.
Чтобы загнать в заданное число точек, можно постепенно огрублять eps - самое тупое, что в голову приходит.
Есть алгоритм на C++.

Earnest, спасибо за алгоритм.  

Правда, я щас использую алгоритм, связанный с расстановкой весов для каждой точки:
1. Для всех точек определяются веса (расстояние от точки до отрезка, соединяющего две соседние точки).
2. Удаляется точка, имеющая минимальный вес. При этом у соседних точек веса пересчитываются.
3. Пункт 2 повторяется, пока не будет удалено достаточное число точек.

Тоже неплохой результат получается 

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