Упрощение полилинии при уменьшении масштаба

На карте нарисована ломаная линия из большого количества отрезков с заданными координатами.
То есть множество (сотни, тысячи) точек последовательно соединяются отрезками.
Такое большое количество объектов не очень хорошо сказывается на скорости работы браузера.
Хочется убрать точки, которые все равно на конечную фигуру заметного (видимого) влияния не оказывают.
Если речь идет о близкорасположенных точках, то для них есть то, что в картографических сервисах называется кластеризацией.
А как поступать с точками, которые расположены недостаточно близко друг к другу, но при этом находятся очень близко к линейной траектории? Другими словами, вместо 100 точек, рисующих чуть изогнутую траекторию, оставить 3 точки, рисующих ломанную, близкую к прямой линии.

Alibek B.
вместо 100 точек, рисующих чуть изогнутую траекторию, оставить 3 точки, рисующих ломанную, близкую к прямой линии.

На самом деле вместо 50 точек оставить 2 точки, отрезок между которыми отклоняется по ломаной не более чем на заданное расстояние. Первых 50, и вторых 50. Ну и учесть, что отрезки должны иметь одну общую конечную точку.

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

Точки на линии могут быть различными — есть активные точки (в которых, например, присоединяются другие линии или объекты), есть транзитные точки, которые просто задают маршрут. У всех точек есть дополнительная информация, но на отрисовку линии она не влияет. Активные точки на упрощенной линии должны остаться обязательно, транзитные должны упроститься до минимума.

Например такой алгоритм:
1. Беру две ближайшие активные точки.
2. Промежуточные точки кластеризую, получаю некоторое количество "упрощенных" транзитных точек.
3. Провожу линию между активными точками, нахожу наиболее удаленную упрощенную транзитную точку.
4. Если эта точка отстоит не далее порогового значения, то цикл завершен и перехожу к следующим активным точкам.
4. Считаю эту точку активной и итеративно повторяю цикл сначала (пропуская пункты 2 и 3).

Так?

Alibek B.,
Начни с построения выпуклой оболочки. Принятые точки берешь за базис, для остальных делаешь решающее правило исходя из масштаба и отклонения.

Alibek B.
Так?

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

Alibek B.,
довольно примитивый алгоритм:

автор

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

http://www.lesis.ru/doc/_toc2_6_3_0.html

Классический алгоритм для упрощения полилиний - алгоритм Дугласа-Пекера