Алгоритм упрощения траектории и сглаживания двумерных траекторий

Я ищу алгоритм для упрощения пути и сглаживания для 2D-траекторий. Итак, у меня есть упорядоченный список 2D-точек. Эти точки следует упростить, например, с помощью алгоритма Рамера–Дугласа–Пекера. Но выход должен быть гладким, поэтому результирующий путь должен быть построен из кривых Безье или сплайнов. Существует ли какая–либо модификация алгоритма Рамера–Дугласа-Пекера, которая могла бы справиться с этим?

Я нашел алгоритм упрощения пути в статье.библиотека js, которая делает именно то, что я ищу: http://paperjs.org/examples/path-simplification/ но я не смог понять алгоритм из недокументированного исходного кода javascript.

2 6
algorithm computational-geometry

2 ответа:

Работа, которую вы хотите выполнить, попадает в категорию "подгонки кривой". Существует множество различных алгоритмов подгонки кривых, но почти все алгоритмы подгонки кривых можно разделить на две различные категории: интерполяцию и аппроксимацию. Алгоритмы интерполяции создают кривую, которая проходит точно через все точки данных, в то время как алгоритмы аппроксимации создают кривую, которая лежит близко к точкам данных. Конечно, существуют и гибридные алгоритмы.

Так как вы хотите, чтобы точки данных должны быть сглажены, вы должны искать алгоритмы аппроксимации. Для двух алгоритмов, которые вы упомянули: алгоритм RDP и алгоритм Шнейдера (тот, что в статье.js), они оба являются алгоритмами аппроксимации. Так что, в принципе, вы можете использовать любой из них. Для RDP, после получения упрощенного пути, вы можете использовать create a Catmull Rom spline или Overhauser spline через вершины упрощенного пути, чтобы получить гладкую кривую. Однако у вас нет прямого контроля за отклонением между результирующим сплайном и вершинами исходного пути.

Для алгоритма Шнайдера он будет начинаться с подгонки точек данных по кубической кривой Безье с конечными касательными ограничениями. Если отклонение от результирующей кривой слишком велико, то она разделит точки данных на две "области" и поместит каждую область данных с кубическими кривыми Безье с ограничениями концевого касательного. Этот процесс будет повторяться до тех пор, пока отклонение всех кубических кривых Безье не станет достаточно малым. Как в результате получается ряд кубических кривых Безье, связанных в лучшем случае с непрерывностью C1 (очень вероятно, что на самом деле это только G1). Кроме того, поскольку этот алгоритм оценивает конечные тангенсы из исходных точек данных, шум в точке данных будет влиять на оценку конечного тангенса и, следовательно, на кубическую подгонку Безье.

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

10

То, что вы, скорее всего, после того, как называется подгонка Кривой.

В то время как алгоритм Рамера-Дугласа-Пекера существенно сглаживает " шум " из полилинии, удаляя ненужные точки - алгоритм подгонки кривой будет соответствовать кривым Безье через эти точки.

Здесь это довольно хороший пример на Youtube и здесь это оригинальная статья, описывающая сам алгоритм.

Что касается бумаги.JS пример:

  • Это является ли ссылка Github для этой конкретной функциональности вы упомянули, и это довольно хорошо прокомментировано. Исследовательская работа, которая был использован есть это.

  • Также здесь это очень короткая дискуссия в списке рассылки о что было использовано, а что нет (по-видимому, использовался Ramer-Douglas-Peucker но убрали позже)

4