Write an algorithm to compute the convex hull of a set of points.
- User
Write an algorithm to compute the convex hull of a set of points.
- Assistant
Developing a convex hull algorithm
The user is looking for an algorithm to compute the convex hull of a set of points, likely in computational geometry. I should consider multiple algorithms, such as Graham scan, Jarvis march, Andrew's monotone chain, and QuickHull. They haven't specified the language or dimensionality, so I’ll assume 2D planar points. I think I’ll focus on Andrew's monotone chain algorithm since it's efficient and robust. I’ll provide pseudocode, an explanation of the cross product and sorting, along with the essential steps. Here is a standard O(n log n) algorithm to compute the convex hull of a finite set of 2D points: Andrew’s monotone chain algorithm.
It returns the hull as a list of vertices in counter-clockwise (CCW) order.
Idea
- Sort points by x, then by y.
- Build the lower hull from left to right.
- Build the upper hull from right to left.
- Concatenate lower and upper (excluding the last point of each to avoid duplication).
The key geometric test is the cross product to detect whether three consecutive points make a left turn, right turn, or are collinear.
Geometry helper
For three points
O,A,B, define:cross(O, A, B) = (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x)cross > 0→ O→A→B makes a counter-clockwise (left) turncross < 0→ clockwise (right) turncross = 0→ points are collinear
For the convex hull, we remove points that would make a right turn (non-convex corner).
Pseudocode
Assume points are given as an array
P[0..n-1], eachP[i]has fields.xand.y.function convex_hull(P): n = length(P) if n <= 1: return copy(P) // 1. Sort by x, then y sort P by (x ascending, then y ascending) // 2. Build lower hull lower = empty list for each point p in P: while length(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0: pop last element from lower append p to lower // 3. Build upper hull upper = empty list for each point p in P in reverse order: while length(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0: pop last element from upper append p to upper // 4. Concatenate lower and upper to get full hull // Last point of each list is same as first point of the other list pop last element from lower pop last element from upper hull = concatenate(lower, upper) return hull function cross(O, A, B): return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x)
Notes
- Complexity:
O(n log n)due to sorting; the hull construction itself isO(n). - The result
hullis a list of vertices in CCW order forming the convex polygon. - To keep collinear boundary points, change the condition
< = 0to< 0in the while loops.
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.