ベジェ曲線の最大/最小値

2019/01/14

Python2.7.8

３次ベジェ曲線の最大・最小値の取得

# -*- coding: utf-8 -*-

def bezier_box(p0,p1,p2,p3):
    bounds = [[],[]]
    bounds[0] += [p0[0],p3[0]]
    bounds[1] += [p0[1],p3[1]]

    for i in [0,1]:
        a = float(-3 * p0[i] +  9 * p1[i] - 9 * p2[i] + 3 * p3[i])
        b = float( 6 * p0[i] - 12 * p1[i] + 6 * p2[i])
        c = float( 3 * p1[i] -  3 * p0[i])
        if a == 0:
            if b == 0: continue
            tlist = [-c / b]
        else:
            tlist = quadratic_equation(a,b,c)
        for t in tlist:
            if 0 < t < 1: 
                v = (1-t)**3*p0[i] + 3*(1-t)**2*t*p1[i] + 3*(1-t)*t**2*p2[i] + t**3*p3[i]
                bounds[i].append(v)

    return [min(bounds[0]),min(bounds[1]),
            max(bounds[0]),max(bounds[1])]

def quadratic_equation(a,b,c):
    d = b*b-4*a*c
    if d < 0:
        return []
    if d == 0:
        x = -b/(2.0*a)
        return [x]
    else:
        x0 = (-b+d**0.5)/(2.0*a)
        x1 = (-b-d**0.5)/(2.0*a)
    return [x0,x1]

def bezier_curve(p0,p1,p2,p3,n=20):
    p0_x,p0_y = p0
    p1_x,p1_y = p1
    p2_x,p2_y = p2
    p3_x,p3_y = p3
    points = []
    for i in range(n+1):
        t = i/float(n)
        p_x = (1-t)**3*p0_x + 3*(1-t)**2*t*p1_x + 3*(1-t)*t**2*p2_x + t**3*p3_x
        p_y = (1-t)**3*p0_y + 3*(1-t)**2*t*p1_y + 3*(1-t)*t**2*p2_y + t**3*p3_y
        points.append([p_x,p_y])
    return points

def main():
    import Tkinter
    window = Tkinter.Tk()
    canvas = Tkinter.Canvas(window,width=300,height=200)
    canvas.pack() 

    points = [[20,60],[120,10],[290,190],[220,140]]
    box = bezier_box(*points)

    r = 3
    for p in [points]:
        for i in range(4):
            canvas.create_oval(p[i][0]-r,p[i][1]-r,
                               p[i][0]+r,p[i][1]+r)
        canvas.create_line(p[0][0],p[0][1],p[1][0],p[1][1])
        canvas.create_line(p[2][0],p[2][1],p[3][0],p[3][1])

    canvas.create_line(bezier_curve(*points))
    canvas.create_line(box[0],box[1],box[0],box[3],fill='red')
    canvas.create_line(box[2],box[1],box[2],box[3],fill='red')
    canvas.create_line(box[0],box[1],box[2],box[1],fill='red')
    canvas.create_line(box[0],box[3],box[2],box[3],fill='red')

    window.mainloop()
    return

if __name__ == '__main__':
    main()

ベジエ曲線のバウンディングボックス
http://d.hatena.ne.jp/nishiohirokazu/20090616/1245104751