¿Algún algoritmo para encontrar el cuadro delimitador de curvas de bezier cerradas?

Question

Busco un algoritmo para encontrar delimitador (puntos max/min) cuadro de una curva cerrada cuadrática de Bézier en el eje cartesiano:

input: C (a closed bezier curve) 
output: A B C D points 

Image http://www.imagechicken.com/uploads/1270586513022388700.jpg

Nota: la imagen muestra una suave curva. podría no ser suave. (tener esquinas)

Answer 1

Bueno, yo diría que comienzas agregando todos los puntos finales a tu cuadro delimitador. Luego, revisas todos los elementos bezier. Asumo la fórmula en cuestión es la siguiente:

De este extracto dos fórmulas para X e Y respectivamente. Pruebe ambos extremos tomando la derivada (cruces por cero). A continuación, agregue los puntos correspondientes a su cuadro delimitador también.

Answer 2

Creo que los puntos de control de una curva Bezier forman un casco convexo que encierra la curva. Si solo quiere un cuadro delimitador alineado con el eje, creo que necesita encontrar el mínimo y el máximo de cada uno (x, y) para cada punto de control de todos los segmentos.

supongo que podría no ser un apretado cuadro . Es decir, la caja puede ser un poco más grande de lo que necesita ser, pero es simple y rápido de calcular. Supongo que depende de tus requisitos.

Answer 3

Utilice el algoritmo de De Casteljau para aproximar la curva de las órdenes superiores. Aquí es cómo funciona para curva cúbica http://jsfiddle.net/4VCVX/25/

function getCurveBounds(ax, ay, bx, by, cx, cy, dx, dy) 
{ 
     var px, py, qx, qy, rx, ry, sx, sy, tx, ty, 
      tobx, toby, tocx, tocy, todx, tody, toqx, toqy, 
      torx, tory, totx, toty; 
     var x, y, minx, miny, maxx, maxy; 

     minx = miny = Number.POSITIVE_INFINITY; 
     maxx = maxy = Number.NEGATIVE_INFINITY; 

     tobx = bx - ax; toby = by - ay; // directions 
     tocx = cx - bx; tocy = cy - by; 
     todx = dx - cx; tody = dy - cy; 
     var step = 1/40;  // precision 
     for(var d=0; d<1.001; d+=step) 
     { 
      px = ax +d*tobx; py = ay +d*toby; 
      qx = bx +d*tocx; qy = by +d*tocy; 
      rx = cx +d*todx; ry = cy +d*tody; 
      toqx = qx - px;  toqy = qy - py; 
      torx = rx - qx;  tory = ry - qy; 

      sx = px +d*toqx; sy = py +d*toqy; 
      tx = qx +d*torx; ty = qy +d*tory; 
      totx = tx - sx; toty = ty - sy; 

      x = sx + d*totx; y = sy + d*toty;     
      minx = Math.min(minx, x); miny = Math.min(miny, y); 
      maxx = Math.max(maxx, x); maxy = Math.max(maxy, y); 
     }   
     return {x:minx, y:miny, width:maxx-minx, height:maxy-miny}; 
} 

Answer 4

Ivan Kuckir's DeCasteljau es una fuerza bruta, pero funciona en muchos casos. El problema con esto es el conteo de iteraciones. La forma real y la distancia entre las coordenadas afectan a la precisión del resultado. Y para encontrar una respuesta lo suficientemente precisa, debe iterar decenas de veces, puede ser más. Y puede fallar si hay giros bruscos en la curva.

La mejor solución es encontrar primeras raíces derivadas, como se describe en el excelente sitio http://processingjs.nihongoresources.com/bezierinfo/. Por favor, lea la sección Encontrar los extremos de las curvas.

El enlace de arriba tiene el algoritmo para las curvas cuadradas y cúbicas.

El autor de la pregunta de pregunta es interesado en curvas cuadráticas, por lo que el resto de esta respuesta puede ser irrelevante, ya que proporciono códigos para el cálculo de las extremidades de las curvas cúbicas.

A continuación se muestran tres códigos Javascript cuyo primero (CÓDIGO 1) es el que sugiero usar.

---

** ** CÓDIGO 1

Después de prueba processingjs y soluciones de Rafael me parece que tenían algunas restricciones y/o errores. Luego busca más y encuentra Bonsai y es bounding box function, que se basa en el guión Python de NISHIO Hirokazu. Ambos tienen una desventaja donde se prueba la doble igualdad usando ==. Cuando cambié estas comparaciones a comparaciones numéricamente robustas, la secuencia de comandos tiene éxito al 100% en todos los casos.Probé el guión con miles de trayectorias aleatorias y también con todos los casos colineales y todos conseguí:

