Once again you can do this with differentiation and get an 'exact' answer, and
I suspect it is more effecient to do so than buddy4n's suggestion of tracking
the path.
Differentiating the parametric equations
x = pu³ + qu² + ru + s
y = wu³ + xu² + yu + z
gives
dx/du = 3pu² + 2qu + r and
dy/du = 3wu² + 2xu + y
from which values of u can be found for the turning points (dx/du = 0) by the
standard quadratic formula (x = [-b±sqrt(b²-4ac)]/2a) as
u = [-2q ± sqrt(4q²-12pr)] / 6p = [-q ± sqrt(q²-3pr)] / 3p (for x) and v = [-x
± sqrt(x²-3wy)] / 3w (for y)
There are two values for each of u and v, one for the minimum and one for the
maximum. For each value, if it is less than 0 then the beginning of the curve
is the min/max, if it is greater than 1 then the end is, and if it is between
then you need to calculate the appropriate x (or y) by using u (or v) in the
initial equations.
Now, unfortunately, this is for a cubic curve of infinite length, and sometimes
it doesn't work.
- If there are no turning points in one direction, there will be no solutions
for u (q²-3pr is negative). In this case use the values at the endpoints.
- If either endpoint is outside the bounding box you just calculated, expand
the bounding box to accommodate it.
The bounding box of a whole path is obviously the 'bounding box of bounding
boxes'. This method should give the box for a cubic Bézier segment.
This is the C# I use for this problem. Alas I used different names for the
variables:
t is the parametric variable (u above)
a, b, c are the (2D) constants of the equation (a=(p, w); b = (q, x) ... etc
from above)
public RectangleF GetBoundingBox(){
RectangleF res = new RectangleF();
// Find values of t for max x
// t = [-b ± sqrt(b²-3ac)] / 3a (if a != 0)
// t = -c/2b (if a = 0)
double tx1, tx2, ty1, ty2;
if(a.X != 0){
tx1 = (-b.X + Math.Sqrt((b.X*b.X) - (3 * a.X *
c.X))) / (3 * a.X);
tx2 = (-b.X - Math.Sqrt((b.X*b.X) - (3 * a.X *
c.X))) / (3 * a.X);
} else if (b.X != 0) {
tx1 = -c.X / (2.0 * b.X);
tx2 = 0;
} else {
tx1 = 0; tx2 = 1;
}
if(Double.IsNaN(tx1)){ tx1 = 0; tx2 = 1; }
if(a.Y != 0){
ty1 = (-b.Y + Math.Sqrt((b.Y*b.Y) - (3 * a.Y *
c.Y))) / (3 * a.Y);
ty2 = (-b.Y - Math.Sqrt((b.Y*b.Y) - (3 * a.Y *
c.Y))) / (3 * a.Y);
} else if(b.Y != 0) {
ty1 = -c.Y / (2.0 * b.Y);
ty2 = 0;
} else {
ty1 = 0; ty2 = 1;
}
if(Double.IsNaN(ty1)){ ty1 = 0; ty2 = 1; }
Console.WriteLine("--BOUNDING BOX--\n" + this + "\nbb:
" + "\ntx1 = "+tx1+"; tx2 = "+tx2+"; ty1 = "+ty1+"; ty2 = "+ty2+"\na = "+a+"; b
= "+b+"; c = "+c);
if(tx1 < 0) tx1 = 0; else if(tx1 > 1) tx1 = 1;
if(tx2 < 0) tx2 = 0; else if(tx2 > 1) tx2 = 1;
if(ty1 < 0) ty1 = 0; else if(ty1 > 1) ty1 = 1;
if(ty2 < 0) ty2 = 0; else if(ty2 > 1) ty2 = 1;
float minX = this[(float)tx1].X;
float maxX = this[(float)tx2].X;
if(maxX < minX){ float temp = minX; minX = maxX; maxX =
temp; }
float minY = this[(float)ty1].Y;
float maxY = this[(float)ty2].Y;
if(maxY < minY){ float temp = minY; minY = maxY; maxY =
temp; }
// Make sure the nodes are inside
if(p1.X < minX) minX = p1.X; if(p1.X > maxX) maxX =
p1.X;
if(p2.X < minX) minX = p2.X; if(p2.X > maxX) maxX =
p2.X;
if(p1.Y < minY) minY = p1.Y; if(p1.Y > maxY) maxY =
p1.Y;
if(p2.Y < minY) minY = p2.Y; if(p2.Y > maxY) maxY =
p2.Y;
res.X = minX; res.Y = minY;
res.Width = maxX - minX; res.Height = maxY - minY;
Console.WriteLine("BB is "+res);
return res;
}
------------------------ Yahoo! Groups Sponsor --------------------~-->
<font face=arial size=-1><a
href="http://us.ard.yahoo.com/SIG=12h7ebbqi/M=362335.6886445.7839731.1510227/D=groups/S=1706030389:TM/Y=YAHOO/EXP=1124385915/A=2894361/R=0/SIG=13jmebhbo/*http://www.networkforgood.org/topics/education/digitaldivide/?source=YAHOO&cmpgn=GRP&RTP=http://groups.yahoo.com/";>In
low income neighborhoods, 84% do not own computers. At Network for Good, help
bridge the Digital Divide!</a>.</font>
--------------------------------------------------------------------~->
-----
To unsubscribe send a message to: [EMAIL PROTECTED]
-or-
visit http://groups.yahoo.com/group/svg-developers and click "edit my
membership"
----
Yahoo! Groups Links
<*> To visit your group on the web, go to:
http://groups.yahoo.com/group/svg-developers/
<*> To unsubscribe from this group, send an email to:
[EMAIL PROTECTED]
<*> Your use of Yahoo! Groups is subject to:
http://docs.yahoo.com/info/terms/
