graphics - online - lineas curvas de bezier

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

Question

¿Cómo puedo encontrar el punto B (t) a lo largo de una curva Bezier cúbica que está más cerca de un punto arbitrario P en el plano?

Answer 1

Dependiendo de sus tolerancias. Fuerza bruta y aceptación de error. Este algoritmo podría estar equivocado 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 coloque los cortes. Simplemente 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 recurriendo alrededor de ese 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 puedes 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í.

Si bien la respuesta aceptada es correcta, realmente puedes descubrir las raíces y comparar esas cosas. Si realmente solo necesitas encontrar el punto más cercano en la curva, esto lo hará.

Respecto a Ben en los comentarios. No puede abreviar la fórmula en los muchos cientos de puntos de control, como hice para las formas cúbica y cuádruple. Debido a que la cantidad demandada por cada nueva adición de una curva de Bézier significa que usted construye 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 cubic vas 1, 3, 3, 1. Terminas construyendo pirámides cada vez más grandes y terminas desglosándolas con el algoritmo de Casteljau (escribí esto para velocidad sólida):

/**
 * 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 x, y que ocurren en la curva en sí, sino que también lo necesita para realizar el algoritmo de subdivisión Bezier real y adecuado (hay otros, pero eso es lo que yo recomendar), para calcular no solo una aproximación como la que doy al dividirla en segmentos de línea, sino también de las curvas reales. O mejor dicho, el casco poligonal que seguramente contiene la curva.

Para ello, utilice el algoritmo anterior para subdividir las curvas en la t dada. Entonces T = 0.5 para cortar las curvas a la mitad (nota 0.2 lo cortaría 20% 80% a través de la curva). Luego, indexa los diversos puntos en el lado de la pirámide y el otro lado de la pirámide como se construye desde la base. Así por ejemplo en cubic:

   9
  7 8
 4 5 6
0 1 2 3

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

Luego, para encontrar el punto más cercano, querría seguir subdividiendo la curva en diferentes partes, teniendo en cuenta que la curva completa de una curva de bezier 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 estar completamente dentro de ese casco poligonal. Entonces, lo que hacemos es definir nuestro punto P dado, luego continuamos subdividiendo las curvas hasta 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 descarte 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 lo hacemos de nuevo. Eventualmente tendremos curvas muy subdivididas que descartarán aproximadamente la mitad de cada paso (lo que significa que debería ser O (n log n)) hasta que nuestro error sea 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 una) y notamos que el error en ese bit de curva altamente subdividido es básicamente igual a un punto. O simplemente decida el problema diciendo cuál de los dos puntos de anclaje más cercano es el más cercano a nuestro punto P. Y conocemos el error en un grado muy específico.

Sin embargo, esto requiere que realmente tengamos una solución robusta y hagamos un algoritmo ciertamente correcto y encontremos correctamente la pequeña fracción de curva que será el punto más cercano a nuestro punto. Y debería ser relativamente rápido todavía.

Answer 2

Después de mucha búsqueda, encontré un artículo que analiza un método para encontrar el punto más cercano en una curva Bezier a un punto dado:

Algoritmo algebraico mejorado en proyección puntual para curvas Bezier , por Xiao-Diao Chen, Yin Zhou, Zhenyu Shu, Hua Su y Jean-Claude Paul.

Además, encontré que MathWorld''s descripciones de las secuencias de Sturm de Wikipedia y MathWorld''s útiles para entender la primera parte del algoritmo, ya que el documento en sí no es muy claro en su propia descripción.

Answer 3

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

Demostración: 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 desviar de manera eficiente entre vectores (en 2D, 3D o 4D), pero sería trivial reemplazar la llamada bézierPoint() en bézierPoint() con su propio código.

Afinando el algoritmo

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

• Primero, calcule puntos a lo largo de la curva (valores espaciados uniformemente 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 cazar la región alrededor de la distancia más pequeña, usando una búsqueda binaria para encontrar la t y el punto que produce la distancia más pequeña verdadera.

El valor de las scans en closestPoint() determina cuántas muestras se utilizarán en la primera pasada. Un menor número de escaneos es más rápido, pero aumenta las posibilidades de perder el punto mínimo verdadero.

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, por lo tanto, 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 , ...) genera aproximadamente 6-8 llamadas adicionales a bézierPoint() .