Convex Hull of a set of points, in 2D plane, is a convex polygon with minimum area such that each point lies either on the boundary of polygon or inside it. Now given a set of points the task is to find the convex hull of points.
 
Example 1:
Input: points_list = {{1,2},{3,1},{5,6}}
Output: {{1,2},{3,1},{5,6}}
Example 2:
Input : points_list = {{5,1},{4,4},{1,2}}
Output: {{1,2},{4,4},{5,1}}
 
Your Task:
You don't need to read or print anything. Your task is to complete the function FindConvexHull() which takes points_list as input parameter and returns Convex Hull of given points in a list. If not possible returns a list containing -1.
 
Expected Time Complexity: O(nlog(n))
Expected Space Complexity: O(n) where n = total no. of points
 
Constraints:
1 <= n <= 10^{4}
-10^{5} <= x, y <= 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Geometry

Divide and conquer

Mathematics

Starter code: #User function Template for python3

class Solution:
	def FindConvexHull(self, points_list):
		# Code here

Solutions:
class Solution:

	def FindConvexHull(self, points):

		def orientation(P, Q, R):
			((xp, yp), (xq, yq), (xr, yr)) = (P, Q, R)
			return xq * (yr - yp) + xp * (yq - yr) + xr * (yp - yq)
		points.sort()
		lower = []
		upper = []
		for r in points:
			while len(lower) >= 2 and orientation(lower[-2], lower[-1], r) <= 0:
				lower.pop()
			lower.append(r)
		for r in points:
			while len(upper) >= 2 and orientation(upper[-2], upper[-1], r) >= 0:
				upper.pop()
			upper.append(r)
		ans = sorted(lower[:-1] + upper[1:])
		return [[-1]] if len(ans) < 3 else ans


class Solution:

	def slope(self, p1, p2):
		return 1.0 * (p1[1] - p2[1]) / (p1[0] - p2[0]) if p1[0] != p2[0] else float('inf')

	def smallest(self, points):
		return min(points_list, key=lambda x: (x[1], x[0]))

	def dist(p1, p2):
		return (p2[1] - p1[1]) ** 2 + (p2[0] - p1[0]) ** 2

	def direction(self, p1, p2, p3):
		return (p2[1] - p1[1]) * (p3[0] - p1[0]) - (p3[1] - p1[1]) * (p2[0] - p1[0])

	def FindConvexHull(self, points_t):
		if len(points_list) < 3:
			return [[-1]]
		hull = []
		points = sorted(points_t, key=lambda x: (x[0], x[1]))
		start = points.pop(0)
		hull.append(start)
		points.sort(key=lambda p: (self.slope(start, p), -p[1], p[0]))
		l = [self.slope(start, p) for p in points]
		for pt in points:
			hull.append(pt)
			while len(hull) > 2 and self.direction(hull[-3], hull[-2], hull[-1]) >= 0:
				a = hull.pop(-2)
			if len(hull) > 2 and self.direction(hull[-2], hull[-1], hull[0]) == 0:
				hull.pop(-1)
		s = []
		for i in hull:
			s.append(points_t.index(i))
		s.sort()
		a = [points_t[i] for i in s]
		return sorted(hull)


class Solution:

	def FindConvexHull(self, points_list):
		points = sorted(points_list, key=lambda p: (p[0], p[1]))
		if len(points_list) <= 2:
			return [[-1]]
		cross = lambda o, a, b: (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])
		lower = []
		for p in points:
			while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
				lower.pop()
			lower.append(p)
		upper = []
		for p in reversed(points):
			while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
				upper.pop()
			upper.append(p)
		ans = [list(row) for row in set((tuple(row) for row in lower[::-1] + upper[::-1]))]
		ans.sort(key=lambda p: (p[0], p[1]))
		return ans


from functools import cmp_to_key

class Solution:

	def FindConvexHull(self, points):
		(left, n) = (0, len(points))
		ref = min(points, key=lambda x: (x[1], x[0]))
		points.remove(ref)

		def comp(a, b):
			o = self.orientation(ref, a, b)
			if o != 0:
				return -o
			return self.dist(a, ref) - self.dist(b, ref)
		points.sort(key=cmp_to_key(comp))
		out = [ref]
		if len(points) < 2:
			return [[-1]]
		out.append(points[0])
		for i in range(1, n - 1):
			while len(out) > 1 and self.isCCW(out[-2], out[-1], points[i]) < 0:
				out.pop()
			out.append(points[i])
		return sorted(out)

	def isCCW(self, x, y, z, collinear=False):
		o = self.orientation(x, y, z)
		if o != 0:
			return o
		if collinear:
			return 1
		return -1

	def orientation(self, x, y, z):
		o = (y[0] - x[0]) * (z[1] - y[1]) - (y[1] - x[1]) * (z[0] - y[0])
		return o

	def dist(self, x, y):
		return (x[0] - y[0]) ** 2 + (x[1] - y[1]) ** 2


