我正在寻找一种算法，用于在笛卡尔坐标系中查找封闭二次贝塞尔曲线的边界框（最大/最小点）：
input: C (a closed bezier curve)
output: A B C D points
图像 http://www.imagechicken.com/uploads/1270586513022388700.jpg
注意：上面的图像展示了一个平滑的曲线，但它也可能不是平滑的（有棱角）。
寻找封闭贝塞尔曲线的边界框算法？
24
- sorush-r
4
编辑到你的问题中。 - Femaref
如果您知道二次方程式，您能否不计算每个 x 值的 y 值，注意 x 值范围内的最低和最高 y 值？ - James Westgate
@ James Westgate：嗯...这可能很难计算，甚至将贝塞尔方程转换为每个曲线的y=f(x)形式也很困难。我正在编写Python代码来完成。所以我需要一个算法而不是一个解决方案。 - sorush-r
@JamesWestgate：如果我理解你的意思，那么你只是对曲线进行采样，找到确切边界的机会很小，而且可能会偏差很大。这就像尝试通过检查每个x的整数值的y值来找到抛物线的最小值一样。实际上，您需要在无穷小的距离上“采样”曲线，这就是微积分被发明的原因=）。 Beziers的好处是您不需要找到导数，它以一组参数方程的形式给出。 - brianmearns
8个回答
28
Ivan Kuckir's DeCasteljau 是一种蛮力算法，在许多情况下都有效。问题在于迭代次数。实际形状和坐标之间的距离影响结果的精度。为了找到足够精确的答案，您必须迭代十几次，甚至更多。如果曲线中有急转弯，则可能会失败。
更好的解决方案是找到一阶导数根，如http://processingjs.nihongoresources.com/bezierinfo/上所述。请阅读查找曲线的极值点部分。
上面的链接提供了二次和三次曲线的算法。
问题的提问者对二次曲线感兴趣，因此本答案的其余部分可能不相关，因为我提供的代码用于计算三次曲线的极值点。
以下是三个Javascript代码，其中第一个（CODE 1）是我建议使用的。
更好的解决方案是找到一阶导数根，如http://processingjs.nihongoresources.com/bezierinfo/上所述。请阅读查找曲线的极值点部分。
上面的链接提供了二次和三次曲线的算法。
问题的提问者对二次曲线感兴趣，因此本答案的其余部分可能不相关，因为我提供的代码用于计算三次曲线的极值点。
以下是三个Javascript代码，其中第一个（CODE 1）是我建议使用的。
** 代码1 **
在测试processingjs和Raphael的解决方案后，我发现它们存在一些限制和/或错误。然后进行更多搜索，并发现了Bonsai及其边界框函数，该函数基于NISHIO Hirokazu的Python脚本。两者都存在一个缺点，即使用 == 测试双重相等性。当我将这些更改为数值稳健的比较时，脚本在所有情况下都成功100％。我使用数千个随机路径以及所有共线情况测试了该脚本，所有情况都成功：
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（适用于大多数情况）：
为了处理共线的情况，我发现了Raphael的解决方案，它基于与代码2相同的一阶导数方法。我还添加了一个返回值dots，其中包含极值点，因为仅知道边界框的最小和最大坐标通常是不够的，我们想要知道确切的极值坐标。
编辑：发现另一个错误。在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
};
};
- Timo Kähkönen
5
如果你把
if (b2ac < 0) 这个检查向上移动一行，就可以避免尝试对负数求平方根。这在 JS 中没有问题，但可以使移植更容易。 - Sebastian@Domi CODE 3 在许多情况下都会失败。在这里可以看到一个例子：http://output.jsbin.com/vebavesivu/1 。蓝色矩形是正确的边界框，红色是CODE 3的边界框。我建议使用蓝色矩形代码（CODE 1）。 - Timo Kähkönen
@Timo 谢谢！显然我浏览了太多的解释！ :) - Domi
问题不是关于立方曲线而是二次曲线吗？ - Vytalyi
7
使用De Casteljau算法来逼近高阶曲线。以下是针对三次曲线的工作原理：
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};
}
- Ivan Kuckir
5
你能解释一下四个顶点的用途吗？哪些是锚点，哪些是控制点？ - Domi
当然，A（=[ax,ay]）是起点，D是终点。B是与A相关的控制点，C是与D相关的控制点。 - Ivan Kuckir
可能需要修正命名 :) - Domi
Bézeir曲线通常由N个点的序列定义，第一个点是起点，最后一个点是终点，中间的点控制形状。 - Ivan Kuckir
我喜欢评论中“precission”拼错了。非常精确。 - Tatarize
7
首先，你需要将所有端点添加到边界框中。然后，浏览所有的贝塞尔元素。我假设所提到的公式是这个：
从此，分别提取X和Y的两个公式。通过求导（零交叉）测试两者是否有极值。然后将相应的点也添加到边界框中。
- ypnos
5
2@ypnos：谢谢。我该如何使用编程语言进行极值测试？我认为这需要一个计算机代数系统，但我没有！你能介绍一个免费的Python计算机代数系统吗？ - sorush-r
2直接计算导数为零的点更容易，公式为t0=(P1-P0)/(P0-2P1+P2)。 - tom10
在你的情况下，极值测试是一个相当简单的公式，解的数量事先已知。因此，您可能需要一个或两个if语句，但其余部分只是计算。很抱歉，我不会Python。 - ypnos
2Tom：我认为你的公式有符号错误。应该是t0=(P1-P0)/(-P0+2P1-P2)。 - Gerrit Beuze
如何“提取X和Y的两个公式”？ - Ky -
5
我认为贝塞尔曲线的控制点形成一个凸包，将曲线围起来。如果你只需要一个轴对齐的边界框，我认为你需要找到所有段的每个控制点的每个(x,y)的最小值和最大值。
我想这可能不是一个紧密的盒子。也就是说，盒子可能比它需要的稍微大一些，但计算简单快捷。我猜这取决于你的要求。
- Adrian McCarthy
6
@Adrian McCarthy：谢谢您的回答。但我需要找到一个面积最小的矩形。 - sorush-r
3根据维基百科的说法，贝塞尔曲线完全包含在其控制点的凸包中。 - Adrian McCarthy
如果我们只考虑离散控制点，那么“曲线可以超出控制点的边界”是正确的。但如果还将起始点和结束点视为控制点，则该句不成立。 - Timo Kähkönen
@Timo：你能澄清一下吗？贝塞尔曲线的起点和终点属于控制点集合。为了形成凸包，必须包括它们以及其他控制点。 - Adrian McCarthy
我的意思是@drawnonward的评论很危险，因为它假设起点和终点不是控制点。通常它们被视为控制点，那么这个句子就不成立了。 - Timo Kähkönen
@AdrianMcCarthy 给你点赞，提供了明智而有用的建议；虽然它不会是一个紧凑的盒子，但使用四个点（一个三次贝塞尔曲线的所有点）来形成其边界框将更加高效和简单易用。 - legends2k
5
我认为接受的答案很好，但是想为任何试图做到这一点的人提供更多解释。
考虑一个二次贝塞尔曲线，其起始点为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（包括1）运行。
前两个是线性的，分别定义了从p1到pc和从pc到p2的线段。第三个是二次的，一旦代入pa(t)和pb(t)的表达式，就可以定义曲线上的点。
实际上，每个方程都是一对方程，一个用于水平维度，一个用于垂直维度。参数曲线的好处是x和y可以独立处理。方程完全相同，只需在上述方程中用x或y代替p。
重要的是，在特定t值处从pa(t)到pb(t)运行的线段在相应点p(t)处是切线。要找到曲线的局部极值，需要找到切线为平坦（即临界点）的参数值。对于垂直维度，您需要找到使ya(t) = yb(t)的t值，这会给出切线的斜率为0。对于水平维度，找到t值，使xa(t) = xb(t)，这会给出切线的无限斜率（即竖直线）。在每种情况下，您只需将t的值插回方程1（或2，甚至3）中，以获取该极值的位置。
换句话说，要找到曲线的垂直极值，只需取方程1和2的y分量，将它们设置为相等并解决t；将其插入方程1的y分量中，以获取该极值的y值。要获取曲线的完整y范围，找到此极端y值和两个端点的y分量的最小值，并找到所有三个的最大值。重复此过程以获取水平限制。
t只在[0,1]范围内运行，因此如果您得到超出此范围的值，则意味着曲线上没有局部极值（至少在两个端点之间没有）。这包括您在解决t时最终除以零的情况，您需要在执行此操作之前进行检查。同样的想法可以应用于高阶Bezier曲线，只是有更多的高次方程，这也意味着每条曲线可能有更多的局部极值。例如，在三次Bezier曲线（两个控制点）上，解决
t以找到局部极值是一个二次方程，因此您可以得到0、1或2个值（记得检查0分母和负平方根，两者都表明该维度没有局部极值）。要找到范围，您只需要找到所有局部极值和两个端点的最小/最大值即可。- brianmearns
3
我在计算三次贝塞尔曲线的边界框中回答了这个问题。
这篇文章详细解释了细节，并且还有一个实时的HTML5演示：
计算三次贝塞尔曲线的边界框
我在Snap.svg中找到了一个用于计算的JavaScript：这里
请查看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)}
};
}
- cuixiping
1
Timo的第一个变体适配到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`s 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;
}
- Massmaker
1
这里未定义
CubicBezier函数。 - Ky -0
Timo's CODE 2 answer 存在一个小错误：在 computeCubicBaseValue 函数中，t 参数应该放在最后。不过还是干得好，非常好用 ;)
C# 解决方案：
double computeCubicBaseValue(double a, double b, double c, double d, double t)
{
var mt = 1 - t;
return mt * mt * mt * a + 3 * mt * mt * t * b + 3 * mt * t * t * c + t * t * t * d;
}
double[] computeCubicFirstDerivativeRoots(double a, double b, double c, double d)
{
var ret = new double[2] { -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;
}
public double[] ComputeCubicBoundingBox(Point start, Point firstControl, Point secondControl, Point end)
{
double xa, ya, xb, yb, xc, yc, xd, yd;
xa = start.X;
ya = start.Y;
xb = firstControl.X;
yb = firstControl.Y;
xc = secondControl.X;
yc = secondControl.Y;
xd = end.X;
yd = end.Y;
// find the zero point for x and y in the derivatives
double minx = Double.MaxValue;
double maxx = Double.MinValue;
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(xa, xb, xc, xd,t);
var y = computeCubicBaseValue(ya, yb, yc, yd,t);
if (x < minx) { minx = x; }
if (x > maxx) { maxx = x; }
}
}
double miny = Double.MaxValue;
double maxy = Double.MinValue;
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 (var i = 0; i < ts.Length; i++)
{
var t = ts[i];
if (t >= 0 && t <= 1)
{
var x = computeCubicBaseValue(xa, xb, xc, xd,t);
var y = computeCubicBaseValue(ya, yb, yc, yd,t);
if (y < miny) { miny = y; }
if (y > maxy) { maxy = y; }
}
}
// bounding box corner coordinates
var bbox = new double[] { minx, miny, maxx, maxy};
return bbox;
}
- Jakub Sedziak
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
- 相关问题
- 3 Objective-C中的贝塞尔曲线算法
- 13 绘制SVG贝塞尔曲线
- 46 将二次贝塞尔曲线转换为三次贝塞尔曲线
- 14 逐像素贝塞尔曲线
- 10 检测封闭贝塞尔曲线中的自交问题
- 12 分割贝塞尔曲线
- 14 加入贝塞尔曲线
- 11 算法：为贝塞尔曲线添加颜色
- 10 计算三次贝塞尔曲线的边界框
- 3 贝塞尔曲线弧长