from __future__ import division
import math
import random
from matplotlib import pyplot as plt
import numpy as np

def intersectLC((x1,y1),(x2,y2), (o1,o2),r):

	#translate everything to (0,0)
	x1 = x1-o1
	y1 = y1-o2
	x2 = x2-o1
	y2 = y2-o2

	d_x = x2-x1
	d_y = y2-y1

	d_r = math.sqrt(math.pow(d_x,2)+math.pow(d_y,2))

	D = x1*y2 - x2*y1

	delta = math.pow(r,2)*math.pow(d_r,2) - math.pow(D,2)

	if delta<=0:
		print "FALSE"
		return False, []
	else:
		p1_x = (D*d_y + sgn(d_y)*d_x*math.sqrt(math.pow(r,2)*math.pow(d_r,2)-math.pow(D,2)))/math.pow(d_r,2)+o1
		p1_y = (-D*d_x + abs(d_y)*math.sqrt(math.pow(r,2)*math.pow(d_r,2)-math.pow(D,2)))/math.pow(d_r,2)+o2
		p2_x = (D*d_y - sgn(d_y)*d_x*math.sqrt(math.pow(r,2)*math.pow(d_r,2)-math.pow(D,2)))/math.pow(d_r,2)+o1
		p2_y = (-D*d_x - abs(d_y)*math.sqrt(math.pow(r,2)*math.pow(d_r,2)-math.pow(D,2)))/math.pow(d_r,2)+o2
		x1 = x1+o1
		y1 = y1+o2
		x2 = x2+o1
		y2 = y2+o2
		plt.subplot(121)
		plt.scatter([p1_x,p2_x],[p1_y,p2_y])

		point = [(p1_x,p1_y),(p2_x,p2_y)]

		# if random.random()<=0.5:
		# 	point = [(p2_x,p2_y),(p1_x,p1_y)]

		print point

		return True, point

def getAngle((x,y), (o1,o2)):

	x = x - o1
	y = y - o2

	theta = math.atan(abs(y/x))

	if x>=0 and y>=0:
		print theta, math.degrees(theta)
		return theta
		#return math.degrees(theta)
	if x<=0 and y>=0:
		print math.pi-theta, math.degrees(math.pi-theta)
		return math.pi-theta
		#return math.degrees(math.pi-theta)
	if x<=0 and y<=0:
		print math.pi+theta, math.degrees(math.pi+theta)
		return math.pi+theta
		#return math.degrees(math.pi+theta)
	if x>=0 and y<=0:
		print 2*math.pi-theta, math.degrees(2*math.pi-theta)
		return 2*math.pi-theta
		#return math.degrees(2*math.pi-theta)

def sgn(x):

	if x<0: return -1
	else: return 1

def chooseSegmentsRandom(n, N):

	segments = []

	plt.subplot(121)
	plt.axis('equal')

	an = np.linspace(0, 2*np.pi, 100)
	plt.plot(15*np.cos(an), 15*np.sin(an))

	for i in xrange(0,n):
		segment = [(random.random()*2*N-N,random.random()*2*N-N),(random.random()*2*N-N,random.random()*2*N-N)]
		segments.append(segment)
		plt.plot([segment[0][0], segment[1][0]], [segment[0][1], segment[1][1]])

	return segments

def chooseSegmentsClusters(n, N):

	segments = []

	plt.subplot(121)
	plt.axis('equal')

	an = np.linspace(0, 2*np.pi, 100)
	plt.plot(15*np.cos(an), 15*np.sin(an))

	for i in xrange(0,int(n/4)):
		segment = [(random.random()*2+5,random.random()*2-6),(random.random()*2+5,random.random()*2+6)]
		segments.append(segment)
		plt.plot([segment[0][0], segment[1][0]], [segment[0][1], segment[1][1]], color = 'r')

	for i in xrange(0,int(n/4)):
		segment = [(random.random()*4,random.random()*2-3),(random.random()*4-2,random.random()*2+3)]
		segments.append(segment)
		plt.plot([segment[0][0], segment[1][0]], [segment[0][1], segment[1][1]], color = 'b')


	for i in xrange(0,int(n/4)):
		segment = [(random.random()*2-6,random.random()*1),(random.random()*2+6, random.random()*1)]
		segments.append(segment)
		plt.plot([segment[0][0], segment[1][0]], [segment[0][1], segment[1][1]], color = 'g')

	for i in xrange(0,int(n/4)):
		segment = [(random.random()*2-6,random.random()*1-7),(random.random()*2+6, random.random()*1-5)]
		segments.append(segment)
		plt.plot([segment[0][0], segment[1][0]], [segment[0][1], segment[1][1]], color = 'y')

	plt.show()

	return segments

