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

Question

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

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

К этому:

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

Answer 1

Рассмотрим Алгоритм Дугласа – Пеккера

Answer 2

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

Самый простой способ - просто удалить точку, угол между соседними точками которой ближе всего к 180 градусам, до некоторого порога или до тех пор, пока вы не достигнете желаемого количества точек.

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