Draw a quadratic B-spline curve approximating a linear B-spline curve

draw_bspline_polyline.py

# coding: utf-8

from PIL import Image, ImageDraw
import math

STEP = 10000

# 14 cps ~ 13 segments
CPS = [(10, 10), (10, 990), (990, 990), (970, 10), (40, 70), (120, 970), (970, 820), (760, 40), (70, 280), (300, 910), (890, 670), (500, 160), (160, 500), (0, 0)]

# -> 16 knots
KNOTS = [STEP**i for i in range(len(CPS)+3)]
print(KNOTS)
KNOTS_LINEAR = list(range(len(KNOTS)))

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 drawlinearbspline(draw, cps, knots, col=(0,0,0)):
    """
    draws a linear 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[1] <= t <= knots[len(cps)])
        """
        
        # divide a curve into two recursively 
        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, 1, i, begin)
            p_begin_x += cps[i][0] * B_begin
            p_begin_y += cps[i][1] * B_begin
            B_end = bspline_basis(knots, 1, i, end)
            p_end_x += cps[i][0] * B_end
            p_end_y += cps[i][1] * B_end
        draw.point((round(p_begin_x), round(p_begin_y)), col)
        # if the distance of the vertices is far, 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[1], knots[len(cps)]
    draw_rec(begin, end)


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)]
    draw_rec(begin, end)

if __name__ == '__main__':
    width, height = 1000, 1000
    im = Image.new("RGB", (width, height), (255,255,255))
    draw = ImageDraw.Draw(im)
    
    #draw.line(CPS[:-1], (255, 0, 0), 1)
    drawlinearbspline(draw, CPS[:-1], KNOTS_LINEAR, (255, 0, 0))
    drawquadbspline(draw, CPS, KNOTS)
    
    im.save("r{}.png".format(STEP))