class Solution:

	def find(self, S):
		if len(S) <= 2:
			return [[-1]]
		self.convex_hull = []
		top_right_point = S[0]
		bottom_left_point = S[0]
		for p in S:
			if p[0] > top_right_point[0]:
				top_right_point = p
			elif p[0] == top_right_point[0]:
				if p[1] > top_right_point[1]:
					top_right_point = p
			if p[0] < bottom_left_point[0]:
				bottom_left_point = p
			elif p[0] == bottom_left_point[0]:
				if p[1] < bottom_left_point[1]:
					bottom_left_point = p
		S1 = []
		S2 = []
		for p in S:
			if self.check_clockwise(bottom_left_point, top_right_point, p) < 0:
				S1.append(p)
			if self.check_clockwise(top_right_point, bottom_left_point, p) < 0:
				S2.append(p)
		self.convex_hull.append(bottom_left_point)
		self.find_hull(S1, bottom_left_point, top_right_point)
		self.convex_hull.append(top_right_point)
		self.find_hull(S2, top_right_point, bottom_left_point)
		if len(self.convex_hull) == 2:
			self.convex_hull = [[-1]]
		return self.convex_hull

	def square_distance(self, point, line):
		res = abs(self.check_clockwise(line[0], point, line[1])) ** 2 / self.square_length(line)
		return res

	def check_clockwise(self, p1, p2, p3):
		res = (p2[0] - p1[0]) * (p3[1] - p1[1]) - (p2[1] - p1[1]) * (p3[0] - p1[0])
		return res

	def square_length(self, line):
		return (line[0][0] - line[1][0]) ** 2 + (line[0][1] - line[1][1]) ** 2

	def find_hull(self, Sk, P, Q):
		if len(Sk) == 0:
			return
		furthestPoint = Sk[0]
		max_sqr_dist = 0
		for p in Sk:
			sqr_dist = self.square_distance(p, [P, Q])
			if sqr_dist > max_sqr_dist:
				max_sqr_dist = sqr_dist
				furthestPoint = p
		S1 = []
		S2 = []
		for p in Sk:
			if self.check_clockwise(P, furthestPoint, p) < 0:
				S1.append(p)
			if self.check_clockwise(furthestPoint, Q, p) < 0:
				S2.append(p)
		self.find_hull(S1, P, furthestPoint)
		self.convex_hull.append(furthestPoint)
		self.find_hull(S2, furthestPoint, Q)

	def FindConvexHull(self, points_list):
		return sorted(self.find(points_list))


class Solution:

	def isLR(self):
		if len(self.hullS) < 3:
			return True
		return (self.hullS[-1][1] - self.hullS[-2][1]) * (self.hullS[-2][0] - self.hullS[-3][0]) > (self.hullS[-2][1] - self.hullS[-3][1]) * (self.hullS[-1][0] - self.hullS[-2][0])

	def checkCollinear(self, points):
		if len(points) < 3:
			return True
		for i in range(2, len(points)):
			if (points[i][1] - points[i - 1][1]) * (points[i - 1][0] - points[i - 2][0]) - (points[i - 1][1] - points[i - 2][1]) * (points[i][0] - points[i - 1][0]) != 0:
				return False
		return True

	def FindConvexHull(self, points):
		N = len(points)
		if self.checkCollinear(points):
			return [[-1]]
		points.sort()
		self.hullS = [points[0], points[1]]
		for i in range(2, N):
			self.hullS.append(points[i])
			while not self.isLR():
				self.hullS.pop(-2)
		hPoints = self.hullS[:]
		self.hullS = [points[-1], points[-2]]
		for i in range(N - 3, -1, -1):
			self.hullS.append(points[i])
			while not self.isLR():
				self.hullS.pop(-2)
		hPoints += self.hullS[1:-1]
		return sorted(hPoints)


class Solution:

	def FindConvexHull(self, points_list):
		points = []
		for x in points_list:
			points.append(Point(*x))
		return convexHull(points, len(points))

class Point:

	def __init__(self, x, y):
		self.x = x
		self.y = y

def Left_index(points):
	minn = 0
	for i in range(1, len(points)):
		if points[i].x < points[minn].x:
			minn = i
		elif points[i].x == points[minn].x:
			if points[i].y > points[minn].y:
				minn = i
	return minn

def orientation(p, q, r):
	val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y)
	if val == 0:
		return 0
	elif val > 0:
		return 1
	else:
		return 2

def convexHull(points, n):
	if n < 3:
		return [[-1]]
	l = Left_index(points)
	hull = []
	p = l
	q = 0
	while True:
		hull.append(p)
		q = (p + 1) % n
		for i in range(n):
			if orientation(points[p], points[i], points[q]) == 2:
				q = i
		p = q
		if p == l:
			break
	sto = []
	for each in hull:
		if [-10, 1] != [points[each].x, points[each].y]:
			sto.append([points[each].x, points[each].y])
	return sorted(sto)