Я ищу алгоритм для поиска ограничивающей рамки (максимальные/минимальные точки) замкнутой квадратичной кривой Безье в декартовой оси:
input: C (a closed bezier curve)
output: A B C D points
Изображение http://www.imagechicken.com/uploads/1270586513022388700.jpg
Примечание: над изображением отображается плавная кривая. это может быть негласно. (имеют углы)
Ну, я бы сказал, что вы начнете с добавления всех конечных точек в ограничивающую рамку. Затем вы проходите все элементы Безье. Я предполагаю, что эта формула такая:
Из этого извлекаем две формулы для X и Y соответственно. Проверьте оба экстремума, взяв производную (пересечение нуля). Затем добавьте соответствующие точки в вашу ограничивающую рамку.
Иван Кукир Де Кастеляу - грубая сила, но работает во многих случаях. Проблема с этим - количество итераций. Фактическая форма и расстояние между координатами влияют на точность результата. И чтобы найти достаточно точный ответ, вам придется повторяться десятки раз, может быть и больше. И он может потерпеть неудачу, если есть крутые повороты на кривой.
Лучшее решение - найти первые производные корни, как описано на отличном сайте http://processingjs.nihongoresources.com/bezierinfo/. Пожалуйста, прочитайте раздел " Нахождение конечностей кривых".
Ссылка выше имеет алгоритм как для квадратичных, так и для кубических кривых.
Задавший вопрос интересуется квадратичными кривыми, поэтому остальная часть этого ответа может быть неактуальной, потому что я предоставляю коды для вычисления конечностей кубических кривых.
Ниже приведены три кода Javascript, первый из которых (КОД 1) - это тот, который я предлагаю использовать.
** КОД 1 **
После тестирования processingjs и решений Raphael я обнаружил, что у них были некоторые ограничения и/или ошибки. Затем продолжил поиск и нашел бонсай и его ограничивающую функцию, которая основана на скрипте NISHIO Hirokazu Python. У обоих есть обратная сторона, где двойное равенство проверяется с помощью ==. Когда я изменил их на численно устойчивые сравнения, тогда сценарий успешно выполняется на 100% правильно во всех случаях. Я проверил сценарий с тысячами случайных путей, а также со всеми коллинеарными случаями, и все удалось:
Коллинеарные кубические кривые
Код выглядит следующим образом. Обычно левые, правые, верхние и нижние значения - это все, что нужно, но в некоторых случаях хорошо знать координаты локальных крайних точек и соответствующие значения t. Поэтому я добавил туда две переменные: tvalues и points. Удалите код, относящийся к ним, и вы получите быструю и стабильную функцию расчета ограничительной рамки.
// 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]}
КОД 2 (который не работает в коллинеарных случаях):
Я перевел код с http://processingjs.nihongoresources.com/bezierinfo/sketchsource.php?sketch=tightBoundsCubicBezier в Javascript. Код работает нормально в обычных случаях, но не в коллинеарных случаях, когда все точки лежат на одной линии.
Для справки вот код 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;
}
КОД 3 (работает в большинстве случаев):
Для обработки коллинеарных случаев я нашел решение Рафаэля, основанное на том же методе первой производной, что и в CODE 2. Я добавил также возвращаемое значение dots, которое имеет точки экстремумов, потому что всегда недостаточно знать ограничивающие рамки min и Максимальные координаты, но мы хотим знать точные координаты экстремумов.
РЕДАКТИРОВАТЬ: обнаружил еще одну ошибку. Сбой например в 532,333,117,305,28,93,265,42, а также во многих других случаях.
Код здесь:
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
};
};
Использовать алгоритм Де Кастеляу для аппроксимации кривой высших порядков. Вот как это работает для кубической кривой 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};
}
Я считаю, что контрольные точки кривой Безье образуют выпуклую оболочку, которая охватывает кривую. Если вам просто нужен ограничивающий прямоугольник по оси, я думаю, вам нужно найти min и max каждого (x, y) для каждой контрольной точки всех сегментов.
Я полагаю, что это может быть не плотная коробка. То есть, поле может быть немного больше, чем должно быть, но это просто и быстро для вычисления. Я думаю, это зависит от ваших требований.
Я думаю, что принятый ответ в порядке, но просто хотел предложить немного больше объяснений для других, кто пытается это сделать.
Рассмотрим квадратичный Безье с начальной точкой p1, конечной точкой p2 и "контрольной точкой" pc. Эта кривая имеет три параметрических уравнения:
pa(t) = p1 + t(pc-p1)pb(t) = pc + t(p2-pc)p(t) = pa(t) + t*(pb(t) - pa(t))Во всех случаях t работает от 0 до 1 включительно.
Первые два являются линейными, определяя сегменты линии от p1 до pc и от pc до p2 соответственно. Третий квадратичный, если вы замените выражения для pa(t) и pb(t); это тот, который фактически определяет точки на кривой.
Собственно, каждое из этих уравнений представляет собой пару уравнений: одно для горизонтального размера и одно для вертикали. Самое приятное в параметрических кривых состоит в том, что x и y можно обрабатывать независимо друг от друга. Уравнения точно такие же, просто замените x или y на p в приведенных выше уравнениях.
Важным моментом является то, что отрезок линии, определенный в уравнении 3, который исходит от pa(t) до pb(t) для конкретного значения t, касается кривой в соответствующей точке p(t). Чтобы найти локальные экстремумы кривой, вам нужно найти значение параметра, где касательная плоская (т.е. Критическая точка). Для вертикальной размерности вы хотите найти значение t такое, что ya(t) = yb(t), которое дает касательную наклонность 0. Для горизонтальной размерности найдем t такую, что xa(t) = xb(t), которая дает касательную a бесконечный наклон (т.е. вертикальная линия). В каждом случае вы можете просто включить значение t обратно в уравнение 1 (или 2 или даже 3), чтобы получить местоположение этих экстремумов.
t; подключите это обратно к y-компоненте уравнения 1, чтобы получить y-значение этих экстремумов. Чтобы получить полный y-диапазон кривой, найдите минимум этого крайнего значения y и y-компонентов двух конечных точек, а также найдите максимум из трех. Повторите для x, чтобы получить горизонтальные пределы.
Помните, что t работает только в [0, 1], поэтому, если вы получаете значение вне этого диапазона, это означает, что на кривой нет локальных экстремумов (по крайней мере, не между двумя вашими конечными точками). Это включает случай, когда вы заканчиваете деление на ноль при решении для t, которое вам, вероятно, нужно будет проверить, прежде чем вы это сделаете.
Та же самая идея может быть применена и для более высоких степеней Безье, есть только больше уравнений более высокой степени, что также означает, что на каждую кривую потенциально больше локальных экстремумов. Например, на кубическом Безье (две контрольные точки) решение для t найти локальные экстремумы является квадратичным уравнением, поэтому вы можете получить значения 0, 1 или 2 (не забудьте проверить 0-знаменатели, а для отрицательные квадратные корни, оба из которых указывают на отсутствие локальных экстремумов для этой размерности). Чтобы найти диапазон, вам просто нужно найти min/max всех локальных экстремумов и двух конечных точек.
Я ответил на этот вопрос в Вычисление ограничивающей рамки кубической кривой безье
В этой статье объясняются подробности, а также есть живая версия html5:
Вычисление/вычисление ограничивающей коробки кубического Безье
Я нашел javascript в Snap.svg, чтобы вычислить это: здесь
см. функции bezierBBox и curveDim.
Я переписываю функцию 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)}
};
}
Тимо-первый вариант адаптирован к Objective-C
CGPoint CubicBezierPointAt(CGPoint p1, CGPoint p2, CGPoint p3, CGPoint p4, CGFloat t) {
CGFloat x = CubicBezier(p1.x, p2.x, p3.x, p4.x, t);
CGFloat y = CubicBezier(p1.y, p2.y, p3.y, p4.y, t);
return CGPointMake(x, y);
}
// array containing TopLeft and BottomRight points for curve enclosing bounds
NSArray* CubicBezierExtremums(CGPoint p1, CGPoint p2, CGPoint p3, CGPoint p4) {
CGFloat a, b, c, t, t1, t2, b2ac, sqrtb2ac;
NSMutableArray *tValues = [NSMutableArray new];
for (int i = 0; i < 2; i++) {
if (i == 0) {
a = 3 * (-p1.x + 3 * p2.x - 3 * p3.x + p4.x);
b = 6 * (p1.x - 2 * p2.x + p3.x);
c = 3 * (p2.x - p1.x);
}
else {
a = 3 * (-p1.y + 3 * p2.y - 3 * p3.y + p4.y);
b = 6 * (p1.y - 2 * p2.y + p3.y);
c = 3 * (p2.y - p1.y);
}
if(ABS(a) < CGFLOAT_MIN) {// Numerical robustness
if (ABS(b) < CGFLOAT_MIN) {// Numerical robustness
continue;
}
t = -c / b;
if (t > 0 && t < 1) {
[tValues addObject:[NSNumber numberWithDouble:t]];
}
continue;
}
b2ac = pow(b, 2) - 4 * c * a;
if (b2ac < 0) {
continue;
}
sqrtb2ac = sqrt(b2ac);
t1 = (-b + sqrtb2ac) / (2 * a);
if (t1 > 0.0 && t1 < 1.0) {
[tValues addObject:[NSNumber numberWithDouble:t1]];
}
t2 = (-b - sqrtb2ac) / (2 * a);
if (t2 > 0.0 && t2 < 1.0) {
[tValues addObject:[NSNumber numberWithDouble:t2]];
}
}
int j = (int)tValues.count;
CGFloat x = 0;
CGFloat y = 0;
NSMutableArray *xValues = [NSMutableArray new];
NSMutableArray *yValues = [NSMutableArray new];
while (j--) {
t = [[tValues objectAtIndex:j] doubleValue];
x = CubicBezier(p1.x, p2.x, p3.x, p4.x, t);
y = CubicBezier(p1.y, p2.y, p3.y, p4.y, t);
[xValues addObject:[NSNumber numberWithDouble:x]];
[yValues addObject:[NSNumber numberWithDouble:y]];
}
[xValues addObject:[NSNumber numberWithDouble:p1.x]];
[xValues addObject:[NSNumber numberWithDouble:p4.x]];
[yValues addObject:[NSNumber numberWithDouble:p1.y]];
[yValues addObject:[NSNumber numberWithDouble:p4.y]];
//find minX, minY, maxX, maxY
CGFloat minX = [[xValues valueForKeyPath:@"@min.self"] doubleValue];
CGFloat minY = [[yValues valueForKeyPath:@"@min.self"] doubleValue];
CGFloat maxX = [[xValues valueForKeyPath:@"@max.self"] doubleValue];
CGFloat maxY = [[yValues valueForKeyPath:@"@max.self"] doubleValue];
CGPoint origin = CGPointMake(minX, minY);
CGPoint bottomRight = CGPointMake(maxX, maxY);
NSArray *toReturn = [NSArray arrayWithObjects:
[NSValue valueWithCGPoint:origin],
[NSValue valueWithCGPoint:bottomRight],
nil];
return toReturn;
}