Дешевый способ расчета кубической длины безье

Ответ 1

Другой вариант - оценить длину дуги как среднее между хордой и сетью управления. На практике:

Bezier bezier = Bezier (p0, p1, p2, p3);

chord = (p3-p0).Length;
cont_net = (p0 - p1).Length + (p2 - p1).Length + (p3 - p2).Length;

app_arc_length = (cont_net + chord) / 2;

Затем вы можете рекурсивно разделить сегмент сплайна на два сегмента и рассчитать длину дуги до конвергенции. Я тестировал себя, и он на самом деле сходится довольно быстро. Я получил идею от этого .

Ответ 2

Самый простой алгоритм: сгладить кривую и эллиптическое расстояние. До тех пор, пока вы хотите приблизительную длину дуги, это решение является быстрым и дешевым. Учитывая вашу координату кривой LUT - вы говорите о скорости, поэтому я предполагаю, что вы ее используете, и не постоянно перекомпонуйте координаты - это простой для цикла с подсчетом. В общем коде с функцией dist, которая вычисляет эвклидовое расстояние между двумя точками:

var arclength = 0,
    last=LUT.length-1,
    i;
for (i=0; i<last; i++) {
  arclength += dist(LUT[i], LUT[i+1]);
}

Готово. arclength - это теперь приблизительная длина дуги, основанная на максимальном числе сегментов, которые вы можете сформировать в кривой на основе вашего LUT. Нужны вещи быстрее с большей потенциальной ошибкой? Контролируйте количество сегментов.

var arclength = 0,
    segCount = ...,
    last=LUT.length-2,
    step = last/segCount,
    s, i;
for (s=0; s<=segCount; s++) {
  i = (s*step/last)|0;
  arclength += dist(LUT[i], LUT[i+1]);
}

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

Если вы хотите знать, почему, нажмите раздел длины дуги "A Primer на кривых Безье".

Ответ 3

Я разработал выражение длины в закрытой форме для 3-точечного Безье (ниже). Я не пытался разработать закрытую форму для очков 4+. Скорее всего, это будет трудно или сложно представить и обработать. Тем не менее, метод числового приближения, такой как алгоритм интегрирования Рунге-Кутты (подробности см. В разделе "Вопросы и ответы", здесь), работал бы достаточно хорошо, интегрируя с использованием формулы длины дуги.

Вот некоторый Java-код для длины дуги трехточечного Безье с точками a, b и c.

    v.x = 2*(b.x - a.x);
    v.y = 2*(b.y - a.y);
    w.x = c.x - 2*b.x + a.x;
    w.y = c.y - 2*b.y + a.y;

    uu = 4*(w.x*w.x + w.y*w.y);

    if(uu < 0.00001)
    {
        return (float) Math.sqrt((c.x - a.x)*(c.x - a.x) + (c.y - a.y)*(c.y - a.y));
    }

    vv = 4*(v.x*w.x + v.y*w.y);
    ww = v.x*v.x + v.y*v.y;

    t1 = (float) (2*Math.sqrt(uu*(uu + vv + ww)));
    t2 = 2*uu+vv;
    t3 = vv*vv - 4*uu*ww;
    t4 = (float) (2*Math.sqrt(uu*ww));

    return (float) ((t1*t2 - t3*Math.log(t2+t1) -(vv*t4 - t3*Math.log(vv+t4))) / (8*Math.pow(uu, 1.5)));

Ответ 4

public float FastArcLength()
{
    float arcLength = 0.0f;
    ArcLengthUtil(cp0.position, cp1.position, cp2.position, cp3.position, 5, ref arcLength);
    return arcLength;
}

private void ArcLengthUtil(Vector3 A, Vector3 B, Vector3 C, Vector3 D, uint subdiv, ref float L)
{
    if (subdiv > 0)
    {
        Vector3 a = A + (B - A) * 0.5f;
        Vector3 b = B + (C - B) * 0.5f;
        Vector3 c = C + (D - C) * 0.5f;
        Vector3 d = a + (b - a) * 0.5f;
        Vector3 e = b + (c - b) * 0.5f;
        Vector3 f = d + (e - d) * 0.5f;

        // left branch
        ArcLengthUtil(A, a, d, f, subdiv - 1, ref L);
        // right branch
        ArcLengthUtil(f, e, c, D, subdiv - 1, ref L);
    }
    else
    {
        float controlNetLength = (B-A).magnitude + (C - B).magnitude + (D - C).magnitude;
        float chordLength = (D - A).magnitude;
        L += (chordLength + controlNetLength) / 2.0f;
    }
}

Ответ 5

