¿El punto más cercano en una curva Bezier cúbica?

Dependiendo de sus tolerancias. Fuerza bruta y aceptación del error. Este algoritmo podría estar mal en algunos casos raros. Pero, en la mayoría de ellos encontrará un punto muy cercano a la respuesta correcta y los resultados mejorarán cuanto más alto establezcas las rebanadas. Solo intenta cada punto a lo largo de la curva a intervalos regulares y devuelve el mejor que encontró.

public double getClosestPointToCubicBezier(double fx, double fy, int slices, double x0, double y0, double x1, double y1, double x2, double y2, double x3, double y3)  {
    double tick = 1d / (double) slices;
    double x;
    double y;
    double t;
    double best = 0;
    double bestDistance = Double.POSITIVE_INFINITY;
    double currentDistance;
    for (int i = 0; i <= slices; i++) {
        t = i * tick;
        //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) * x0 + 3 * (1 - t) * (1 - t) * t * x1 + 3 * (1 - t) * t * t * x2 + t * t * t * x3;
        y = (1 - t) * (1 - t) * (1 - t) * y0 + 3 * (1 - t) * (1 - t) * t * y1 + 3 * (1 - t) * t * t * y2 + t * t * t * y3;

        currentDistance = Point.distanceSq(x,y,fx,fy);
        if (currentDistance < bestDistance) {
            bestDistance = currentDistance;
            best = t;
        }
    }
    return best;
}

Puede obtener mucho mejor y más rápido simplemente encontrando el punto más cercano y recursivamente alrededor de eso punto.

public double getClosestPointToCubicBezier(double fx, double fy, int slices, int iterations, double x0, double y0, double x1, double y1, double x2, double y2, double x3, double y3) {
    return getClosestPointToCubicBezier(iterations, fx, fy, 0, 1d, slices, x0, y0, x1, y1, x2, y2, x3, y3);
}

private double getClosestPointToCubicBezier(int iterations, double fx, double fy, double start, double end, int slices, double x0, double y0, double x1, double y1, double x2, double y2, double x3, double y3) {
    if (iterations <= 0) return (start + end) / 2;
    double tick = (end - start) / (double) slices;
    double x, y, dx, dy;
    double best = 0;
    double bestDistance = Double.POSITIVE_INFINITY;
    double currentDistance;
    double t = start;
    while (t <= end) {
        //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) * x0 + 3 * (1 - t) * (1 - t) * t * x1 + 3 * (1 - t) * t * t * x2 + t * t * t * x3;
        y = (1 - t) * (1 - t) * (1 - t) * y0 + 3 * (1 - t) * (1 - t) * t * y1 + 3 * (1 - t) * t * t * y2 + t * t * t * y3;


        dx = x - fx;
        dy = y - fy;
        dx *= dx;
        dy *= dy;
        currentDistance = dx + dy;
        if (currentDistance < bestDistance) {
            bestDistance = currentDistance;
            best = t;
        }
        t += tick;
    }
    return getClosestPointToCubicBezier(iterations - 1, fx, fy, Math.max(best - tick, 0d), Math.min(best + tick, 1d), slices, x0, y0, x1, y1, x2, y2, x3, y3);
}

En ambos casos se puede hacer el quad con la misma facilidad:

x = (1 - t) * (1 - t) * x0 + 2 * (1 - t) * t * x1 + t * t * x2; //quad.
y = (1 - t) * (1 - t) * y0 + 2 * (1 - t) * t * y1 + t * t * y2; //quad.

Cambiando la ecuación allí.

Mientras que la respuesta aceptada es correcta, y realmente se puede averiguar las raíces y comparar esas cosas. Si realmente solo necesitas encontrar el punto más cercano en la curva, esto lo hará.

Con respecto a Ben en los comentarios. No se puede acortar la fórmula en los muchos cientos de rango de puntos de control, como hice para formas cúbicas y cuádruples. Porque la cantidad demandada por cada nueva adición de una curva de Bézier significa que se construyen pirámides de Pitágoras para ellos, y básicamente estamos tratando con cadenas de números cada vez más masivas. Para quad vas 1, 2, 1, para cúbico vas 1, 3, 3, 1. Terminas construyendo pirámides cada vez más grandes, y terminas descomponiéndolas con el algoritmo de Casteljau, (escribí esto para solid speed):

