#24576 by Alexander Ross (Alexander)


import sys
import Image
from numpy import *

def save(a, name):
    a = a[:,:, newaxis]*255
    a = concatenate((a, a, a), 2)
    Image.fromarray(a).save(name)

def adjacent(x,y, img):
    c = -1
    for s,t in [(x-1, y-1), (x,y-1),
                (x+1, y-1), (x+1, y),
                (x+1, y+1), (x, y+1),
                (x-1, y+1), (x-1, y)]:
        if s < 0 or s >= img.shape[0] or t < 0 or t >= img.shape[1]:
            continue
        if img[s,t] == True:
            c+=1
    return c

def area_of(yx_1, yx_2, yx_3):
    y1, x1 = yx_1
    y2, x2 = yx_2
    y3, x3 = yx_3
    return 1/2. * abs(-x2*y1 + x3*y1 + x1*y2 - x3*y2 - x1*y3 + x2*y3)

def shapes_of(a):
    # return the seperate contiguous shapes of a.
    a = a.copy()
    while True:
        Y, X = a.nonzero()
        b = fill(a, (min(Y),min(X)), False)
        yield logical_xor(b, a)
        a = logical_xor(s,a)
        if not a.any():
            break

if __name__ == "__main__":
    i = Image.open(sys.argv[1])
    a = asarray(i)

    # get a minimal polygon bounding the shape in a.
    a = a[:,:,0].astype(bool)
    Y, X = a.nonzero()

    minx, maxx = min(X)-1, max(X)+2
    miny, maxy = min(Y)-1, max(Y)+2

    b = a[miny:maxy, minx:maxx]
    save(b, "b.png")
    Y, X = b.nonzero()
    YX= zip(Y,X)
    first = min(YX)
    x,y = first
    last = (-1,-1)
    buf = [(x,y)]
    # Traverse the shape in a clockwise manner, recording all
    # pixels as we go.
    not_done = True
    while not_done:
        adj = [(y-1, x-1), (y-1, x  ),
               (y-1, x+1), (y  , x+1),
               (y+1, x+1), (y+1, x  ),
               (y+1, x-1), (y  , x-1)]
        adj = [(s,t) for s,t in adj if b[s,t] == True]
        scores = [adjacent(s,t, b) for s,t in adj]
        t = sorted([(scr, st) for scr, st in zip(scores,adj)])
        adj = [st for scr, st in t if scr < 6]
        for s,t in adj:
            if (s,t) not in YX:               
                continue
            elif (s,t) not in buf:
                buf.append((s,t))
                y,x = s,t
                break
        if (y,x) == last:
            break
        if (y,x) == first:
            break
        last = (y,x)

    c = zeros(b.shape).astype(bool)
    for y,x in buf:
        c[y,x] = True

    save(c, "c.png")

    # simplify polygon
    min_area = 0.25
    i = 0
    while True:
        j,k,m = i, i+1, i+2
        if area_of(buf[j], buf[k], buf[m]) < min_area:
            del buf[k]
            i = 0
            continue
        else:
            i+=1
        if i+2 >= len(buf):
            break

    html = file("c.html", 'w')
    html.write("<html><body>\n<map name='#c'>")
    html.write("<area shape='poly' href='www.google.com' coords=\"")
    html.write(", ".join("%i,%i" % (x,y) for y,x in buf))
    html.write("\">\n</map><img src='c.png', usemap='#c'></body></html>")
    html.close()
    save(c, "c.png")