Curva Cuadrática de Bézier: Calcular Puntos

En caso de que alguien necesite la forma cúbica:

        //B(t) = (1-t)**3 p0 + 3(1 - t)**2 t P1 + 3(1-t)t**2 P2 + t**3 P3

        x = (1-t)*(1-t)*(1-t)*p0x + 3*(1-t)*(1-t)*t*p1x + 3*(1-t)*t*t*p2x + t*t*t*p3x;
        y = (1-t)*(1-t)*(1-t)*p0y + 3*(1-t)*(1-t)*t*p1y + 3*(1-t)*t*t*p2y + t*t*t*p3y;

En caso de que alguien necesite la enésima forma, aquí está el algoritmo. Lo alimentas N puntos y devolverá una matriz de N + (N-1) + (N-2) ... puntos, esto resuelve a (N * (N*1)) / 2. El último punto es la posición en la curva para el valor dado de T.

   9
  7 8
 4 5 6
0 1 2 3

Alimentaría el algoritmo 0 1 2 3 como puntos de control, y esas posiciones serían el resto de la matriz. El último punto (9) es el valor que desea.

Así es también como subdivide una curva de bézier, le da el valor de t que desea, luego declara la curva subdividida como los lados de la pirámide. Luego indexas los diversos puntos en el lado de la pirámide y el otro lado de la pirámide como construido desde la base. Así, por ejemplo, en quintic:

    E
   C D
  9 A B 
 5 6 7 8
0 1 2 3 4

(Perdón por el maleficio, lo quería bonito)

Usted indexaría las dos curvas perfectamente subdivididas en 0, 5, 9, C, E y E, D, B, 8, 4. Tome nota especial para ver que la primera curva comienza con un control punto (0) y termina en un punto en la curva (E) y la segunda curva comienza en la curva (E) y termina en el punto de control (4) Dado esto se puede subdividir perfectamente una curva de bézier, esto es lo que esperarías. El nuevo punto de control que une las dos curvas está en la curva.

/**
 * Performs deCasteljau's algorithm for a bezier curve defined by the given control points.
 *
 * A cubic for example requires four points. So it should get at least an array of 8 values
 *
 * @param controlpoints (x,y) coord list of the Bezier curve.
 * @param returnArray Array to store the solved points. (can be null)
 * @param t Amount through the curve we are looking at.
 * @return returnArray
 */
public static float[] deCasteljau(float[] controlpoints, float[] returnArray, float t) {
    int m = controlpoints.length;
    int sizeRequired = (m/2) * ((m/2) + 1);
    if (returnArray == null) returnArray = new float[sizeRequired];
    if (sizeRequired > returnArray.length) returnArray = Arrays.copyOf(controlpoints, sizeRequired); //insure capacity
    else System.arraycopy(controlpoints,0,returnArray,0,controlpoints.length);
    int index = m; //start after the control points.
    int skip = m-2; //skip if first compare is the last control point.
    for (int i = 0, s = returnArray.length - 2; i < s; i+=2) {
        if (i == skip) {
            m = m - 2;
            skip += m;
            continue;
        }
        returnArray[index++] = (t * (returnArray[i + 2] - returnArray[i])) + returnArray[i];
        returnArray[index++] = (t * (returnArray[i + 3] - returnArray[i + 1])) + returnArray[i + 1];
    }
    return returnArray;
}

Notarás que es solo la fórmula para la cantidad a través de cada conjunto de puntos. Para las soluciones de N usted consigue (N-1) puntos medios en valor (t) entonces de eso usted toma los puntos medios de ésos y consigue (N-2) puntos, entonces (N-3) puntos, etc. hasta que tenga solo un punto. Ese punto está en la curva. Así que resolver la cosa para valores entre 0, 1 para t, le dará toda la curva. Sabiendo esto, mi implementación allí solo propaga los valores hacia adelante en un array ahorrando recalculando cualquier cosa más de una vez. Lo he usado para 100s de puntos y todavía es muy rápido.

(en caso de que te preguntes, no, realmente no vale la pena. SVG tiene razón para detenerse en cubic).

He creado esta demo :

// x = a * (1-t)³ + b * 3 * (1-t)²t + c * 3 * (1-t)t² + d * t³
//------------------------------------------------------------
// x = a - 3at + 3at² - at³ 
//       + 3bt - 6bt² + 3bt³
//             + 3ct² - 3ct³
//                    + dt³
//--------------------------------
// x = - at³  + 3bt³ - 3ct³ + dt³
//     + 3at² - 6bt² + 3ct²
//     - 3at + 3bt
//     + a
//--------------------------------
// 0 = t³ (-a+3b-3c+d) +  => A
//     t² (3a-6b+3c)   +  => B
//     t  (-3a+3b)     +  => c
//     a - x              => D
//--------------------------------

var A = d - 3*c + 3*b - a,
    B = 3*c - 6*b + 3*a,
    C = 3*b - 3*a,
    D = a-x;

// So we need to solve At³ + Bt² + Ct + D = 0 

Ejemplo Completo aquí

Puede ayudar a alguien.

Solo una nota: Si está utilizando las fórmulas habituales presentadas aquí, no espere que t = 0.5 devuelva el punto a la mitad de la longitud de la curva.. En la mayoría de los casos no lo hará.

Más sobre esto aquí bajo "§23 - Trazando una curva a intervalos de distancia fija"y aquí.