bezier bounding box

bounds.py

# http://stackoverflow.com/questions/2587751/an-algorithm-to-find-bounding-box-of-closed-bezier-curves

from __future__ import division
import math

def getBoundsOfCurve(x0, y0, x1, y1, x2, y2, x3, y3):
    tvalues = []
    bounds = [[], []]
    points = []

    for i in range(2):
        if i:
            b = 6 * y0 - 12 * y1 + 6 * y2
            a = -3 * y0 + 9 * y1 - 9 * y2 + 3 * y3
            c = 3 * y1 - 3 * y0
        else:
            b = 6 * x0 - 12 * x1 + 6 * x2
            a = -3 * x0 + 9 * x1 -9 * x2 + 3 * x3
            c = 3 * x1 - 3 * x0
        if abs(a) < 0.000001:
            if abs(b) < 0.000001:
                continue
            t = -c / b
            if 0 < t < 1:
                tvalues.append(t)
            continue
        b2ac = b * b - 4 * c * a
        if b2ac < 0:
            continue
        sqrtb2ac = math.sqrt(b2ac)
        t1 = (-b + sqrtb2ac) / (2 * a)
        if 0 < t1 < 1:
            tvalues.append(t1)
        t2 = (-b - sqrtb2ac) / (2 * a)
        if 0 < t2 < 1:
            tvaleus.append(t2)

    j = jlen = len(tvalues)
    while j:
        j -= 1

        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].append(x)

        y = (mt * mt * mt * y0) + (3 * mt * mt * t * y1) + (3 * mt * t * t * y2) + (t * t * t * y3)
        bounds[1].append(y)
        points.append({"X":x, "Y":y})


    tvalues.append(0)
    tvalues.append(1)
    points.append({"X":x0, "Y":y0})
    points.append({"X":x3, "Y":y3})

    bounds[0].append(x0)
    bounds[1].append(y0)
    bounds[0].append(x3)
    bounds[1].append(y3)

    return {
        "left": min(bounds[0]),
        "top": min(bounds[1]),
        "right": max(bounds[0]),
        "bottom": max(bounds[1]),
        "points": points,
        "tvalues": tvalues
    }

# test
bounds = getBoundsOfCurve(532,333,117,305,28,93,265,42)
print bounds
#expected:
# {"left": 135.77684049079755, "top":42, "right":532, "bottom":333, "points":[{"X":135.77684049079755, "Y":144.86387466397255},{"X":532, "Y":333},{"X":265, "Y":42}],"tvalue":[0.6365030674846626,0,1]}