Un algoritmo per trovare il riquadro di delimitazione delle curve chiuse di bezier?

Question

Sto cercando un algoritmo per trovare rettangolo di selezione (max/min punti) di una curva chiusa quadratica di Bézier in assi cartesiani:

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

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

Nota: sopra di immagine mostra una superficie liscia curva. potrebbe non essere liscio. (avere angoli)

Answer 1

Bene, direi che inizi aggiungendo tutti gli endpoint al riquadro di selezione. Quindi, passerai attraverso tutti gli elementi più bezier. Suppongo che la formula in questione è questo:

Da questo estratto due formule per X, e Y, rispettivamente. Provare entrambi per extrema prendendo la derivata (zero crossing). Quindi aggiungi anche i punti corrispondenti al riquadro di delimitazione.

Answer 2

Credo che i punti di controllo di una curva di Bezier formino uno scafo convesso che racchiude la curva. Se si desidera solo un riquadro di delimitazione allineato all'asse, penso che sia necessario trovare il minimo e il massimo di ciascuno (x, y) per ciascun punto di controllo di tutti i segmenti.

Suppongo che potrebbe non essere un stretto casella. Cioè, la scatola potrebbe essere leggermente più grande di quanto dovrebbe essere, ma è semplice e veloce da calcolare. Immagino dipenda dalle tue esigenze.

Answer 3

Utilizzare l'algoritmo di De Casteljau per approssimare la curva degli ordini superiori. Ecco come funziona per curva cubica 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 è una forza bruta, ma funziona in molti casi. Il problema con esso è il conteggio delle iterazioni. La forma attuale e la distanza tra le coordinate influiscono sulla precisione del risultato. E per trovare una risposta abbastanza precisa, devi ripetere le decine di volte, potrebbe essere di più. E potrebbe fallire se ci sono curve strette in curva.

La soluzione migliore è trovare prime derivate, come descritto nell'eccellente sito http://processingjs.nihongoresources.com/bezierinfo/. Si prega di leggere la sezione Trovare le estremità delle curve.

Il collegamento sopra ha l'algoritmo per le curve quadratiche e cubiche.

Il richiedente la domanda è interessato alle curve quadratiche, quindi il resto di questa risposta potrebbe essere irrilevante, perché fornisco i codici per il calcolo delle estremità delle curve cubiche.

Di seguito sono riportati tre codici Javascript di cui il primo (CODICE 1) è quello che suggerisco di utilizzare.

---

** CODICE 1 **

Dopo processingjs test e le soluzioni di Raffaello Trovo che avevano alcune restrizioni e/o bug. Quindi più ricerca e trova Bonsai ed è bounding box function, che si basa sullo script Python di NISHIO Hirokazu. Entrambi hanno un lato negativo in cui viene testata la doppia uguaglianza utilizzando ==. Quando li ho trasformati in confronti numericamente robusti, lo script ha ottenuto il 100% giusto in tutti i casi.Ho provato lo script con migliaia di percorsi casuali ed anche con tutti i casi allineati e tutto riuscito:

Various cubic curves

Random cubic curves

Collinear cubic curves

Il codice è il seguente. Di solito i valori left, right, top e bottom sono tutti necessari, ma in alcuni casi è bene conoscere le coordinate dei punti estremi locali e i valori t corrispondenti. Quindi ho aggiunto due variabili: tvalues e points. Rimuovi il codice che ti riguarda e hai una funzione di calcolo del bounding box veloce e stabile.

// 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]} 

---

CODICE 2 (che non riesce in casi allineati):

ho tradotto il codice http://processingjs.nihongoresources.com/bezierinfo/sketchsource.php?sketch=tightBoundsCubicBezier a Javascript. Il codice funziona bene nei casi normali, ma non nei casi collineari in cui tutti i punti si trovano sulla stessa riga.

Per riferimento, ecco il codice 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; 
} 

---

CODICE 3 (funziona nella maggior parte dei casi):

