G-code generator for plotting a Sierpinski triangle without lifting the tool

sierpinski_eulerian_plotter.py

#!/usr/bin/env python3


'''
Generate G-code for drawing a Sierpenski triangle, using lines,
only drawing each line once, and never lifting the tool.

This is achieved drawing along an Eulerian cycle
'''


# these commands are for an eleksdraw plotter
# you will need to modify them to fit your machine!
prolog = '''
(mm mode)
G21
(absolute positioning)
G90
(feed rate)
F800
(lift pen)
M03 S0
(travel to the starting position)
G00 X{:.4f} Y{:.4f}
(lower pen)
M03 S50
(start drawing!)
'''

draw_move_template = 'G01 X{:.4f} Y{:.4f}'

epilog = '''
(drawing done)
(lift pen)
M03 S0
(done)
'''


def midpoint(p1, p2):
    return((p1[0]+p2[0])/2, (p1[1]+p2[1])/2)


def draw_piece(a, b, c, levels):
    '''Draw a region of a sierpienski triangle using lines

    levels is how much deeper should we draw'''
    edges = []
    if levels > 0:
        ab = midpoint(a, b)
        ac = midpoint(a, c)
        bc = midpoint(b, c)
        edges += draw_piece(a, ab, ac, levels - 1)
        edges += draw_piece(ab, b, bc, levels - 1)
        edges += draw_piece(ac, bc, c, levels - 1)
    else:
        edges = [(a, b), (b, c), (a, c)]
    return edges


def render_plot(path):
    '''display the path with matplotlib'''
    import matplotlib.pyplot as plt
    plt.figure()
    plt.subplot(1, 1, 1)
    plt.axis('off')

    last = None
    for p in path:
        if last is not None:
            plt.plot([last[0], p[0]], [last[1], p[1]])
        last = p

    plt.show()


def render_gcode(path):
    '''create g-code and print it to stdout'''
    first, *rest = path
    print(prolog.format(*first))
    for p in rest:
        print(draw_move_template.format(*p))
    print(epilog)


def get_edges(edges, p):
    '''list of edges point p is vertex of'''
    return [edge for edge in edges if p in edge]


def find_eulerian_cycle(edges, start_point):
    '''sort points to create an Eulerian cycle

    NOTE: this only works for our Sierpenski triangle!'''
    path = [start_point]
    curr = start_point

    # basic algo:
    # take the first unvisited edge connected in this order:
    #   1) south-west
    #   2) north-west
    #   3) east
    # mark the edge as visited, and set its other endpoint as the next point
    while edges:
        best = None
        best_score = 0
        for edge in get_edges(edges, curr):
            other = edge[0]
            score = 1
            if other == curr:
                other = edge[1]
            if other[0] < curr[0] and other[1] < curr[1]:
                # SW
                # best choice, don't look further
                best = edge
                break
            elif other[0] < curr[0] and other[1] > curr[1]:
                # NW
                score = 3
            if score > best_score:
                best = edge
                best_score = score
        edges.remove(best)
        # the other point of the selected edge
        if curr == best[0]:
            curr = best[1]
        else:
            curr = best[0]
        path.append(curr)
    return path


def main():
    import argparse

    parser = argparse.ArgumentParser(
            formatter_class=argparse.ArgumentDefaultsHelpFormatter)
    parser.add_argument('--display', action='store_true')
    parser.add_argument('--limit', type=int, default=0)
    parser.add_argument('--width', type=int, default=100)
    parser.add_argument('--level', type=int, default=5)

    args = parser.parse_args()

    width = args.width
    a = (width / 2, width * (3 ** 0.5) / 2)
    b = (0, 0)
    c = (width, 0)
    edges = draw_piece(a, b, c, args.level)
    path = find_eulerian_cycle(edges, b)

    if args.limit != 0:
        path = path[:args.limit]

    if args.display:
        render_plot(path)
    render_gcode(path)

    return 0


if __name__ == '__main__':
    import sys
    sys.exit(main())