Here is what I want to draw:
To calculate bounding box of cubic Bezier seems easy, especially you know its parametric form. See Bézier curve - Wikipedia, the free encyclopedia
However, there are some pitfall. The derivative of Bezier equation is usually quadratic equation but not always. Solutions of the derivative may out of range, etc.
I publish following source code under MIT License. Feel free to use it.
def calc_box(start, curves):
P0 = start
bounds = [[P0[0]], [P0[1]]]
for c in curves:
P1, P2, P3 = (
(c[0], c[1]),
(c[2], c[3]),
(c[4], c[5]))
bounds[0].append(P3[0])
bounds[1].append(P3[1])
for i in [0, 1]:
f = lambda t: (
(1-t)**3 * P0[i]
+ 3 * (1-t)**2 * t * P1[i]
+ 3 * (1-t) * t**2 * P2[i]
+ t**3 * P3[i])
b = 6 * P0[i] - 12 * P1[i] + 6 * P2[i]
a = -3 * P0[i] + 9 * P1[i] - 9 * P2[i] + 3 * P3[i]
c = 3 * P1[i] - 3 * P0[i]
if a == 0:
if b == 0:
continue
t = -c / b
if 0 < t < 1:
bounds[i].append(f(t))
continue
b2ac = b ** 2 - 4 * c * a
if b2ac < 0:
continue
t1 = (-b + sqrt(b2ac))/(2 * a)
if 0 < t1 < 1: bounds[i].append(f(t1))
t2 = (-b - sqrt(b2ac))/(2 * a)
if 0 < t2 < 1: bounds[i].append(f(t2))
P0 = P3
x = min(bounds[0])
w = max(bounds[0]) - x
y = min(bounds[1])
h = max(bounds[1]) - y
return (x, y, w, h)
Want to know more about me? Please visit http://www.nishiohirokazu.org/
Posts
5 Comments:
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 ?
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.
sorry
s/point/vertex/g
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;
}
Thank you very much for this algorithm, it helped me a lot!
Post a Comment