def chooseSegmentsIntersection(n, N, a,b):

	segments = []

	plt.subplot(121)
	plt.axis('equal')

	an = np.linspace(0, 2*np.pi, 100)
	plt.plot(15*np.cos(an), 15*np.sin(an))

	for i in xrange(0,n):
		x1 = 1
		x2 = 1
		while math.pow(x1,2) + math.pow(x2,2)>=1:
			x1 = random.random()*2 - 1
			x2 = random.random()*2 - 1
		x = 5*(math.pow(x1,2)-math.pow(x2,2))/(math.pow(x1,2)+math.pow(x2,2))
		y = 5*(2*x1*x2)/(math.pow(x1,2)+math.pow(x2,2))
		segment = [(a,b),((x+a),(y+b))]
		segments.append(segment)
		plt.plot([segment[0][0], segment[1][0]], [segment[0][1], segment[1][1]])

	return segments

def findAngles(segments, o, r):

	plt.axis('equal')

	i = 0

	angles = []

	for segment in segments:
		print segment
		b, p = intersectLC(segment[0], segment[1], o, r)
		if b:
			plt.subplot(122)
			a1 = getAngle(p[0],o)
			a2 = getAngle(p[1],o)
			plt.scatter(a1,a2, color = 'r')
			angles.append([a1,a2])
			# if i<int(100/4):
			# 	plt.scatter(getAngle(p[0],o), getAngle(p[1],o), color = 'r')
			# else:
			# 	if i<2*int(100/4):
			# 		plt.scatter(getAngle(p[0],o), getAngle(p[1],o), color = 'b')
			# 	else:
			# 		if i<3*int(100/4):
			# 			plt.scatter(getAngle(p[0],o), getAngle(p[1],o), color = 'g')
			# 		else:
			# 			plt.scatter(getAngle(p[0],o), getAngle(p[1],o), color = 'y')

		i+=1

	plt.show()
	return angles

def torus_distance((x1,y1),(x2,y2)):

	return math.sqrt(math.pow(min(abs(x1-x2), 2*math.pi - abs(x1-x2)),2)+math.pow(min(abs(y1-y2), 2*math.pi - abs(y1-y2)),2))


def kMeans(X, K, maxIters = 10, plot_progress = None):

    centroids = X[np.random.choice(np.arange(len(X)), K), :]
    for i in range(maxIters):
        # Cluster Assignment step
        C = np.array([np.argmin([np.dot(x_i-y_k, x_i-y_k) for y_k in centroids]) for x_i in X])
        # Move centroids step
        centroids = [X[C == k].mean(axis = 0) for k in range(K)]
        if plot_progress != None: plot_progress(X, C, np.array(centroids))
    return np.array(centroids) , C

#centroids, C = kMeans(np.array([(0,-1),(0,0),(0,1),(0,2)]),3)
#print centroids
#print C

# segments = []
# segments.extend(chooseSegmentsIntersection(100,2,0,0))
# segments.extend(chooseSegmentsIntersection(100,2,-7.5,0))
# segments.extend(chooseSegmentsIntersection(100,2,5,0))
# segments.extend(chooseSegmentsIntersection(100,2,-5,0))
# segments.extend(chooseSegmentsIntersection(100,2,7.5,0))
# segments.extend(chooseSegmentsIntersection(100,2,-7.5,0))
# segments.extend(chooseSegmentsIntersection(100,2,10,0))
# segments.extend(chooseSegmentsIntersection(100,2,-10,0))

# findAngles(segments, (0,0), 15)