Sexy pixel generator for efficiently drawing ellipse (or circle) shapes, either outlined or filled.

gistfile1.py

def iter_ellipse_points(cx, cy, rx, ry, filled=False):
    """For details, refer to the John Kennedy paper on efficiently drawing the
    pixels of an ellipse: http://homepage.smc.edu/kennedy_john/belipse.pdf
    """
    assert rx > 0, 'Cannot compute ellipse points with zero radius.'
    assert ry > 0, 'Cannot compute ellipse points with zero radius.'

    # 2a2 and 2b2 are the 2*a^2 and 2*b^2 terms (constants)
    _2a2, _2b2 = 2 * rx * rx, 2 * ry * ry

    # This part calculates the first section of the first quadrant
    x, y = rx, 0
    dx, dy = ry * ry * (1 - 2 * rx), rx * rx
    err, stopx, stopy = 0, _2b2 * rx, 0
    while stopx >= stopy:
        for p in iter_plot4points(cx, cy, x, y): yield p
        if filled:
            for z in range(x):
                for p in iter_plot4points(cx, cy, z, y): yield p
        y += 1; stopy += _2a2; err += dy; dy += _2a2
        if 2 * err + dx > 0:
            x -= 1; stopx -= _2b2; err += dx; dx += _2b2

    ky = y

    # This part calculates the second section of the first quadrant
    # Together, they form the whole first quadrant
    x, y = 0, ry
    dx, dy = ry * ry, rx * rx * (1 - 2 * ry)
    err, stopx, stopy = 0, 0, _2a2 * ry
    while stopx <= stopy:
        for p in iter_plot4points(cx, cy, x, y): yield p
        if filled:
            for z in range(ky, y):
                for p in iter_plot4points(cx, cy, x, z): yield p
        x += 1; stopx += _2b2; err += dx; dx += _2b2
        if 2 * err + dy > 0:
            y -= 1; stopy -= _2a2; err += dy; dy += _2a2


def iter_plot4points(cx, cy, x, y):
    yield (cx + x, cy + y)
    if x != 0:
        yield (cx - x, cy + y)
    if y != 0:
        yield (cx + x, cy - y)
    if x != 0 and y != 0:
        yield (cx - x, cy - y)