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

Question

Дано 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), какполучить остальные две контрольные точки близко к исходным точкам?

Answer 1

Возможно, вы захотите взглянуть на эту страницу: http://www.antigrain.com/research/bezier_interpolation/index.html

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

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

Answer 2

Кривая Безье (кубическая) - это способ определения кубического параметрического сплайна общего вида 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. Обычно это приводит к линейной системе уравнений (извините, у меня заняло бы некоторое время, чтобы сделать математику, и прошло много времени с тех пор, как я это сделал ...).Но, как я уже сказал, я думаю, что для вашей проблемы это не приведет к уникальному решению.

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

Answer 3

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

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

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

Answer 4

Функция Хана использует две версии 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.

Answer 5

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