Постепенное упрощение линии

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

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 тысячу раз, вместо этого я бы хотел, чтобы он обрабатывал мой набор постепенно, пересечения не имеют значения, дело просто в том, чтобы уменьшить размер набора данных с минимальным визуальным воздействием. Есть ли какой-нибудь разумный способ справиться с этой проблемой?


algorithm line simplification douglas-peucker
person Lu4    schedule 09.08.2017    source источник

Ответы (1)


arrow_upward
0
arrow_downward

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

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

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

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

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

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

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