Алгоритм поиска ограничительной рамки замкнутых кривых Безье?

Question

Я ищу алгоритм, чтобы найти ограничивающий прямоугольник (макс/мин точек) замкнутой квадратичной кривой Безье в декартовой оси:

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

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

Примечание: выше изображение показывает гладкое кривая. это может быть негласно. (есть углы)

Answer 1

Ну, я бы сказал, что вы начинаете с добавления всех конечных точек в свою ограничительную рамку. Затем вы проходите все элементы безье. Я предполагаю, что формула в вопросе это одна:

Из этого отрывка две формулы для X и Y соответственно. Испытайте как экстремумы, взяв производную (пересечение нуля). Затем добавьте соответствующие точки в свою ограничительную рамку.

Answer 2

Я считаю, что контрольные точки кривой Безье образуют выпуклую оболочку, которая охватывает кривую. Если вы просто хотите ограничивать по оси ограничительную рамку, я думаю, вам нужно найти min и max каждого (x, y) для каждой контрольной точки всех сегментов.

Я полагаю, что это может быть не плотно коробка. То есть, поле может быть немного больше, чем должно быть, но это просто и быстро для вычисления. Я думаю, это зависит от ваших требований.

Answer 3

Использовать алгоритм Де Кастеляу для аппроксимации кривой высших порядков. Вот как это работает для кубической кривой 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 это перебор, но работает во многих случаях. Проблема с этим - количество итераций. Фактическая форма и расстояние между координатами влияют на точность результата. И чтобы найти достаточно точный ответ, вы должны повторять десятки раз, может быть больше. И это может потерпеть неудачу, если есть резкие повороты в кривой.

Лучшее решение - найти первые производные корни, как описано на отличном сайте http://processingjs.nihongoresources.com/bezierinfo/. Пожалуйста, ознакомьтесь с разделом Поиск контуров кривых.

Ссылка выше имеет алгоритм как для квадратичной, так и для кубической кривых.

Вопросник интересует квадратичные кривые, поэтому остальная часть этого ответа может быть неактуальной, поскольку я предоставляю коды для вычисления конечностей кубических кривых.

Ниже приведены три Javascript-кода, из которых первый (КОД 1) является тем, который я предлагаю использовать.

---

** КОД 1 **

После тестирования processingjs и решений Рафаэля я нахожу у них были какие-то ограничения и/или ошибок. Затем больше поиска и нашел Bonsai, и это bounding box function, основанный на скрипте Python от NISHIO Hirokazu. Оба имеют недостаток, когда двойное равенство проверяется с использованием ==. Когда я изменил их на численно надежные сравнения, тогда скрипт успешно выполнил 100% во всех случаях.Я тестировал скрипт с тысячами случайных путей, а также со всех случаях коллинеарных и все удалось:

Various cubic curves

Random cubic curves

Collinear cubic curves

Код выглядит следующим образом. Обычно левые, правые, верхние и нижние значения являются необходимыми, но в некоторых случаях хорошо знать координаты локальных крайних точек и соответствующих значений 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]} 

---

CODE 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 (работает в большинстве случаев):

Для обработки также коллинеарные случаи, я нашел решение Рафаэля, который основан на той же самой первой производной метода в качестве кода 2. Я добавил также возвращаемое значение dots, которое имеет точки экстремумов, потому что всегда недостаточно знать ограничивающие поля мин и макс, но мы хотим знать точные координаты экстремумов.

EDIT: обнаружена еще одна ошибка. Не работает, например. в 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 
     }; 
    }; 

Answer 5

Я думаю, что принятый ответ хорошо, но просто хотел предложить немного больше объяснений для тех, кто еще пытается сделать это.

Рассмотрите квадратичный Безье с начальной точкой p1, конечная точка p2 и "контрольная точка" pc. Эта кривая имеет три параметрические уравнения:

1. pa(t) = p1 + t(pc-p1)
2. pb(t) = pc + t(p2-pc)
3. 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), что дает касательную бесконечный уклон (т. Е. Вертикальную линию). В каждом случае вы можете просто включить значение t обратно в уравнение 1 (или 2 или даже 3), чтобы получить местоположение этих экстремумов.

Другими словами, чтобы найти вертикальные экстремумы кривой, возьмите только y-составляющую уравнений 1 и 2, установите их равными друг другу и решите для t; подключите это обратно к y-компоненте уравнения 1, чтобы получить y-значение этих экстремумов. Чтобы получить полный y-диапазон кривой, найдите минимум этого крайнего значения y и y-компонентов двух конечных точек, а также найдите максимум из трех. Повторите для x, чтобы получить горизонтальные пределы.

Помните, что t работает только в [0, 1], поэтому, если вы получаете значение вне этого диапазона, это означает, что на кривой нет локальных экстремумов (по крайней мере, не между двумя вашими конечными точками). Это включает случай, когда вы заканчиваете деление на ноль при решении для t, которое вам, вероятно, нужно будет проверить, прежде чем вы это сделаете.

Та же идея может быть применена к более поздним Безье, есть только более высокие уравнения с высокой степенью, что также означает, что на каждую кривую потенциально больше локальных экстремумов. Например, на кубическом Безье (две контрольные точки) решение для t найти локальные экстремумы является квадратичным уравнением, поэтому вы можете получить значения 0, 1 или 2 (не забудьте проверить 0-знаменатели, а для отрицательного квадрата -roots, оба из которых указывают, что для этой размерности нет локальных экстремумов). Чтобы найти диапазон, вам просто нужно найти min/max всех локальных экстремумов и двух конечных точек.

Answer 6

Я ответил на этот вопрос в Calculating the bounding box of cubic bezier curve

в этой статье объяснить детали, а также имеет живой html5 демо:
Calculating/Computing the Bounding Box of Cubic Bezier

Я нашел JavaScript в Snap.svg, чтобы вычислить, что: here
см функции 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)} 
    }; 
}