Sort shuffled circle points in clockwise order

clockwise-sort.py

import matplotlib
matplotlib.use('TKAgg')
import matplotlib.pyplot as plt
import numpy as np
import math
import random

def circlePoints(sides, length=1):
	angle = 0
	angleInc = 2*math.pi / sides
	result = []
	for i in range(sides):
		result.append([math.cos(angle) * length, math.sin(angle) * length])
		angle -= angleInc
	return result	

def leftMostPoint(points):
	return min(points, key=lambda p: p[0])

def topMostPoint(points):
	return max(points, key=lambda p: p[1])

def mean(l):
	return sum(l) / len(l)

def averageVertices(points):
	avgX = mean(map(lambda p: p[0], points))
	avgY = mean(map(lambda p: p[1], points))
	return [avgX, avgY]

def computeAngle(p1, p2, p3):
	alpha = math.atan2(p2[1] - p1[1], p2[0] - p1[0])
	beta  = math.atan2(p3[1] - p1[1], p3[0] - p1[0])
	r = alpha - beta	
	if r < 0: return r + 2*math.pi
	else: return r

def printAngles(points):
	cp = averageVertices(points)
	size = len(points)
	for i in range(size):
		print math.degrees(computeAngle(cp, points[0], points[(i+1) % size]))

def minhaIdeiaSort(points):
	cp = averageVertices(points)
	top = topMostPoint(points)
	points.remove(top)
	current = top
	sorted = [current]	
	while len(points) > 0:
		minAngle = math.pi * 2
		minAngleIndex = -1
		for i in range(len(points)):
			candidate = points[i]
			angle = computeAngle(cp, current, candidate)
			if (angle < minAngle):
				# new min angle
				minAngle = angle
				minAngleIndex = i
		current = points[minAngleIndex]
		points.remove(current)
		sorted.append(current)
	return sorted

allPoints = circlePoints(16)
random.shuffle(allPoints)
allPoints = minhaIdeiaSort(allPoints)
points = np.array(allPoints)
x, y = points.T
plt.scatter(x, y)

for i, p in enumerate(allPoints):
	plt.annotate(i, (x[i], y[i]))

plt.show()