Question: can you please implement this code into 5 different data structure in Python def convexHull(points, n): # Find the bottommost point ymin = points[0].y min
can you please implement this code into 5 different data structure in Python
def convexHull(points, n):
# Find the bottommost point
ymin = points[0].y
min = 0
for i in range(1, n):
y = points[i].y
# Pick the bottom-most or choose the left
# most point in case of tie
if ((y < ymin) or
(ymin == y and points[i].x < points[min].x)):
ymin = points[i].y
min = i
# Place the bottom-most point at first position
points[0], points[min] = points[min], points[0]
# Sort n-1 points with respect to the first point.
# A point p1 comes before p2 in sorted output if p2
# has larger polar angle (in counterclockwise
# direction) than p1
p0 = points[0]
points = sorted(points, key=cmp_to_key(compare))
# If two or more points make same angle with p0,
# Remove all but the one that is farthest from p0
# Remember that, in above sorting, our criteria was
# to keep the farthest point at the end when more than
# one points have same angle.
m = 1 # Initialize size of modified array
for i in range(1, n):
# Keep removing i while angle of i and i+1 is same
# with respect to p0
while ((i < n - 1) and
(orientation(p0, points[i], points[i + 1]) == 0)):
i += 1
points[m] = points[i]
m += 1 # Update size of modified array
# If modified array of points has less than 3 points,
# convex hull is not possible
if m < 3:
return
# Create an empty stack and push first three points
# to it.
S = []
S.append(points[0])
S.append(points[1])
S.append(points[2])
# Process remaining n-3 points
for i in range(3, m):
# Keep removing top while the angle formed by
# points next-to-top, top, and points[i] makes
# a non-left turn
while ((len(S) > 1) and
(orientation(nextToTop(S), S[-1], points[i]) != 2)):
S.pop()
S.append(points[i])
# Now stack has the output points,
# print contents of stack
while S:
p = S[-1]
print("(" + str(p.x) + ", " + str(p.y) + ")")
S.pop()
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
