You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
deforientation(p, q, r):
""" Calculate orientation of three points (p, q, r). Returns: -1 if counterclockwise 0 if colinear 1 if clockwise """val= (q[1] -p[1]) * (r[0] -q[0]) - (q[0] -p[0]) * (r[1] -q[1])
ifval==0:
return0return1ifval>0else-1defgraham_scan(points):
""" Graham's scan algorithm to find the convex hull of a set of points. Returns the sorted points forming the convex hull. """n=len(points)
ifn<3:
returnpoints# Find the point with the lowest y-coordinate (and leftmost if ties)pivot=min(points, key=lambdap: (p[1], p[0]))
# Sort the points based on polar angle with respect to the pivotsorted_points=sorted(points, key=lambdap: (math.atan2(p[1]-pivot[1], p[0]-pivot[0]), p))
# Initialize the stackstack= [pivot, sorted_points[0], sorted_points[1]]
# Iterate over the sorted pointsforiinrange(2, n):
whilelen(stack) >1andorientation(stack[-2], stack[-1], sorted_points[i]) !=-1:
stack.pop()
stack.append(sorted_points[i])
returnstack# Example: Collection of arbitrary pointspoints= [(0, 0), (3, 1), (1, 2), (2, 3), (4, 4), (3, 0), (2, 1)]
# Sort the points to form a closed linear ringsorted_ring=graham_scan(points)
print("Original Points:", points)
print("Sorted Linear Ring Points:", sorted_ring)
This implementation uses the Graham's scan algorithm to find the convex hull of the points, and the resulting sorted_ring contains the points forming a closed linear ring without self-intersections.
This discussion was converted from issue #204 on February 05, 2024 14:52.
Heading
Bold
Italic
Quote
Code
Link
Numbered list
Unordered list
Task list
Attach files
Mention
Reference
Menu
reacted with thumbs up emoji reacted with thumbs down emoji reacted with laugh emoji reacted with hooray emoji reacted with confused emoji reacted with heart emoji reacted with rocket emoji reacted with eyes emoji
-
This implementation uses the Graham's scan algorithm to find the convex hull of the points, and the resulting sorted_ring contains the points forming a closed linear ring without self-intersections.
Beta Was this translation helpful? Give feedback.
All reactions