Various cubic curves

Random cubic curves

Collinear cubic curves

El código es el siguiente. Generalmente, los valores izquierdo, derecho, superior e inferior son los necesarios, pero en algunos casos está bien conocer las coordenadas de los puntos extremos locales y los valores t correspondientes. Entonces agregué dos variables: tvalues y points. Elimine el código relacionado con ellos y tenga una función de cálculo de cuadro delimitador rápida y estable.

// Source: http://blog.hackers-cafe.net/2009/06/how-to-calculate-bezier-curves-bounding.html 
// Original version: NISHIO Hirokazu 
// Modifications: Timo 

var pow = Math.pow, 
    sqrt = Math.sqrt, 
    min = Math.min, 
    max = Math.max; 
    abs = Math.abs; 

function getBoundsOfCurve(x0, y0, x1, y1, x2, y2, x3, y3) 
{ 
    var tvalues = new Array(); 
    var bounds = [new Array(), new Array()]; 
    var points = new Array(); 

    var a, b, c, t, t1, t2, b2ac, sqrtb2ac; 
    for (var i = 0; i < 2; ++i) 
    { 
    if (i == 0) 
    { 
     b = 6 * x0 - 12 * x1 + 6 * x2; 
     a = -3 * x0 + 9 * x1 - 9 * x2 + 3 * x3; 
     c = 3 * x1 - 3 * x0; 
    } 
    else 
    { 
     b = 6 * y0 - 12 * y1 + 6 * y2; 
     a = -3 * y0 + 9 * y1 - 9 * y2 + 3 * y3; 
     c = 3 * y1 - 3 * y0; 
    } 

    if (abs(a) < 1e-12) // Numerical robustness 
    { 
     if (abs(b) < 1e-12) // Numerical robustness 
     { 
     continue; 
     } 
     t = -c/b; 
     if (0 < t && t < 1) 
     { 
     tvalues.push(t); 
     } 
     continue; 
    } 
    b2ac = b * b - 4 * c * a; 
    sqrtb2ac = sqrt(b2ac); 
    if (b2ac < 0) 
    { 
     continue; 
    } 
    t1 = (-b + sqrtb2ac)/(2 * a); 
    if (0 < t1 && t1 < 1) 
    { 
     tvalues.push(t1); 
    } 
    t2 = (-b - sqrtb2ac)/(2 * a); 
    if (0 < t2 && t2 < 1) 
    { 
     tvalues.push(t2); 
    } 
    } 

    var x, y, j = tvalues.length, 
    jlen = j, 
    mt; 
    while (j--) 
    { 
    t = tvalues[j]; 
    mt = 1 - t; 
    x = (mt * mt * mt * x0) + (3 * mt * mt * t * x1) + (3 * mt * t * t * x2) + (t * t * t * x3); 
    bounds[0][j] = x; 

    y = (mt * mt * mt * y0) + (3 * mt * mt * t * y1) + (3 * mt * t * t * y2) + (t * t * t * y3); 
    bounds[1][j] = y; 
    points[j] = { 
     X: x, 
     Y: y 
    }; 
    } 

    tvalues[jlen] = 0; 
    tvalues[jlen + 1] = 1; 
    points[jlen] = { 
    X: x0, 
    Y: y0 
    }; 
    points[jlen + 1] = { 
    X: x3, 
    Y: y3 
    }; 
    bounds[0][jlen] = x0; 
    bounds[1][jlen] = y0; 
    bounds[0][jlen + 1] = x3; 
    bounds[1][jlen + 1] = y3; 
    tvalues.length = bounds[0].length = bounds[1].length = points.length = jlen + 2; 

    return { 
    left: min.apply(null, bounds[0]), 
    top: min.apply(null, bounds[1]), 
    right: max.apply(null, bounds[0]), 
    bottom: max.apply(null, bounds[1]), 
    points: points, // local extremes 
    tvalues: tvalues // t values of local extremes 
    }; 
}; 

// Usage: 
var bounds = getBoundsOfCurve(532,333,117,305,28,93,265,42); 
console.log(JSON.stringify(bounds)); 
// Prints: {"left":135.77684049079755,"top":42,"right":532,"bottom":333,"points":[{"X":135.77684049079755,"Y":144.86387466397255},{"X":532,"Y":333},{"X":265,"Y":42}],"tvalues":[0.6365030674846626,0,1]} 

