algorithm - pierre - ¿Un algoritmo para encontrar el cuadro delimitador de curvas cerradas de bezier?

lineas curvas de bezier

Question

Estoy buscando un algoritmo para encontrar el cuadro delimitador (puntos máximo / mínimo) de una curva bezier cuadrática cerrada en el eje cartesiano:

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

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

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

Answer 1

Bueno, yo diría que comienza agregando todos los puntos finales a su cuadro delimitador. Luego, pasas por todos los elementos de Bezier. Asumo que la fórmula en cuestión es esta:

De este extracto se extraen dos fórmulas para X e Y respectivamente. Prueba ambos para extremos tomando la derivada (cero cruces). Luego agrega los puntos correspondientes a tu caja delimitadora también.

Answer 2

Creo que la respuesta aceptada está bien, pero solo quería ofrecer un poco más de explicación a cualquier otra persona que intente hacer esto.

Considere un Bezier cuadrático con punto de inicio p1 , punto de finalización p2 y pc "punto de control". 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 segmentos de línea de p1 a pc y de pc a p2 , respectivamente. El tercero es cuadrático una vez que sustituyas 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 otra para la vertical. Lo bueno de las curvas paramétricas es que la x y la y se pueden manejar de manera independiente una de otra. Las ecuaciones son exactamente iguales, solo sustituye 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 va de pa(t) a pb(t) para un valor específico de t es tangente a la curva en el punto correspondiente p(t) . 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, desea encontrar el valor de t tal que ya(t) = yb(t) , lo 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 volver a insertar 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 de manera igualitaria y resuelva para t ; vuelva a conectar 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 y extremo y los componentes y de los dos puntos finales, y también encuentre el máximo de los tres. Repita 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 terminas dividiendo por cero al resolver t , que probablemente deberás verificar antes de hacerlo.

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

Answer 3

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

Supongo que eso podría no ser una caja apretada . Es decir, la caja puede ser un poco más grande de lo que debe ser, pero es fácil y rápido de calcular. Supongo que depende de tus necesidades.

Answer 4

Respondí esta pregunta en Cálculo del cuadro delimitador de la curva bezier cúbica

Este artículo explica los detalles y también tiene una demostración en vivo de html5:
Cálculo / cálculo de la caja delimitadora de Cubic Bezier

Encontré un javascript en Snap.svg para calcular eso: 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)}
};
}

Answer 5

Utilice el algoritmo de De Casteljau para aproximar la curva de órdenes superiores. Así es como funciona para la 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 6

DeCasteljau de Ivan Kuckir es una fuerza bruta, pero funciona en muchos casos. El problema con ello es la cuenta 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, tienes que iterar decenas de veces, puede ser más. Y puede fallar si hay curvas cerradas en la curva.

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

El enlace de arriba tiene el algoritmo para curvas tanto cuadráticas como cúbicas.

El interrogador está interesado en las curvas cuadráticas, por lo que el resto de esta respuesta puede ser irrelevante, porque proporciono códigos para calcular las extremidades de las curvas cúbicas.

Abajo hay tres códigos de Javascript de los cuales el primero (CÓDIGO 1) es el que sugiero usar.

** CÓDIGO 1 **

Después de probar el procesamiento y las soluciones de Raphael, descubrí que tenían algunas restricciones y / o errores. Luego, más buscó y encontró Bonsai y su función de cuadro delimitador , que se basa en el script Python de Hirokazu de NISHIO. Ambos tienen un inconveniente en el que la igualdad doble se prueba utilizando == . Cuando los cambié a comparaciones numéricamente sólidas, la secuencia de comandos tiene éxito al 100% en todos los casos. Probé la secuencia de comandos con miles de rutas aleatorias y también con todos los casos colineales y todos fueron exitosos:

Varias curvas cúbicas.

Curvas cúbicas aleatorias

Curvas colineales cúbicas

El código es el siguiente. Por lo general, los valores de izquierda, derecha, arriba y abajo son todos los necesarios, pero en algunos casos está bien conocer las coordenadas de los puntos extremos locales y los valores t correspondientes. Así que agregué allí dos variables: tvalues y points . Elimine el código que les concierne y tendrá una función de cálculo del 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):

Traduje 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.

Para referencia, aquí está el código 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 manejar también los casos colineales, encontré la solución de Raphael, que se basa en el mismo primer método derivado que el CÓDIGO 2. También agregué dots valor de retorno, que tienen los puntos extremos, porque siempre no es suficiente saber los cuadros de delimitación min y Coordenadas máximas, pero queremos saber las coordenadas extremas exactas.

EDITAR: encontré otro error. Falla por ejemplo en 532,333,117,305,28,93,265,42 y también 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
};
};