from math import sqrt

OPEN = 0
OUTLINE = 1
FILLED = 2
OUTLINEFILLED = 3

class VectorShapeException(Exception):
	pass

class VectorShape:
	"""
		Defines a generic two dimensional polygon with a color and an outline color and some geometry methods.
		The class of the points can be something other than the default 'list' such as euclid.py's vector2 or something.
		Set the pointClass variable to something other than 'list' for that behaviour.
		points is a set of points which will be automatically cast to pointClass.
		sprite is the parent of this vector shape and defaults to None.
		
		>>> v = VectorShape([(0, 0), (0.5, 0.5)])
		>>> v.AddPoint((0.5, 0))
		>>> v.points
		[[0, 0], [0.5, 0], [0.5, 0.5]]
		>>> v[0]
		[0, 0]
		>>> v[1]
		[0.5, 0]
		>>> v[2]
		[0.5, 0.5]
		>>> v.PointIn((0.7, 0.25))
		False
		>>> v.PointIn((0.25, 0.25))
		True
		>>> v.CloseToLine((0.26, 0.26))
		True
		>>> v.CloseToLine((0.6, 0.6))
		False
		>>> v.IntersectLine([(1.0, 1.0), (1.0, 2.0)])
		[]
		>>> v.IntersectLine([(0.4, 0.1), (0.6, 0.3)])
		[(0.5, 0.20000000000000001)]
		>>> v.IntersectLine([(0, 0.5), (0.25, 0.25)])
		[(0.25, 0.25)]
		>>> v.IntersectLine([(0, 0.25), (1, 0.25)])
		[(0.5, 0.25), (0.25, 0.25)]
		>>> v.IntersectLine([(0, 0), (0.5, 0.5)])
		[(0.0, 0.0), (0.5, 0.5)]
		>>> v.IntersectLine([(0.5, 0.5), (0, 0)])
		[(0.0, 0.0), (0.5, 0.5)]
		>>> v.IntersectLine([(0, 0.1), (0.5, 0.6)])
		[]
		>>> v.IntersectPolygon(VectorShape([(0, 0.25), (1, 0.25), (1, 1.0)]))
		[(0.5, 0.25), (0.25, 0.25)]
		>>> v.IntersectPolygon(VectorShape([(0.25, 0.2), (1, 0.25), (0, 0.26)]))
		[(0.5, 0.21666666666666667), (0.5, 0.255), (0.25742574257425743, 0.25742574257425743), (0.20967741935483872, 0.20967741935483872)]
		>>> v.IntersectPolygon(VectorShape([(0, 0.1), (0, 0.5), (0.4, 0.5)]))
		[]
	"""
	pointClass = list
	
	def __init__(self, points, sprite=None):
		self.points = [self.pointClass(p) for p in points]
		self.status = OUTLINE
		self.sprite = sprite
		self.color = [255, 255, 255]
		self.outlineColor = [0, 0, 0]
	
	def __getitem__(self, idx):
		return self.points[idx]
	
	def AddPoint(self, point, index = -1):
		self.points.insert(index, self.pointClass(point))
	
	def Draw(self):
		"""
		draw a polygon if filled
		a line around it if outline is true
		should be a closed line if closed
		draw circles for selected
		"""
		pts = self.points[:] # [tuple([point * zoom for point in p]) for p in self.points]
		
		if self.status:
			pts.append(pts[0])
		
		if self.status & FILLED:
			self.DrawPolygon(pts, self.color)
		
		if self.status & OUTLINE or not self.status:
			self.DrawLine(pts, self.outlineColor)
	
	def DrawPolygon(self, points, color):
		raise VectorShapeException("No DrawPolygon Method")
	
	def DrawLine(self, points, color):
		raise VectorShapeException("No DrawLine Method")
	
	###
	###	Geometry stuff
	###
	def PointIn(self, pos):
		"""
		This code is patterned after [Franklin, 2000]
		http://www.geometryalgorithms.com/Archive/algorithm_0103/algorithm_0103.htm
		Tells us if the point is in this polygon
		"""
		cn = 0	# the crossing number counter
		pts = self.points[:]
		pts.append(self.points[0])
		for i in range(len(pts) - 1):
			if (((pts[i][1] <= pos[1]) and (pts[i+1][1] > pos[1])) or ((pts[i][1] > pos[1]) and (pts[i+1][1] <= pos[1]))):
				if (pos[0] < pts[i][0] + float(pos[1] - pts[i][1]) / (pts[i+1][1] - pts[i][1]) * (pts[i+1][0] - pts[i][0])):
					cn += 1
		return bool(cn % 2)
	
	def CloseToLine(self, pos, detectDistance=0.01):
		"""
		Is the given point close to the line?
		"""
		def p2s( a, b, p ):
			"""
			Yanked from:
			http://onezstudio.blogspot.com/2007/11/code-distance-from-point-to-line.html
			"""
			dX = b[0] - a[0]
			dY = b[1] - a[1]
			segmentLen = sqrt( dX * dX + dY * dY )
			halfLen = segmentLen / 2
		 	
			pX = p[0] - a[0]
			pY = p[1] - a[1]
			if segmentLen < 1E-6:
				return sqrt( pX * pX + pY * pY )
		 	
			newX = abs( ( pX * dX + pY * dY ) / segmentLen - halfLen )
			newY = abs( - pX * dY + pY * dX ) / segmentLen
		 	
			if newX > halfLen:
				newX = newX - halfLen
				return sqrt( newX * newX + newY * newY )
			else:
				return newY
		
		pts = self.points[:]
		pts.append(self.points[0])
		for i in range(len(pts) - 1):
			if p2s(pts[i], pts[i+1], pos) < detectDistance:
				return True
		return False
	
	def IntersectLineLine(self, line1, line2):
		"""
		Detects the intersection of two lines
		http://www.kevlindev.com/gui/math/intersection/Intersection.js
		"""
		a1, a2 = line1
		b1, b2 = line2
		a1x = a1[0]
		a1y = a1[1]
		a2x = a2[0]
		a2y = a2[1]
		b1x = b1[0]
		b1y = b1[1]
		b2x = b2[0]
		b2y = b2[1]
		
		ua_t = (b2x - b1x) * (a1y - b1y) - (b2y - b1y) * (a1x - b1x)
		ub_t = (a2x - a1x) * (a1y - b1y) - (a2y - a1y) * (a1x - b1x)
		u_b  = (b2y - b1y) * (a2x - a1x) - (b2x - b1x) * (a2y - a1y)
		
		if u_b:
			ua = ua_t / u_b
			ub = ub_t / u_b
			
			if 0 <= ua and ua <= 1 and 0 <= ub and ub <= 1:
				# intersection
				return [(a1x + ua * (a2x - a1x), a1y + ua * (a2y - a1y))]
			else:
				return []
		else:
			if ua_t == 0 or ub_t == 0:
				# coincident
				#return [line2]
				#this will be caught elsewhere anyway
				return []
			else:
				# parallel
				return []
	
	def IntersectLine(self, line):
		"""
			Detects the intersection of a polygon and a line
			http://www.kevlindev.com/gui/math/intersection/Intersection.js
		"""
		length = len(self.points)
		return sum([self.IntersectLineLine(line, (self[p], self[(p + 1) % length])) for p in xrange(length)], [])
	
	def IntersectPolygon(self, poly2):
		"""
			Detects the intersection of two polygons
			http://www.kevlindev.com/gui/math/intersection/Intersection.js
		"""
		length = len(poly2.points)
		return sum([self.IntersectLine((poly2[p], poly2[(p + 1) % length])) for p in xrange(length)], [])

def _test():
    import doctest
    doctest.testmod()

if __name__ == "__main__":
    _test()