""" Triangulation of a simple polygon.
"""

class Triangulate(object):
	'Triangulation class for a simple polygon'

	def __init__(self, data):
		""" data = Polygon class -- assume vertices cycle in
			clockwise order.
		"""
		self.data = polygon.clone
		self.convex = []
		self.concave = []
		self.triangulation = []

	def getCoordinate(self, vertex):
		return (vertex.x, vertex.y)

	def getTriangle(self, vertex):
		""" Returns triangle with vertex as the 'ear-tip'
		"""
		x = self.getCoordinate(vertex.previous)
		y = self.getCoordinate(vertex)
		z = self.getCoordinate(vertex.next)
		return (x,y,z)

	def getBarycentricCoordinate(self, triangle, point):
		""" http://en.wikipedia.org/wiki/Barycentric_coordinate_system
			if coordinates z_1, z_2, z_3 between 0 and 1 then they are
			inside triangle.  Equal to 1 or 0 and rest in [0,1] means
			on border of triangle.
		"""
		x_1, y_1 = triangle[0][0], triangle[0][1]
		x_2, y_2 = triangle[1][0], triangle[1][1]
		x_3, y_3 = triangle[2][0], triangle[2][1]
		x  , y   = point[0]	     , point[1]

		detT	 = (x_1 - x_3)*(y_2 - y_3) + (x_3 - x_2)*(y_1 - y_3)

		z_1  	 = ((y_2 - y_3)*(x - x_3) + (x_3 - x_2)*(y - y_3)) / detT
		z_2 	 = ((y_3 - y_1)*(x - x_3) + (x_1 - x_3)*(y - y_3)) / detT
		z_3  	 = 1.0 - z_1 - z_2
		return  (z_1, z_2, z_3)

	def checkPointIn(self, triangle, point):
		""" Using definition of Barycentric Coordinate System:
			if coordinates all in (0,1) then inside, else outside
			or on border.
		"""
		point_bbc = self.getBarycentricCoordinate(triangle, point)
		for i in point_bbc:
			if i <= 0.0 or i >= 1.0:
				return False
		return True

	def noConcaveIn(self, triangle):
		""" Checks self.concave for intersecting points.
			Returns True if no points are in triangle.
		"""
		for vertex_coord in self.concave:
			if self.checkPointIn(triangle, vertex_coord):
				return False
		return True

	def checkConvex(self, vertex):
		""" Checks if angle made by vertex.prev - vertex - vertex.next
			is convex relative to polygon.  Uses sign of triple product
			of vectors which gives orientation.  CCW = +, CW = -.
			If same orientation as cycling then convex, else concave.
			eg. If vertices are cycling clockwise and signed_area is
			negative then returns True.  Signed_area = 0 happens when
			triangle is degenerate.  Implemented for clockwise cycling.
		"""
		x = self.getCoordinate(vertex.previous)
		y = self.getCoordinate(vertex)
		z = self.getCoordinate(vertex.next)

		signed_area = (x[0]*y[1] + y[0]*z[1] + z[0]*x[1] -
						y[0]*x[1] - z[0]*y[1] - x[0]*z[1])

		return True if signed_area < 0 else False

	def getConvexConcave(self, vertex):
		""" Populates self.convex/self.concave
			using self.checkConvex
		"""
		if self.checkConvex(cursor):
			self.convex.append(self.getCoordinate(cursor))
		else:
			self.concave.append(self.getCoordinate(cursor))

	def populateConvexConcave(self):

		cursor = self.data.head		#Some initial vertex
		sentinel = cursor
		self.getConvexConcave(cursor)

		cursor = cursor.next
		while cursor != sentinel:
			self.getConvexConcave(cursor)
			cursor = cursor.next

	def findEar(self):
		""" Resets and populates self.convex/self.concave,
			checks triangles where the ear-tip is a convex
			vertex for intersection with any concave vert-
			ices.  If no intersection returns that ear.
		"""
		n = self.data.ngon
		cursor = self.data.head		#Some initial vertex

		if n == 3:
			triangle = self.getTriangle(cursor)
			return [triangle, cursor]

		self.convex = []
		self.concave = []
		self.populateConvexConcave()

		i = 0
		while i <= 2*n:
			if self.getCoordinate(cursor) in self.convex:
				triangle = self.getTriangle(cursor)
				if self.noConcaveIn(triangle):
					return [triangle, cursor]
			cursor = cursor.next
			i += 1
		raise Exception('Algorithm is bugged, this should not happen.')

	def triangulate(self):
		""" Finds an ear, documents and removes vertice from polygon,
			repeats until only a triangle is left and adds that to
			triangulation.
		"""
		while self.data.ngon > 3:
			ear = self.findEar()
			self.triangulation.append(ear[0])
			self.data.remove(ear[1])

		finalear = self.findEar()
		self.triangulation.append(ear[0])
		return self.triangulation