2009-06-16

How to calculate Bezier curves' bounding box

This entry was moved to NISHIO Hirokazu's blog

5 comments:

Blaze Boy said...

i couldn't understand the source code , could you please comment it ? ,
or give some explanation of the mathematical solution,
i'm making graphics application using python and i need this

my curve has the structure : [point,point,point....]

point = [handler,vertex,handler]
handler,vertex = (x,y)

could you help me ?

NISHIO Hirokazu said...

Almost same:

for c in curves:
P1, P2, P3 = (
(c[0], c[1]),
(c[2], c[3]),
(c[4], c[5]))

here, any c in curves are [handler, handler, point]
P0 and P3 are terminal points of each bezier curves.

NISHIO Hirokazu said...

sorry
s/point/vertex/g

ivek said...

This works fine for me when you have only one curve.


private List FindPointsForBounds(Point P0, Point P1, Point P2, Point P3)
{
List toReturn = new List();

int A = P3.X - 3 * P2.X + 3 * P1.X - P0.X;
int B = 3 * P2.X - 6 * P1.X + 3 * P0.X;
int C = 3 * P1.X - 3 * P0.X;
int D = P0.X;

int E = P3.Y - 3 * P2.Y + 3 * P1.Y - P0.Y;
int F = 3 * P2.Y - 6 * P1.Y + 3 * P0.Y;
int G = 3 * P1.Y - 3 * P0.Y;
int H = P0.Y;

float x, y;
float xMin = int.MaxValue;
float yMin = int.MaxValue;
float xMax = 0;
float yMax = 0;

for (float t = 0.0f; t <= 1.0f; t += 0.01f)
{
x = A * t * t * t + B * t * t + C * t + D;
if (x < xMin)
xMin = x;
if (x > xMax)
xMax = x;
y = E * t * t * t + F * t * t + G * t + H;
if (y < yMin)
yMin = y;
if (y > yMax)
yMax = y;
}
toReturn.Add(new Point((int)xMin, (int)yMin));
toReturn.Add(new Point((int)xMax, (int)yMax));
return toReturn;
}

jan said...

Thank you very much for this algorithm, it helped me a lot!