---

CÓDIGO 2 (que falla en casos colineales):

que traduce el código de http://processingjs.nihongoresources.com/bezierinfo/sketchsource.php?sketch=tightBoundsCubicBezier a Javascript. El código funciona bien en casos normales, pero no en casos colineales donde todos los puntos se encuentran en la misma línea.

Como referencia, aquí está el código de Javascript.

function computeCubicBaseValue(a,b,c,d,t) { 
    var mt = 1-t; 
    return mt*mt*mt*a + 3*mt*mt*t*b + 3*mt*t*t*c + t*t*t*d; 
} 

function computeCubicFirstDerivativeRoots(a,b,c,d) { 
    var ret = [-1,-1]; 
    var tl = -a+2*b-c; 
    var tr = -Math.sqrt(-a*(c-d) + b*b - b*(c+d) +c*c); 
    var dn = -a+3*b-3*c+d; 
    if(dn!=0) { ret[0] = (tl+tr)/dn; ret[1] = (tl-tr)/dn; } 
    return ret; 
} 

function computeCubicBoundingBox(xa,ya,xb,yb,xc,yc,xd,yd) 
{ 
    // find the zero point for x and y in the derivatives 
    var minx = 9999; 
    var maxx = -9999; 
    if(xa<minx) { minx=xa; } 
    if(xa>maxx) { maxx=xa; } 
    if(xd<minx) { minx=xd; } 
    if(xd>maxx) { maxx=xd; } 
    var ts = computeCubicFirstDerivativeRoots(xa, xb, xc, xd); 
    for(var i=0; i<ts.length;i++) { 
     var t = ts[i]; 
     if(t>=0 && t<=1) { 
      var x = computeCubicBaseValue(t, xa, xb, xc, xd); 
      var y = computeCubicBaseValue(t, ya, yb, yc, yd); 
      if(x<minx) { minx=x; } 
      if(x>maxx) { maxx=x; }}} 

    var miny = 9999; 
    var maxy = -9999; 
    if(ya<miny) { miny=ya; } 
    if(ya>maxy) { maxy=ya; } 
    if(yd<miny) { miny=yd; } 
    if(yd>maxy) { maxy=yd; } 
    ts = computeCubicFirstDerivativeRoots(ya, yb, yc, yd); 
    for(i=0; i<ts.length;i++) { 
     var t = ts[i]; 
     if(t>=0 && t<=1) { 
      var x = computeCubicBaseValue(t, xa, xb, xc, xd); 
      var y = computeCubicBaseValue(t, ya, yb, yc, yd); 
      if(y<miny) { miny=y; } 
      if(y>maxy) { maxy=y; }}} 

    // bounding box corner coordinates 
    var bbox = [minx,miny, maxx,miny, maxx,maxy, minx,maxy ]; 
    return bbox; 
} 

---

CÓDIGO 3 (funciona en la mayoría de los casos):

Para mango también casos colineales, encontré solución de Rafael, que se basa en el mismo primer método derivado como el código 2. También agregué un valor de retorno dots, que tiene los puntos extremos, porque siempre no es suficiente conocer las coordenadas mínimas y máximas de los cuadros delimitadores, pero queremos conocer las coordenadas extremas exactas.

EDIT: encontré otro error. Falla, por ej. en 532,333,117,305,28,93,265,42 y también en muchos otros casos.

el código está aquí:

Array.max = function(array){ 
    return Math.max.apply(Math, array); 
}; 
Array.min = function(array){ 
    return Math.min.apply(Math, array); 
}; 

