Bezier curva longitud del arco

Ver también: misma pregunta en Math.SE

¿Cómo puedo encontrar la longitud de arco de una curva de Bezier? Por ejemplo, una curva lineal de Bezier tiene la longitud:

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

Pero, ¿qué pasa con las curvas Bezier cuadráticas, cúbicas o de n grados?

(Mi objetivo era estimar de antemano una resolución de muestreo, por lo que no tengo que perder el tiempo comprobando si el siguiente punto toca el punto anterior).

Una manera simple para los Béziers cúbicos es dividir la curva en N segmentos y sumar las longitudes de los segmentos.

Sin embargo, tan pronto como necesite la longitud de solo una parte de la curva (por ejemplo, hasta un punto del 30% de la longitud), entrará en juego la parametrización de la longitud del arco . Publiqué una respuesta bastante larga en una de mis propias preguntas sobre Béziers, con un código de muestra simple.

Si bien estoy de acuerdo con las respuestas que ya obtuvo, quiero agregar un mecanismo de aproximación simple pero poderoso que puede usar para cualquier grado de curvas Bézier: subdivide continuamente la curva usando la subdivisión de Casteljau hasta la distancia máxima de los puntos de control de una subcurva a la línea base de la subcurva está debajo de un épsilon constante . En ese caso, la subcurva puede aproximarse por su línea de base.

De hecho, creo que este es el enfoque que generalmente se toma cuando un subsistema de gráficos tiene que dibujar una curva Bézier. Pero no me cite sobre esto, no tengo referencias disponibles en este momento.

En la práctica se verá así: (excepto que el idioma es irrelevante)

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]);
}

Las longitudes de arco para las curvas de Bezier son solo de forma cerrada para las lineales y cuadráticas. Para los cúbicos, no se garantiza tener una solución cerrada. La razón es que la longitud del arco está definida por una integral radical, para la cual tiene un polinomio cerrado de solo 2º grado.

Solo como referencia: la longitud de un Bezier cuadrático para los puntos (a, p) (b, q) y (c, r) es

(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)

Donde LN es el logaritmo natural, y ^ denota potencia y √ la raíz cuadrada.

Por lo tanto, debería ser más fácil y económico aproximar el arco mediante alguna otra regla, como un polígono o un esquema de integración como la regla de Simpson, porque las raíces cuadradas del LN son operaciones costosas.

Trabajé la expresión cerrada de longitud para un Bezier de 3 puntos (abajo). No he intentado elaborar un formulario cerrado para más de 4 puntos. Es muy probable que esto sea difícil o complicado de representar y manejar. Sin embargo, una técnica de aproximación numérica como un algoritmo de integración Runge-Kutta funcionaría bastante bien al integrarse utilizando la fórmula de longitud de arco . Mis preguntas y respuestas sobre RK45 en MSE pueden ayudar con la implementación de RK45.

Aquí hay un código Java para la longitud de arco de 3 puntos de Bezier, con puntos a, by 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)));