Предисловие

Недавно на работе задали задачу — есть клиент с GPS устройством. Ходит, он значит по городу и записывает на это устройство каждую секунду координату своего местонахождения. Потом заходит на наш сайт и отправляет файл с записями маршрута. И в ответ получает изображение карты и поверх нарисованный маршрут по которому он двигался. Все вроде бы ничего, но есть одна проблемка — клиент может записывать хоть целый день и прислать громадный файл, а отрисовка маршрута занимает очень много времени. А он ведь мог идти по прямой линии и тогда смысл отрисовывать все точки отпадает(ценных только две крайних). Тем более рисуется она на JavaScript на клиентской стороне и если клиентская сторона это мобильное устройство вполне вероятно что маршрут он не увидит((
И потому мне надо было сделать небольшую оптимизацию — оптимально упростить ломанную линию. Для этой задачи существует метод Дугласа-Пекера, но на русском описания этого метода я не нашёл, поэтому я решил заполнить этот пробел рунета.