Skip to content

Instantly share code, notes, and snippets.

@juliomarcos
Last active July 15, 2019 19:02
Show Gist options
  • Save juliomarcos/03f5599794adafcfbe7ffaea12627292 to your computer and use it in GitHub Desktop.
Save juliomarcos/03f5599794adafcfbe7ffaea12627292 to your computer and use it in GitHub Desktop.
Sort shuffled circle points in clockwise order
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()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment