Гладкая полилиния с минимальной деформацией

У меня есть двухмерная замкнутая полилиния, которая достаточно гладкая. Вершины, которые определяют ломаную, однако, не одинаково разнесены. Иногда двое будут очень близко, иногда целых четыре будут очень близко друг к другу.

Я хотел бы сгладить ломаную линию, но обычный алгоритм усреднения имеет тенденцию уменьшать область:

for (int i = 0; i < (V.Length-1); i++)
{
   PointF prev = V[i-1]; //I have code that wraps the index around.
   PointF next = V[i+1];       
   PointF pt = V[i];

   float ave_x = one_third * (prev.X + next.X + pt.X);
   float ave_y = one_third * (prev.Y + next.Y + pt.Y);

   smooth_polyline[i] = new PointF(ave_x, ave_y);
}

Мои полилинии содержат тысячи точек, а угол между двумя соседними сегментами обычно меньше 1 градуса.

Есть ли лучший способ сгладить эти кривые, что позволит равномерно распределить вершины, не слишком сильно влияя на область?

Источник

3 ответа

Решение

Вы можете взглянуть на литературу по "упрощению кривой", такую ​​как алгоритм Дугласа-Пекера или этот документ http://www.cs.ait.ac.th/~guha/papers/simpliPoly.pdf.

Это, вероятно, не будет работать хорошо, если вам нужны равномерно расположенные вершины, даже если определяемые ими смежные сегменты линии почти коллинеарны.

Источник

Я думаю, что вы ищете алгоритм Чайкина. Существует вариант этой идеи, который заставляет сглаженную кривую проходить непосредственно (а не "внутри") контрольных точек, но у меня сейчас проблемы с поиском в Google.

Источник

Вы также можете использовать сплайны для интерполяции - просто поиск в википедии

Источник

Кто-то перенес 2 алгоритма сглаживания на C# с лицензией CPOL (бесплатно), см. Здесь:

https://github.com/RobinCK/smooth-polyline

Источник
Другие вопросы по тегам