import PIL.Image as Image
import PIL.ImageDraw as ImageDraw
from scikits.delaunay import delaunay
import numpy
import math
import polygontools

print "Collecting point cloud...",
image = Image.open('output.png').convert('1')
step = 4
points_x = []
points_y = []
for y in range(0, image.size[1], step):
	for x in range(0, image.size[0], step):
		if image.getpixel((x, y)) != 0:
			points_x.append(x)
			points_y.append(y)

fpoints_x = numpy.array(points_x, dtype = 'float')
fpoints_y = numpy.array(points_y, dtype = 'float')
print "done"

print "Delaunay...",
circumcenters, edges, tri_points, tri_neighbours = delaunay(fpoints_x, fpoints_y)
print "done"

print "Filtering triangles...",
selected_triangles = set()
selected_points = set()
point_owners = {}
for tri_index, point_indexes in enumerate(tri_points):
	points = [(points_x[i], points_y[i]) for i in point_indexes]
	points.append(points[0])
	
	lengths = []
	for i in range(3):
		x1, y1 = points[i]
		x2, y2 = points[i + 1]
		lengths.append((x1 - x2) ** 2 + (y1 - y2) ** 2)
		
	avglength = math.sqrt(sum(lengths) / 3.)
	if avglength < 30:
		selected_triangles.add(tri_index)
	
print "done"

print "Traversing borders...", "regions",
d = polygontools.DelaunayData(selected_triangles, tri_points, tri_neighbours)
print "polygons",
polygons = d.traverse_all()
print "done"

print "Drawing output...",
output = Image.new('RGB', image.size)
draw = ImageDraw.Draw(output)
i = 0
for points in polygons:
    i += 1553
    color = (i % 255, (i >> 8) % 255, (i >> 16) % 128 + 128)

    points = [(points_x[i], points_y[i]) for i in points]
    points.append(points[0])

    draw.polygon(points, outline = color)
output.save('output3.png')

output = Image.new('RGB', image.size)
draw = ImageDraw.Draw(output)

i = 0
for region in d.allregions:
    i += 1553
    color = (i % 255, (i >> 8) % 255, (i >> 16) % 255)
    for triangle in region:
        points = [(points_x[i], points_y[i]) for i in d.tri_points[triangle]]
        points.append(points[0])

        draw.polygon(points, outline = (255,255,255), fill = color)
print "done"
	
output.save('output3b.png')