в моем случае это быстрый и правильный подход. (Переписано в С# для Unity3d)

public static float BezierSingleLength(Vector3[] points){
    var p0 = points[0] - points[1];
    var p1 = points[2] - points[1];
    var p2 = new Vector3();
    var p3 = points[3]-points[2];

    var l0 = p0.magnitude;
    var l1 = p1.magnitude;
    var l3 = p3.magnitude;
    if(l0 > 0) p0 /= l0;
    if(l1 > 0) p1 /= l1;
    if(l3 > 0) p3 /= l3;

    p2 = -p1;
    var a = Mathf.Abs(Vector3.Dot(p0,p1)) + Mathf.Abs(Vector3.Dot(p2,p3));
    if(a > 1.98f || l0 + l1 + l3 < (4 - a)*8) return l0+l1+l3;

    var bl = new Vector3[4];
    var br = new Vector3[4];

    bl[0] = points[0];
    bl[1] = (points[0]+points[1]) * 0.5f;

    var mid = (points[1]+points[2]) * 0.5f;

    bl[2] = (bl[1]+mid) * 0.5f;
    br[3] = points[3];
    br[2] = (points[2]+points[3]) * 0.5f;
    br[1] = (br[2]+mid) * 0.5f;
    br[0] = (br[1]+bl[2]) * 0.5f;
    bl[3] = br[0];

    return BezierSingleLength(bl) + BezierSingleLength(br);
}

Ответ 6

сначала вы должны понять, как использовать алгоритм в Безье, Когда я кодировал программу с помощью С#, в которой было полно графического материала, я использовал безьеров и много раз мне приходилось находить точку в форме безье, которая кажется на первый взгляд неудобной. так что я делаю это, чтобы написать Cubic bezier function в моем классе математики, который был в моем проекте. поэтому я сначала поделюсь с вами кодом.

    //--------------- My Costum Power Method ------------------\\

public static float FloatPowerX(float number, int power)
        {
            float temp = number;
            for (int i = 0; i < power - 1; i++)
            {
                temp *= number;
            }
            return temp;
        }

    //--------------- Bezier Drawer Code Bellow ------------------\\

public static void CubicBezierDrawer(Graphics graphics, Pen pen, float[] startPointPixel, float[] firstControlPointPixel
                , float[] secondControlPointPixel, float[] endPointPixel)
        {
            float[] px = new float[1111], py = new float[1111];
            float[] x = new float[4] { startPointPixel[0], firstControlPointPixel[0], secondControlPointPixel[0], endPointPixel[0] };
            float[] y = new float[4] { startPointPixel[1], firstControlPointPixel[1], secondControlPointPixel[1], endPointPixel[1] };
        int i = 0;

        for (float t = 0; t <= 1F; t += 0.001F)
        {
            px[i] = FloatPowerX((1F - t), 3) * x[0] + 3 * t * FloatPowerX((1F - t), 2) * x[1] + 3 * FloatPowerX(t, 2) * (1F - t) * x[2] + FloatPowerX(t, 3) * x[3];
            py[i] = FloatPowerX((1F - t), 3) * y[0] + 3 * t * FloatPowerX((1F - t), 2) * y[1] + 3 * FloatPowerX(t, 2) * (1F - t) * y[2] + FloatPowerX(t, 3) * y[3];
            graphics.DrawLine(pen, px[i - 1], py[i - 1], px[i], py[i]);
            i++;
        }
    }

как вы видите выше, так работает функция Безье, и она рисует тот же Bezier, что и функция Microsoft Bezier (я ее тестировал). вы можете сделать его еще более точным, увеличив размер массива и размер счетчика или нарисуйте elipse вместо line &.... Все они зависят от необходимости и уровня точности, который вам нужен, и....

Возвращаясь к главной цели, вопрос заключается в том, как вычислить длину

Хорошо Ответ: у нас есть тонны точек, и у каждого из них есть координаты x coorinat и y, которые помнят нас о форме треугольника и особенно в форме RightTriabgle Shape. поэтому, если у нас есть точки p1 и p2, мы можем рассчитать их расстояние как правого треугольника. как мы помним из нашего математического класса в школе, в ABC Треугольник типа RightTriangle, аккорд Длина → Sqrt (Angle FrontCostalLenght ^ 2 + Angle SideCostalLeghth ^ 2);

и есть это отношение между всеми точками, мы вычисляем длину между текущей точкой и последней точкой перед текущей точкой (exmp p [i-1] и p [i]) и сохраняем их сумму в переменной. давайте покажем его ниже.

//--------------- My Costum Power Method ------------------\\

public static float FloatPower2(float number)
        {
            return number * number;
        }

//--------------- My Bezier Lenght Calculator Method ------------------\\

public static float CubicBezierLenghtCalculator(float[] startPointPixel
            , float[] firstControlPointPixel, float[] secondControlPointPixel, float[] endPointPixel)
        {
            float[] tmp = new float[2];
            float lenght = 0;
            float[] px = new float[1111], py = new float[1111];

            float[] x = new float[4] { startPointPixel[0], firstControlPointPixel[0]
                , secondControlPointPixel[0], endPointPixel[0] };

            float[] y = new float[4] { startPointPixel[1], firstControlPointPixel[1]
                , secondControlPointPixel[1], endPointPixel[1] };

            int i = 0;

            for (float t = 0; t <= 1.0; t += 0.001F)
            {
                px[i] = FloatPowerX((1.0F - t), 3) * x[0] + 3 * t * FloatPowerX((1.0F - t), 2) * x[1] + 3F * FloatPowerX(t, 2) * (1.0F - t) * x[2] + FloatPowerX(t, 3) * x[3];
                py[i] = FloatPowerX((1.0F - t), 3) * y[0] + 3 * t * FloatPowerX((1.0F - t), 2) * y[1] + 3F * FloatPowerX(t, 2) * (1.0F - t) * y[2] + FloatPowerX(t, 3) * y[3];
                if (i > 0)
                {
                    tmp[0] = Math.Abs(px[i - 1] - px[i]);// calculating costal lenght
                    tmp[1] = Math.Abs(py[i - 1] - py[i]);// calculating costal lenght
                    lenght += (float)Math.Sqrt(FloatPower2(tmp[0]) + FloatPower2(tmp[1]));// calculating the lenght of current RightTriangle Chord  & add it each time to variable
                }
                i++;
            }
            return lenght;
        }

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

Мы также можем уменьшить потребность в памяти, уменьшив px и py до длины массива до 1 или сделав простую двойную переменную, но из-за условной ситуации. Happend, которая увеличивает наш большой O, я этого не делал.

Надеюсь, вам это очень помогло. если есть другой вопрос, просто спросите. С наилучшими пожеланиями, Гейдар - Исламская Республика Иран.