Блог

Недавно я изучил несколько различных методов упрощения полигонов.

Популярные методы включают алгоритм упрощения пути Рамера-Дугласа-Пекера и Visvalingam, хотя оба они являются хорошими алгоритмами, в некоторых случаях дают плохие результаты, только удаляя точки, никогда не размещая точки в новых местах (как за, так и против в зависимости от использования).

Я изучал возможность использования упрощенного метода свертывания сегментов, общего для 3D-геометрии, см.: Упрощение поверхности с использованием метрик квадрических ошибок.

Из некоторых быстрых тестов это работает достаточно хорошо, однако я подозреваю, что это не все, что ново, возможно, есть и лучшие методы для 2D-полигонов.

Я также изучил метод упрощения полигонов PO-Trace, который является превосходным, но сосредоточен на упрощении полигонов, извлеченных из растровых изображений.

Существуют ли хорошо известные алгоритмы упрощения полигонов с использованием свертывания сегмента?

Спрашиваю, потому что я собираюсь написать свою собственную функцию, которая использует метрики ошибок quadric, но подозреваю, что это может уже существовать, возможно, с другим именем.

Если нет, я свяжу код, как только он будет готов.

Библиотека CGAL предоставляет реализацию алгоритма упрощения полилиний.

Он основан на работе Дайкена и др.