Кривая Безье длина дуги

23

Смотрите также: тот же вопрос на Math.SE

Как я могу найти длину дуги кривой Безье? Например, линейная кривая Безье имеет длину:

length = sqrt(pow(x[1] - x[0], 2) + pow(y[1] - y[0], 2));

Но как насчет квадратичных, кубических или n-градусных кривых Безье?

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

Матин Улхак
источник
1
Вы должны перефразировать вопрос, чтобы обозначить длину кривой, это гораздо более простой (и доступный для поиска) термин.
Спарр
я предлагаю опубликовать это по математике, я уверен, что какое-нибудь умное лицо там даст вам ответ в одном из них - «Умные веб-шрифты»: p
Tor Valamo
2
@ Я так и сделал (вчера), но мне сказали, что это очень сложно и, следовательно, непрактично. [ math.stackexchange.com/q/12186/2736 ]
Матин Улхак
Предположительно, клотоидные кривые / сплайны являются альтернативой Безье и имеют замкнутые выражения длины волны, но я пока не знаю об этом много. (Попытка создать точки равного расстояния вдоль кривой.) У цепей также есть выражения длины дуги замкнутой формы?
эндолит

Ответы:

9

Простой способ для кубических Безье состоит в том, чтобы разбить кривую на N сегментов и суммировать длины сегментов.

Однако, как только вам понадобится длина только части кривой (например, до 30% длины), будет введена параметризация длины дуги . Я написал довольно длинный ответ на один из моих собственных вопросов о Безье с простым примером кода.

Иво Ветцель
источник
Я делаю это для LEGO Mindstorms NXT, у которого действительно слабый процессор (48 МГц), поэтому мне нужна как можно большая скорость. Я возьму разделительный подход, чтобы сохранить некоторую скорость и получить ее достаточно точно (для рендеринга «не в реальном времени»). У меня также есть опция, в которой вы можете установить значение 1.0/t( resolutionnamed), так что это для «реального времени» (которое в лучшем случае составляет 10 кадров в секунду на медленном NXT). Каждая итерация, t += resolutionи новая точка / линия рисуется. В любом случае, спасибо за идею.
Матин Улхак
4

Хотя я согласен с ответами, которые вы уже получили, я хочу добавить простой, но мощный механизм аппроксимации, который вы можете использовать для любых кривых Безье степени: вы непрерывно делите кривую, используя подразделение де Кастельжау, до максимального расстояния от контрольных точек подкривого к базовой линии подкривого ниже некоторой постоянной эпсилона . В этом случае подкривая может быть аппроксимирована своей базовой линией.

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

На практике это будет выглядеть так: (за исключением того, что язык не имеет значения)

public static Line[] toLineStrip(BezierCurve bezierCurve, double epsilon) {
    ArrayList<Line> lines = new ArrayList<Line>();

    Stack<BezierCurve> parts = new Stack<BezierCurve>();
    parts.push(bezierCurve);

    while (!parts.isEmpty()) {
        BezierCurve curve = parts.pop();
        if (distanceToBaseline(curve) < epsilon) {
            lines.add(new Line(curve.get(0), curve.get(1)));
        } else {
            parts.addAll(curve.split(0.5));
        }
    }

    return lines.toArray(new Line[0]);
}
Матиас
источник
Хотя это хороший подход, я слышал о численной нестабильности на кривых Безье высокого порядка, которая требует другой идеи: разбивать кривые высшего порядка на кубические кривые меньшего размера.
Матин Улхак
Кроме того, если конечной целью является точная оценка, возможно, было бы неплохо приблизиться с помощью квадратиков вместо линий, чтобы убедиться, что мы не занижаем нашу оценку в местах с высокой кривизной.
Матин Улхак
2

Дуги для кривых Безье имеют только замкнутую форму для линейных и квадратичных. Для кубиков не гарантируется, что решение будет закрытым. Причина в том, что длина дуги определяется радикальным интегралом, для которого есть замкнутый только для многочленов 2-й степени.

Для справки: длина квадратичного Безье для точек (a, p) (b, q) и (c, r) равна

(a ^ 2 · (q ^ 2 - 2 · q · r + r ^ 2) + 2 · a · (r - q) · (b · (p - r) + c · (q - p)) + ( b · (p - r) + c · (q - p)) ^ 2) · LN ((√ (a ^ 2 - 2 · a · b + b ^ 2 + p ^ 2 - 2 · p · q + q ^ 2) · √ (a ^ 2 + 2 · a · (c - 2 · b) + 4 · b ^ 2 - 4 · b · c + c ^ 2 + (p - 2 · q + r) ^ 2) + a ^ 2 + a · (c - 3 · b) + 2 · b ^ 2 - b · c + (p - q) · (p - 2 · q + r)) / (√ (a ^ 2 + 2 · A · (c - 2 · b) + 4 · b ^ 2 - 4 · b · c + c ^ 2 + (p - 2 · q + r) ^ 2) · √ (b ^ 2 - 2 · b · c + c ^ 2 + q ^ 2 - 2 · q · r + r ^ 2) + a · (b - c) - 2 · b ^ 2 + 3 · b · c - c ^ 2 + (p - 2 · q + r) · (q - r))) / (a ​​^ 2 + 2 · a · (c - 2 · b) + 4 · b ^ 2 - 4 · b · c + c ^ 2 + (p - 2 · Q + r) ^ 2) ^ (3/2) + (√ (a ^ 2 - 2 · a · b + b ^ 2 + p ^ 2 - 2 · p · q + q ^ 2) · (a ^ 2 + a · (c - 3 · b) + 2 · b ^ 2 - b · c + (p - q) · (p - 2 · q + r)) - √ (b ^ 2 - 2 · b · c + c ^ 2 + q ^ 2 - 2 · q · r + r ^ 2) · (a · (b - c) - 2 · b ^ 2 + 3 · b · c - c ^ 2 + (p - 2 · q + r) · (q - r))) / (a ​​^ 2 + 2 · a · (c - 2 · b) + 4 · b ^ 2 - 4 · b · c + c ^ 2 + (p - 2 · Q + r) ^ 2)

Где LN - натуральный логарифм, а ^ обозначает степень и √ квадратный корень.

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

Роберт
источник
2

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

Вот некоторые Java - код для длины дуги 3 точки Безье а, с точками 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)));
пиксель
источник