Per gestire anche casi collineari, ho trovato la soluzione di Raphael, che si basa sullo stesso primo metodo derivato come CODE 2. Ho aggiunto anche un valore di ritorno dots, che ha i punti extrema, perché non è sempre sufficiente conoscere le caselle di confine min e max, ma vogliamo conoscere le coordinate estreme esatte.

MODIFICA: trovato un altro bug. Non riesce ad es. in 532,333,117,305,28,93,265,42 e anche in molti altri casi.

il codice è qui:

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

Penso che la risposta accettata va bene, ma solo voluto offrire un po 'più spiegazione per chiunque altro cercando di fare questo.

Si consideri un Bezier quadratico con punto di partenza p1, punto finale p2 e "punto di controllo" pc. Questa curva ha tre equazioni parametriche:

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

In tutti i casi, t va da 0 a 1 inclusi.

I primi due sono lineari, definendo segmenti di linea da p1 a pc e da pc a p2, rispettivamente.Il terzo è quadratico una volta che si sostituisce nelle espressioni per pa(t) e pb(t); questo è quello che definisce effettivamente i punti sulla curva.

In realtà, ciascuna di queste equazioni è una coppia di equazioni, una per la dimensione orizzontale e una per la verticale. Il bello delle curve parametriche è che le xey possono essere gestite indipendentemente l'una dall'altra. Le equazioni sono esattamente le stesse, basta sostituire x o per p nelle equazioni precedenti.

Il punto importante è che il segmento definito nell'equazione 3, che va da pa(t) a pb(t) per un valore specifico di t è tangente alla curva corrispondente punto p(t). Per trovare l'estremo locale della curva, è necessario trovare il valore del parametro in cui la tangente è piatta (cioè, un punto critico). Per la dimensione verticale, si desidera trovare il valore di ya(t) = yb(t), che fornisce alla tangente una pendenza di 0. Per la dimensione orizzontale, trovare t tale che xa(t) = xb(t), che dia alla tangente una pendenza infinita (ad esempio, una linea verticale). In ogni caso, puoi semplicemente ricollegare il valore di t all'equazione 1 (o 2, o anche 3) per ottenere la posizione di quell'estremo.

In altre parole, per trovare l'estremo verticale della curva, prendere solo la componente y delle equazioni 1 e 2, impostarle l'una uguale all'altra e risolvere per t; ricollegalo alla componente y dell'equazione 1, per ottenere il valore y di quell'estremo. Per ottenere la gamma y completa della curva, trovare il minimo di questo valore y estremo e le componenti y dei due punti finali, e allo stesso modo trovare il massimo di tutti e tre. Ripeti per x per ottenere i limiti orizzontali.

Ricordare che t viene eseguito solo in [0, 1], quindi se si ottiene un valore al di fuori di questo intervallo, significa che non vi è alcun estremo locale sulla curva (almeno non tra i due endpoint). Questo include il caso in cui finisci per dividere per zero quando risolvi il t, che probabilmente dovrai controllare prima di farlo.

La stessa idea può essere applicata ai Bezier di ordine superiore, ci sono solo più equazioni di grado più alto, il che significa anche che ci sono potenzialmente più estremi locali per curva. Ad esempio, su un Bezier cubico (due punti di controllo), risolvere per t per trovare gli estremi locali è un'equazione quadratica, in modo da poter ottenere valori 0, 1 o 2 (ricordarsi di controllare i denominatori 0 e il quadrato negativo -roots, entrambi i quali indicano che non ci sono estremi locali per quella dimensione). Per trovare l'intervallo, devi solo trovare il minimo/massimo di tutti gli estremi locali e i due punti finali.

Answer 6

ho risposto a questa domanda in Calculating the bounding box of cubic bezier curve

questo articolo spiegare i dettagli e ha anche un live demo HTML5:
Calculating/Computing the Bounding Box of Cubic Bezier

ho trovato un javascript in Snap.svg calcolare che: here
vedere le funzioni bezierBBox e curveDim.

Riscrivo una funzione 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)} 
    }; 
}