Tuesday, June 16, 2009

How to calculate Bezier curves' bounding box

Hi, it is NISHIO Hirokazu. Today I wanted to make a lot of Bezier curves same size. And I got it.

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)`

Blaze Boy asked me about the structure, thank you. for each c in curves is 6-tuples: P1, P2, P3 = ((c[0], c[1]), (c[2], c[3]), (c[4], c[5])) P0 and P3 are terminal points of each bezier curves.