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

Учитывая 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 точек:

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

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

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

Ответ 1

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

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

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

Ответ 2

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

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

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

Ответ 3

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

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

Ответ 4

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

Ответ 5

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