Draw a quadratic B-spline curve with TrueType control points

draw_quad_bspline_w_truetype_points.py

# coding: utf-8

from PIL import Image, ImageDraw
import math, sys
import time

STEP = 10000

# 9 cps ~ 8 segments
CPS1 = [(10, 10), (10, 990), (250, 500), (500, 990), (750, 500), (990, 990), (990, 10), (500, 500), (10, 10)]
# +2 cps
CPS2 = [(10, 10), (10, 500), (10, 990), (250, 500), (500, 990), (750, 500), (990, 990), (990, 500), (990, 10), (500, 500), (10, 10)]

# -> 12 knots
KNOTS1 = [STEP**0, STEP**0, STEP**0, STEP**1, STEP**2, 2*STEP**2, 3*STEP**2, 3*STEP**2, STEP**3, STEP**4, STEP**4, STEP**4]
# +2 knots
KNOTS2 = [0, 0, 0, 1, 1, 2, 3, 4, 4, 5, 5, 6, 6, 6] 

print(KNOTS1)

def bspline_basis(knots, n, i, t):
    if n<=0:
        return 1 if knots[i] <= t < knots[i+1] else 0
    # n>0
    # do not divide if bspline_basis==0
    b_i0 = bspline_basis(knots, n-1, i, t)
    b_i1 = bspline_basis(knots, n-1, i+1, t)
    left = (t - knots[i])/(knots[i+n] - knots [i]) * b_i0 if b_i0>0 else 0 
    right = (knots[i+n+1] - t) / (knots[i+n+1] - knots[i+1]) * b_i1 if b_i1>0 else 0
    return left + right

def draw_dot(draw, p, col=(0,0,0)):
    x = round(p[0])
    y = round(p[1])
    draw.point((x-1, y), col)
    draw.point((x, y), col)
    draw.point((x+1, y), col)
    draw.point((x, y-1), col)
    draw.point((x, y+1), col)

def draw_dots(draw, ps, col=(0,0,0)):
    for p in ps:
        draw_dot(draw, p, col)

def drawquadbspline(draw, cps, knots, col=(0,0,0)):
    """
    draws a quadratic B-spline curve
    draw: ImageDraw.Draw object
    cps: control points
    knots: knot vector
    col: color(r, g, b)
    """
    def draw_rec(begin, end):
        """
        begin, end: t (knots[2] <= t <= knots[len(cps)])
        """
        # calculate the point coordinates of begin and end
        p_begin_x = 0
        p_begin_y = 0
        p_end_x = 0
        p_end_y = 0
        for i in range(len(cps)):
            B_begin = bspline_basis(knots, 2, i, begin)
            p_begin_x += cps[i][0] * B_begin
            p_begin_y += cps[i][1] * B_begin
            B_end = bspline_basis(knots, 2, i, end)
            p_end_x += cps[i][0] * B_end
            p_end_y += cps[i][1] * B_end
        # draw the vertice corresponding to begin
        draw.point((round(p_begin_x), round(p_begin_y)), col)
        # if the distance of the vertices is far,
        # divide into 2 parts and draw recursively.
        if (p_begin_x - p_end_x)**2 + (p_begin_y - p_end_y)**2 > 1:
            half = (begin + end)/2
            draw_rec(begin, half)
            draw_rec(half, end)
    
    begin, end = knots[2], knots[len(cps)]
    
    #workaround :(
    #最初の点と最後の点が一致してる場合描画されなかったやつをとりあえず回避
    #曲線が交差などで重なる場合問題になる可能性がある
    half = (begin + end) / 2
    draw_rec(begin, half)
    draw_rec(half, end - end*sys.float_info.epsilon)

if __name__ == '__main__':
    width, height = 1000, 1000
    im = Image.new("RGB", (width, height), (255,255,255))
    draw = ImageDraw.Draw(im)
    
    draw.line(CPS1, (0, 255, 255))
    
    drawquadbspline(draw, CPS2, KNOTS2, (255, 0, 0))
    drawquadbspline(draw, CPS1, KNOTS1)
    
    #draw_dots(draw, CPS2, (255, 0, 0))
    draw_dots(draw, CPS1, (0, 0, 255))
    
    im.save("test.png")