Блог

Учитывая n точек:

p0, p1, p2, …, pn;

Как я могу получить точку c1, c2, чтобы кубическая кривая Безье, определенная

p0, c1, c2, pn

ближайшую к заданным точкам?

Я попробовал метод наименьших квадратов. Я написал это после того, как прочитал PDF-документ в http://www.mathworks.com/matlabcentral/fileexchange/15542-cubic-bezier-least-square-fitting . Но я не могу найти хорошую функцию t (i).

 using System;
using System.Collections.Generic;
using System.Linq;
using System.Windows;

namespace BezierFitting
{
    class CubicBezierFittingCalculator
    {
        private List<Point> data;

        public CubicBezierFittingCalculator(List<Point> data)
        {
            this.data = data;
        }

        private double t(int i)
        {
            return (double)(i - 1) / (data.Count - 1);
            // double s = 0.0, d = 0.0;
            // 
            // for (int j = 1; j < data.Count; j  )
            // {
            //     if (j < i)
            //     {
            //         s  = (data[j] - data[j - 1]).Length;
            //     }
            //     d  = (data[j] - data[j - 1]).Length;
            // }
            // return s / d;
        }

        public void Calc(ref Point p1, ref Point p2)
        {
            double n = data.Count;
            Vector p0 = (Vector)data.First();
            Vector p3 = (Vector)data.Last();

            double a1 = 0.0, a2 = 0.0, a12 = 0.0;
            Vector c1 = new Vector(0.0, 0.0), c2 = new Vector(0.0, 0.0);
            for (int i = 1; i <= n; i  )
            {
                double ti = t(i), qi = 1 - ti;
                double ti2 = ti * ti, qi2 = qi * qi;
                double ti3 = ti * ti2, qi3 = qi * qi2;
                double ti4 = ti * ti3, qi4 = qi * qi3;
                a1  = ti2 * qi4;
                a2  = ti4 * qi2;
                a12  = ti3 * qi3;

                Vector pi = (Vector)data[i - 1];
                Vector m = pi - qi3 * p0 - ti3 * p3;
                c1  = ti * qi2 * m;
                c2  = ti2 * qi * m;
            }
            a1 *= 9.0;
            a2 *= 9.0;
            a12 *= 9.0;
            c1 *= 3.0;
            c2 *= 3.0;

            double d = a1 * a2 - a12 * a12;
            p1 = (Point)((a2 * c1 - a12 * c2) / d);
            p2 = (Point)((a1 * c2 - a12 * c1) / d);
        }
    }
}
  

Каков наилучший способ получить кубическую кривую Безье, ближайшую к заданным точкам?

Например, вот 30 точек:

 22, 245
26, 240
39, 242
51, 231
127, 189
136, 185
140, 174
147, 171
163, 162
169, 155
179, 107
181, 147
189, 168
193, 187
196, 75
199, 76
200, 185
201, 68
204, 73
205, 68
208, 123
213, 118
216, 210
216, 211
218, 68
226, 65
227, 110
228, 102
229, 87
252, 247
  

Эти точки распределены вокруг кубической кривой Безье, управляемой четырьмя точками:

P0 (0, 256), P1 (512, 0), P2 (0, 0), P3 (256, 256).

Предположим, что кривая находится от (0, 256) до (256, 256), как получить остальные две контрольные точки, близкие к исходным точкам?

Возможно, вы захотите взглянуть на эту страницу

Это очень хорошая реализация, хотя, как пишет автор: «Этот метод является чисто эвристическим и эмпирическим. Вероятно, это дает неверный результат с точки зрения строгого математического моделирования. Но на практике результат достаточно хорош и требует абсолютного минимума вычислений. «

Это на C , но действительно легко переносимо на любой язык… Передайте каждое из ваших «ребер» через функцию вычисления контрольных точек, затем через функцию вычисления Безье, и она у вас есть. Чтобы выполнить сглаживание Безье на многоугольнике, передайте последнее ребро с вашей последней и первой точкой.

(Кубическая) кривая Безье — это способ определения кубического параметрического сплайна общего вида P = A * t ^ 3 B * t ^ 2 C * t D, где P, A, B, C и D являются (двумерными, т. Е. Векторными) весами. Используя полиномы Бернштейна, вы можете вычислить веса A, B, C и D, учитывая четыре контрольные точки P0, P1, P2 и P3, известные практически из всех программ векторного рисования.

Поскольку у вас есть только четыре контрольные точки, но вы хотите разместить произвольное количество произвольных точек, я подозреваю, что уникального решения нет. Например, заданные входные данные (0,0),(1,0),(1,1) и (0,1), для каждого «оптимального» решения (каким бы оно ни было), вы могли бы построить эквивалентное решение, отразив сплайн вдоль главной диагонали.

Существует общий подход к такого рода задачам, который заключается в построении уравнения для суммы квадратов расстояний для всех точек до общей кривой Безье (т. Е. Кривой, определяемой переменными A, B, C и D), вычислении первого отклонения и установке его равным нулю и решении уравнениярезультирующая система для A, B, C и D. Обычно это приводит к линейной системе уравнений (извините, мне потребовалось бы некоторое время, чтобы сделать математику, и прошло много времени с тех пор, как я это делал …). Но, как я уже сказал, я думаю, что для вашей проблемыэто не приведет к уникальному решению.

Если вы определяете порядок входных точек, т. Е. Вы хотите подогнать линию полигона, используя одну кривую Безье, я думаю, что для уникального решения слишком много степеней свободы (но, опять же, у меня нет времени или, возможно, навыков, чтобы доказать это …)

Ваша проблема очень сложна, если вы хотите создавать кривые с остриями. Я могу придумать эвристику для создания начального набора контрольных точек. Для первой контрольной точки попробуйте взять первую 1/3 доступных вам точек, отсортированных по расстоянию до первой опорной точки. Сортировка необходима, иначе вы можете перепрыгнуть через все. Возьмите эту 1/3 ваших точек и выполните линейную подгонку по методу наименьших квадратов, которая имеет линейную временную сложность. Это дает вам направление, в котором ваша кривая должна взлететь. Проделайте то же самое с последней 1/3, и у вас будет направление «посадки».

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

Вот несколько других идей (я могу опубликовать только две ссылки!): physics forum question
тезис о подгонке кривой Безье

Судя по вашему вопросу, я предполагаю, что вы просто хотите оптимизировать подгонку кривой по 2 «внутренним» контрольным точкам кубического Безье. Это непростая задача, поскольку кривая Безье описывается параметрически. Наиболее очевидным решением было бы использовать регрессию ортогонального расстояния методом наименьших квадратов, но это сложно, так как вам нужно будет сгенерировать параметры опорных точек на кривой Безье для каждой точки, которую вы хотите разместить. Если эта проблема требует конкретного аналитического решения и у вас есть некоторое математическое образование, я бы рекомендовал прочитать «Книгу NURBS» Пейгла и Тиллера и ознакомиться с теорией аппроксимации и методами оптимизации. Если нет, я бы выбрал более эвристический подход, поскольку проблема такого типа вряд ли будет решена простым ответом здесь.

Функция Хана использует две версии t[i], где t [i] представляет предположение о ближайшей точке на кривой приближения к входной точке p [i]. Первый просто использует равномерное t[i] = i / (N-1), второй использует длину хорды. Хотя я не смог найти функцию Хана, я думаю, что это просто вычисляет линейное расстояние от p [i] до p [i 1], устанавливает t [0] в 0, t [1] на расстояние от p [0] до p [1], t[2] до t[1] расстояние от p [1] до p [2] и так далее. Деление на последнее значение, чтобы поместить все в диапазон 0-1.