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

Question

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

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

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 градуса.

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

Answer 1

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

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

Answer 2

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

Answer 3

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

Answer 4

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

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