/**
 * 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;
}

Básicamente necesita usar el algoritmo directamente, no solo para el cálculo de la x, y que se producen en la curva en sí, pero también lo necesita para realizar real y propio algoritmo de subdivisión Bezier (hay otros, pero eso es lo que recomendaría), para calcular no solo una aproximación como doy dividiendo en segmentos de línea, pero de las curvas reales. O más bien el casco del polígono que es seguro que contiene la curva.

Esto se hace usando el algoritmo anterior para subdividir las curvas en la t dada. Así que T = 0.5 para cortar las curvas por la mitad (nota 0.2 lo cortaría 20% 80% a través curva). 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 cúbico:

   9
  7 8
 4 5 6
0 1 2 3

Alimentaría el algoritmo 0 1 2 3 como puntos de control, luego indexaría las dos curvas perfectamente subdivididas en 0, 4, 7, 9 y 9, 8, 6, 3. Tome nota especial para ver que estas curvas comienzan y terminan en el mismo punto. y el índice final 9 que es el punto en la curva se utiliza como el otro nuevo punto de anclaje. Dado esto puedes subdividir perfectamente una curva de Bézier.

Luego, para encontrar el punto más cercano, querrá seguir subdividiendo la curva en diferentes partes, señalando que es el caso de que toda la curva de una curva de bézier esté contenida dentro del casco de los puntos de control. Es decir, si convertimos los puntos 0, 1, 2, 3 en un camino cerrado que conecta 0,3 esa curva debe caer completamente dentro del casco de ese polígono. Así que lo que hacemos es definir nuestro punto dado P, luego continuamos subdividiendo curvas hasta el momento en que sepamos que el punto más lejano de una curva está más cerca que el punto más cercano de otra curva. Simplemente comparamos este punto P con todos los puntos de control y anclaje de las curvas. Y descartar cualquier curva de nuestra lista activa cuyo punto más cercano (ya sea ancla o control) está más lejos que el punto más lejano de otra curva. Luego subdividimos todas las curvas activas y hacemos esto de nuevo. Eventualmente tendremos curvas muy subdivididas descartando aproximadamente la mitad de cada paso (lo que significa debe ser O (n log n)) hasta que nuestro error es básicamente insignificante. En este punto, llamamos a nuestras curvas activas el punto más cercano a ese punto (podría haber más de uno), y notamos que el error en ese bit altamente subdividido de curva es básicamente igual a un punto. O simplemente decidir el problema diciendo que cualquiera de los dos puntos de anclaje es más cercano es el punto más cercano a nuestro punto P. Y conocemos el error en un grado muy específico.

Esto, sin embargo, requiere que realmente tengamos un robusto solución y hacer un algoritmo ciertamente correcto y encontrar correctamente la pequeña fracción de la curva que sin duda será el punto más cercano a nuestro punto. Y debería ser relativamente rápido todavía.

He escrito un código rápido y sucio que estima esto para curvas de Bézier de cualquier grado. (Nota: esto es pseudo-fuerza bruta, no una solución de forma cerrada.)

Demo: http://phrogz.net/svg/closest-point-on-bezier.html

/** Find the ~closest point on a Bézier curve to a point you supply.
 * out    : A vector to modify to be the point on the curve
 * curve  : Array of vectors representing control points for a Bézier curve
 * pt     : The point (vector) you want to find out to be near
 * tmps   : Array of temporary vectors (reduces memory allocations)
 * returns: The parameter t representing the location of `out`
 */
function closestPoint(out, curve, pt, tmps) {
    let mindex, scans=25; // More scans -> better chance of being correct
    const vec=vmath['w' in curve[0]?'vec4':'z' in curve[0]?'vec3':'vec2'];
    for (let min=Infinity, i=scans+1;i--;) {
        let d2 = vec.squaredDistance(pt, bézierPoint(out, curve, i/scans, tmps));
        if (d2<min) { min=d2; mindex=i }
    }
    let t0 = Math.max((mindex-1)/scans,0);
    let t1 = Math.min((mindex+1)/scans,1);
    let d2ForT = t => vec.squaredDistance(pt, bézierPoint(out,curve,t,tmps));
    return localMinimum(t0, t1, d2ForT, 1e-4);
}

/** Find a minimum point for a bounded function. May be a local minimum.
 * minX   : the smallest input value
 * maxX   : the largest input value
 * ƒ      : a function that returns a value `y` given an `x`
 * ε      : how close in `x` the bounds must be before returning
 * returns: the `x` value that produces the smallest `y`
 */
function localMinimum(minX, maxX, ƒ, ε) {
    if (ε===undefined) ε=1e-10;
    let m=minX, n=maxX, k;
    while ((n-m)>ε) {
        k = (n+m)/2;
        if (ƒ(k-ε)<ƒ(k+ε)) n=k;
        else               m=k;
    }
    return k;
}

/** Calculate a point along a Bézier segment for a given parameter.
 * out    : A vector to modify to be the point on the curve
 * curve  : Array of vectors representing control points for a Bézier curve
 * t      : Parameter [0,1] for how far along the curve the point should be
 * tmps   : Array of temporary vectors (reduces memory allocations)
 * returns: out (the vector that was modified)
 */
function bézierPoint(out, curve, t, tmps) {
    if (curve.length<2) console.error('At least 2 control points are required');
    const vec=vmath['w' in curve[0]?'vec4':'z' in curve[0]?'vec3':'vec2'];
    if (!tmps) tmps = curve.map( pt=>vec.clone(pt) );
    else tmps.forEach( (pt,i)=>{ vec.copy(pt,curve[i]) } );
    for (var degree=curve.length-1;degree--;) {
        for (var i=0;i<=degree;++i) vec.lerp(tmps[i],tmps[i],tmps[i+1],t);
    }
    return vec.copy(out,tmps[0]);
}

El código anterior utiliza la biblioteca vmath para lerp de manera eficiente entre vectores (en 2D, 3D o 4D), pero sería trivial reemplazar la llamada lerp() en bézierPoint() con su propio código.

Tuning the Algoritmo

La función closestPoint() funciona en dos fases:

• Primero, calcular puntos a lo largo de la curva (valores uniformemente espaciados del parámetro t). Registre qué valor de t tiene la distancia más pequeña al punto.
• Luego, use la función localMinimum() para buscar la región alrededor de la distancia más pequeña, usando una búsqueda binaria para encontrar el t y el punto que produce la verdadera distancia más pequeña.

El valor de scans en closestPoint() determina cuántas muestras usar en la primera pasada. Menos escaneos es más rápido, pero aumenta las posibilidades de perder el verdadero punto mínimo.

El límite ε pasado a la función localMinimum() controla cuánto tiempo continúa buscando el mejor valor. Un valor de 1e-2 cuantifica la curva en ~100 puntos, y así puede ver los puntos devueltos desde closestPoint() apareciendo a lo largo de la línea. Cada punto decimal adicional de precisión-1e-3, 1e-4, ...-cuesta alrededor de 6-8 llamadas adicionales a bézierPoint().