

# Given three colinear points p, q, r, the function checks if
# point q lies on line segment 'pr'
def onSegment (p, q, r):
	if min(p[0], r[0]) <= q[0] <= max(p[0], r[0]) and min(p[1], r[1]) <= q[1] <= max(p[1], r[1]):
		return True

	return False


# To find orientation of ordered triplet (p, q, r).
# The function returns following values
# 0 --> p, q and r are colinear
# 1 --> Clockwise
# 2 --> Counterclockwise
def orientation(p, q, r):

	# See https://www.geeksforgeeks.org/orientation-3-ordered-points/
	# for details of below formula.
	val = (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1])

	if val == 0: return 0 # colinear

	if val > 0: return 1 #clockwise

	return 2 #counterclocl wise


# The main function that returns True if line segment 'p1q1'
# and 'p2q2' intersect.
def doSegmentIntersect(p1, q1, p2, q2):
	# Find the four orientations needed for general and
	# special cases
	o1 = orientation(p1, q1, p2)
	o2 = orientation(p1, q1, q2)
	o3 = orientation(p2, q2, p1)
	o4 = orientation(p2, q2, q1)

	# General case
	if o1 != o2 and o3 != o4:
		return True

	# Special Cases
	# p1, q1 and p2 are colinear and p2 lies on segment p1q1
	if o1 == 0 and onSegment(p1, p2, q1): return True

	# p1, q1 and q2 are colinear and q2 lies on segment p1q1
	if o2 == 0 and onSegment(p1, q2, q1): return True

	# p2, q2 and p1 are colinear and p1 lies on segment p2q2
	if o3 == 0 and onSegment(p2, p1, q2): return True

	# p2, q2 and q1 are colinear and q1 lies on segment p2q2
	if o4 == 0 and onSegment(p2, q1, q2): return True

	return False  # Doesn't fall in any of the above cases


def doPolygonIntersect(poly1, poly2):
	for i in range(len(poly1)):
		P1 = poly1[i]
		if i == (len(poly1)-1):
			P2 = poly1[0]
		else:
			P2 = poly1[i + 1]

		for j in range(len(poly2)):
			P3= poly2[j]
			if j == (len(poly2)-1):
				P4 = poly2[0]
			else:
				P4 = poly2[j + 1]
			if doSegmentIntersect(P1, P2, P3, P4):
				return True
	return False


