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

Question

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

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

Answer 1

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

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

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

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

Answer 2

То, что вы, скорее всего, после, называется Curve Fitting.

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

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

---

Что касается примера Paper.js:

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

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

Answer 3

В моем случае я нашел, что сплайны Catmull-Rom Splines проще всего применять. Smooth Paths Using Catmull-Rom Splines статья из Mika's Coding Bits очень полезна. Я использовал его для реализации скрипта интерполяции сплайнов на C# в моем проекте Unity3D. Это сценарий:

public static Vector2 CatmullRomInterpolation(Vector2 p0, Vector2 p1, Vector2 p2, Vector2 p3, float t, float alpha = .5f, float tension = 0)
{
    float t01 = Mathf.Pow(Vector2.Distance(p0, p1), alpha);
    float t12 = Mathf.Pow(Vector2.Distance(p1, p2), alpha);
    float t23 = Mathf.Pow(Vector2.Distance(p2, p3), alpha);
    Vector2 m1 = (1.0f - tension) * (p2 - p1 + t12 * ((p1 - p0) / t01 - (p2 - p0) / (t01 + t12)));
    Vector2 m2 = (1.0f - tension) * (p2 - p1 + t12 * ((p3 - p2) / t23 - (p3 - p1) / (t12 + t23)));
    return (2.0f * (p1 - p2) + m1 + m2) * Mathf.Pow(t, 3) + (-3.0f * (p1 - p2) - m1 - m1 - m2) * Mathf.Pow(t, 2) + m1 * t + p1;
}

p0 и p3 - это контрольные точки, которые должны отличаться от p1 и p2, которые являются начальной и конечной точками вашего пути.