var findDotAtSegment = function (p1x, p1y, c1x, c1y, c2x, c2y, p2x, p2y, t) { 
     var t1 = 1 - t; 
     return { 
      x: t1*t1*t1*p1x + t1*t1*3*t*c1x + t1*3*t*t * c2x + t*t*t * p2x, 
      y: t1*t1*t1*p1y + t1*t1*3*t*c1y + t1*3*t*t * c2y + t*t*t * p2y 
     }; 
}; 
var cubicBBox = function (p1x, p1y, c1x, c1y, c2x, c2y, p2x, p2y) { 
     var a = (c2x - 2 * c1x + p1x) - (p2x - 2 * c2x + c1x), 
      b = 2 * (c1x - p1x) - 2 * (c2x - c1x), 
      c = p1x - c1x, 
      t1 = (-b + Math.sqrt(b * b - 4 * a * c))/2/a, 
      t2 = (-b - Math.sqrt(b * b - 4 * a * c))/2/a, 
      y = [p1y, p2y], 
      x = [p1x, p2x], 
      dot, dots=[]; 
     Math.abs(t1) > "1e12" && (t1 = 0.5); 
     Math.abs(t2) > "1e12" && (t2 = 0.5); 
     if (t1 >= 0 && t1 <= 1) { 
      dot = findDotAtSegment(p1x, p1y, c1x, c1y, c2x, c2y, p2x, p2y, t1); 
      x.push(dot.x); 
      y.push(dot.y); 
      dots.push({X:dot.x, Y:dot.y}); 
     } 
     if (t2 >= 0 && t2 <= 1) { 
      dot = findDotAtSegment(p1x, p1y, c1x, c1y, c2x, c2y, p2x, p2y, t2); 
      x.push(dot.x); 
      y.push(dot.y); 
      dots.push({X:dot.x, Y:dot.y}); 
     } 
     a = (c2y - 2 * c1y + p1y) - (p2y - 2 * c2y + c1y); 
     b = 2 * (c1y - p1y) - 2 * (c2y - c1y); 
     c = p1y - c1y; 
     t1 = (-b + Math.sqrt(b * b - 4 * a * c))/2/a; 
     t2 = (-b - Math.sqrt(b * b - 4 * a * c))/2/a; 
     Math.abs(t1) > "1e12" && (t1 = 0.5); 
     Math.abs(t2) > "1e12" && (t2 = 0.5); 
     if (t1 >= 0 && t1 <= 1) { 
      dot = findDotAtSegment(p1x, p1y, c1x, c1y, c2x, c2y, p2x, p2y, t1); 
      x.push(dot.x); 
      y.push(dot.y); 
      dots.push({X:dot.x, Y:dot.y}); 
     } 
     if (t2 >= 0 && t2 <= 1) { 
      dot = findDotAtSegment(p1x, p1y, c1x, c1y, c2x, c2y, p2x, p2y, t2); 
      x.push(dot.x); 
      y.push(dot.y); 
      dots.push({X:dot.x, Y:dot.y}); 
     } 
     // remove duplicate dots 
       var dots2 = []; 
       var l = dots.length; 
       for(var i=0; i<l; i++) { 
        for(var j=i+1; j<l; j++) { 
        if (dots[i].X === dots[j].X && dots[i].Y === dots[j].Y) 
         j = ++i; 
        } 
        dots2.push({X: dots[i].X, Y: dots[i].Y}); 
       } 
     return { 
     min: {x: Array.min(x), y: Array.min(y)}, 
     max: {x: Array.max(x), y: Array.max(y)}, 
     dots: dots2 // these are the extrema points 
     }; 
    }; 

Answer 5

creo que la respuesta aceptada está muy bien, pero sólo quería ofrecer un poco más de explicación para cualquier otra persona tratando de hacer esto.

Considere un Bezier cuadrático con punto de partida p1, punto final p2 y "punto de control" pc. Esta curva tiene tres ecuaciones paramétricas:

1. pa(t) = p1 + t(pc-p1)
2. pb(t) = pc + t(p2-pc)
3. p(t) = pa(t) + t*(pb(t) - pa(t))

En todos los casos, t va de 0 a 1, ambos inclusive.

Los dos primeros son lineales, definiendo los segmentos de línea p1-pc y de pc a p2, respectivamente.El tercero es cuadrático una vez que lo sustituye en las expresiones pa(t) y pb(t); este es el que realmente define puntos en la curva.

En realidad, cada una de estas ecuaciones es un par de ecuaciones, una para la dimensión horizontal, y uno para la vertical. Lo bueno de las curvas paramétricas es que las xey se pueden manejar independientemente una de la otra. Las ecuaciones son exactamente iguales, simplemente sustituya x o y por p en las ecuaciones anteriores.

El punto importante es que el segmento de línea definido en la ecuación 3, que se ejecuta pa(t)-pb(t) para un valor específico de t es tangente a la curva en el punto p(t) correspondiente. Para encontrar los extremos locales de la curva, necesita encontrar el valor del parámetro donde la tangente es plana (es decir, un punto crítico). Para la dimensión vertical, quiere encontrar el valor de t tal que ya(t) = yb(t), que le da a la tangente una pendiente de 0. Para la dimensión horizontal, encuentre t tal que xa(t) = xb(t), que le da a la tangente una pendiente infinita (es decir, una línea vertical) En cada caso, puede simplemente tapar el valor de t en la ecuación 1 (o 2, o incluso 3) para obtener la ubicación de ese extremo.

