Инкрементальное упрощение линии

Question

В интернете много информации об упрощении обычных линий,

https://www.jasondavies.com/simplify/

https://bost.ocks.org/mike/simplify/

http://geomalgorithms.com/a16-_decimate-1.html

http://mourner.github.io/simplify-js/

т.е. когда упрощенные точки известны заранее. Алгоритм Дугласа-Пекера, алгоритм Висвалингама, но что делать, если параметр допуска фиксирован и точки не известны заранее. У меня много точек, и я бы не хотел запускать алгоритм N * Log(N) M тысячу раз, вместо этого я хотел бы, чтобы он обрабатывал мой набор постепенно, пересечения не имеют значения, смысл просто уменьшить Размер набора данных с минимальным визуальным воздействием. Есть ли какой-нибудь умный способ справиться с этой проблемой?

Answer 1

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

В псевдокоде:

Let C be the original chain
Let R be the reduced chain (initially empty)

Add the first point of C to R
For every subsequent point p of C:
    If distance(p, the last point of R) >= ε:
        Add p to R

Что этот подход гарантирует:

• Длина каждого сегмента в сокращенной цепочке будет не менее ε
• Расстояние Хаусдорфа между цепями будет не более ε

Что это не гарантирует:

• Отсутствие самопересечения
• Любой вид оптимальности (может быть другая цепочка, которая ближе по Хаусдорфу и меньше по количеству точек)