Как уменьшить количество точек на кривой при сохранении ее общей формы?

У меня есть список точек, которые делают кривую, и я хотел бы уменьшить количество точек, но все равно сохранить общую форму кривой.

В принципе, я хочу перейти от этого:

Для этого:

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

Ответы

Ответ 1

Рассмотрим Douglas-Peucker_algorithm

Ответ 2

Для этого существует несколько алгоритмов.

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

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