En otras palabras, para encontrar los extremos verticales de la curva, tome solo el componente y de las ecuaciones 1 y 2, ajústelos el uno al otro y resuelva para t; vuelva a enchufar esto en el componente y de la ecuación 1, para obtener el valor y de ese extremo. Para obtener el rango y completo de la curva, encuentre el mínimo de este valor extremo yy los componentes y de los dos puntos finales, y asimismo encuentre el máximo de los tres. Repite para x para obtener los límites horizontales.

Recuerde que t solo se ejecuta en [0, 1], por lo que si obtiene un valor fuera de este rango, significa que no hay extremos locales en la curva (al menos no entre sus dos puntos finales). Esto incluye el caso en el que termina dividiéndose por cero al resolver t, que probablemente necesitará verificar antes de hacerlo.

La misma idea se puede aplicar a Beziers de orden superior, no son sólo más ecuaciones de grado superior, que también significa que hay potencialmente extrema más local por curva. Por ejemplo, en un Bezier cúbico (dos puntos de control), resolver para t para encontrar los extremos locales es una ecuación cuadrática, por lo que podría obtener 0, 1 o 2 valores (recuerde verificar los denominadores 0, y para el cuadrado negativo -las raíces, que indican que no hay extremos locales para esa dimensión). Para encontrar el rango, solo necesita encontrar el mínimo/máximo de todos los extremos locales y los dos puntos finales.

Answer 6

que respondieron a esta pregunta en Calculating the bounding box of cubic bezier curve

este artículo explicar los detalles y también tiene una demostración en vivo html5:
Calculating/Computing the Bounding Box of Cubic Bezier

me encontré con un javascript en Snap.svg calcular que: here
ver las funciones bezierBBox y curveDim.

Reescribo una función de JavaScript.

//(x0,y0) is start point; (x1,y1),(x2,y2) is control points; (x3,y3) is end point. 
function bezierMinMax(x0, y0, x1, y1, x2, y2, x3, y3) { 
    var tvalues = [], xvalues = [], yvalues = [], 
     a, b, c, t, t1, t2, b2ac, sqrtb2ac; 
    for (var i = 0; i < 2; ++i) { 
     if (i == 0) { 
      b = 6 * x0 - 12 * x1 + 6 * x2; 
      a = -3 * x0 + 9 * x1 - 9 * x2 + 3 * x3; 
      c = 3 * x1 - 3 * x0; 
     } else { 
      b = 6 * y0 - 12 * y1 + 6 * y2; 
      a = -3 * y0 + 9 * y1 - 9 * y2 + 3 * y3; 
      c = 3 * y1 - 3 * y0; 
     } 
     if (Math.abs(a) < 1e-12) { 
      if (Math.abs(b) < 1e-12) { 
       continue; 
      } 
      t = -c/b; 
      if (0 < t && t < 1) { 
       tvalues.push(t); 
      } 
      continue; 
     } 
     b2ac = b * b - 4 * c * a; 
     if (b2ac < 0) { 
      continue; 
     } 
     sqrtb2ac = Math.sqrt(b2ac); 
     t1 = (-b + sqrtb2ac)/(2 * a); 
     if (0 < t1 && t1 < 1) { 
      tvalues.push(t1); 
     } 
     t2 = (-b - sqrtb2ac)/(2 * a); 
     if (0 < t2 && t2 < 1) { 
      tvalues.push(t2); 
     } 
    } 

    var j = tvalues.length, mt; 
    while (j--) { 
     t = tvalues[j]; 
     mt = 1 - t; 
     xvalues[j] = (mt * mt * mt * x0) + (3 * mt * mt * t * x1) + (3 * mt * t * t * x2) + (t * t * t * x3); 
     yvalues[j] = (mt * mt * mt * y0) + (3 * mt * mt * t * y1) + (3 * mt * t * t * y2) + (t * t * t * y3); 
    } 

    xvalues.push(x0,x3); 
    yvalues.push(y0,y3); 

    return { 
     min: {x: Math.min.apply(0, xvalues), y: Math.min.apply(0, yvalues)}, 
     max: {x: Math.max.apply(0, xvalues), y: Math.max.apply(0, yvalues)} 
    }; 
}