algorithm.py

def algorithm(points, k, cutoff):

    initial = random.sample(points, k)
    clusters = [Cluster([p]) for p in initial]
    loop_counter = 0
    while True:
        lists = [[] for c in clusters]
        cluster_count = len(clusters)
        loop_counter += 1

        for p in points:
            smallest_distance = get_distance(p, clusters[0].centroid)
            cluster_index = 0

            for i in range(cluster_count - 1):
                distance = get_distance(p, clusters[i + 1].centroid)
                if distance < smallest_distance:
                    smallest_distance = distance
                    cluster_index = i + 1
            lists[cluster_index].append(p)

        biggest_shift = 0.0

        for i in range(cluster_count):
            shift = clusters[i].update(lists[i])
            biggest_shift = max(biggest_shift, shift)

        if biggest_shift < cutoff:
            print "Converged after %s iterations" % loop_counter
            break

    return clusters