clustering.py

import random

from math import sqrt

location = [(random.randint(0,10), random.randint(0,10))
            for i in xrange(20)]

location = set(location)

def distanza(first, second):
    ax, ay = first
    bx, by = second
    return sqrt((ax-bx)**2 + (ay-by)**2)

def punto_medio(first, second):
    ax, ay = first
    bx, by = second
    return [(ax+bx) / 2.0, (ay+by) / 2.0]

def find_closer(fields):
    return sorted([[ [x,y], distanza(x,y)]
                   for x in fields
                      for y in fields if x != y],
                  key = lambda x: x[1])
    
def find_farest(fields):
    farest = find_closer(fields)
    farest.reverse()
    return farest

def find_closer_to(point, fields):
    return sorted([[x, distanza(point,x)]
                   for x in fields],
                  key = lambda x: x[1])

def averange_midle(location):
    avg_x = 0.0
    avg_y = 0.0
    for h in location:
        avg_x += h[0]
        avg_y += h[1]
    return (avg_x/len(location), avg_y/len(location))
    
def print_map(location, bomb = False):
    if bomb:
        bomb = [(int(x[0]), int(x[1])) for x in bomb]
        print bomb
    for x in xrange(11):
        for y in xrange(11):
            if (x,y) in location:
                print "a",
            elif (x,y) in bomb:
                print "X",
            else: print "_",
        print
    return

def cluster(l):
    location = l.copy()
    cluster1 , cluster2 = find_farest(location)[0][0]
    location.remove(cluster1)
    location.remove(cluster2)
    cluster1 = [cluster1]
    cluster2 = [cluster2]
    while(location):
        closer_to_1 = find_closer_to(averange_midle(cluster1), location)[0]
        closer_to_2 = find_closer_to(averange_midle(cluster2), location)[0]
        if closer_to_1[1] <= closer_to_2[1]:
            cluster1.append(closer_to_1[0])
            location.remove(closer_to_1[0])
        else:
            cluster2.append(closer_to_2[0])
            location.remove(closer_to_2[0])
    return averange_midle(cluster1), averange_midle(cluster2)


def run():
    bomb = cluster(location)
    print bomb
    print_map(location, bomb)