# $Id$
# tkinter canvas-style line smoothing code

# taken from wckgraph

##
# Adds a bezier curve segment to the given list.
#
# @param out The output array.
# @param xy Bezier control points.
# @param steps Number of interpolation steps.

def addcurve(out, xy, steps):
    # from PIL's libImaging/Draw.c
    add = out.append
    for i in range(1, steps+1):
        t = float(i) / steps; t2 = t*t; t3 = t2*t
        u = 1.0 - t; u2 = u*u; u3 = u2*u
        add(xy[0]*u3 + 3*(xy[2]*t*u2 + xy[4]*t2*u) + xy[6]*t3)
        add(xy[1]*u3 + 3*(xy[3]*t*u2 + xy[5]*t2*u) + xy[7]*t3)


##
# Smoothes a polyline using parabolic splines.  This algorithm is based
# on the one used by the "smooth" option in Tkinter's Canvas widget.
#
# @param xy Coordinate array.
# @param steps Number of interpolation steps.
# @return A smooth and flattened coordinate array.

def smooth(xy, steps=12):
    # based on Tk's tkTrig.c
    # FIXME: return curves, and let the drawing code to the flattening
    if not xy:
        return xy
    closed = xy[0] == xy[-2] and xy[1] == xy[-1]
    out = []
    if closed:
        # connect end segment to first segment
        control = (
            0.500*xy[-4] + 0.500*xy[0],
            0.500*xy[-3] + 0.500*xy[1],
            0.167*xy[-4] + 0.833*xy[0],
            0.167*xy[-3] + 0.833*xy[1],
            0.833*xy[0]  + 0.167*xy[2],
            0.833*xy[1]  + 0.167*xy[3],
            0.500*xy[0]  + 0.500*xy[2],
            0.500*xy[1]  + 0.500*xy[3],
            )
        out = [control[0], control[1]]
        addcurve(out, control, steps)
    else:
        out = [xy[0], xy[1]]
    for i in range(0, len(xy)-4, 2):
        if i == 0 and not closed:
            control = (
                xy[i],
                xy[i+1],
                0.333*xy[i] + 0.667*xy[i+2],
                0.333*xy[i+1] + 0.667*xy[i+3],
                )
        else:
            control = (
                0.500*xy[i] + 0.500*xy[i+2],
                0.500*xy[i+1] + 0.500*xy[i+3],
                0.167*xy[i] + 0.833*xy[i+2],
                0.167*xy[i+1] + 0.833*xy[i+3],
                )
        if i == len(xy)-6 and not closed:
            control = control + (
                0.667*xy[i+2] + 0.333*xy[i+4],
                0.667*xy[i+3] + 0.333*xy[i+5],
                xy[i+4],
                xy[i+5],
                )
        else:
            control = control + (
                0.833*xy[i+2] + 0.167*xy[i+4],
                0.833*xy[i+3] + 0.167*xy[i+5],
                0.500*xy[i+2] + 0.500*xy[i+4],
                0.500*xy[i+3] + 0.500*xy[i+5],
                )
        if ((xy[i] == xy[i+2] and xy[i+1] == xy[i+3]) or
            (xy[i+2] == xy[i+4] and xy[i+3] == xy[i+5])):
            out.append(control[6])
            out.append(control[7])
        else:
            addcurve(out, control, steps)
    return out


if __name__ == "__main__":

    from Tkinter import *

    canvas = Canvas()
    canvas.pack()

    xy = [0, 0, 200, 100, 50, 200, 300, 300]

    canvas.create_line(xy, fill="red")
    canvas.move(canvas.create_line(xy, smooth=1, fill="green"), 0, 0)
    canvas.move(canvas.create_line(smooth(xy), fill="blue"), 0, 0)

    mainloop()