**Problem:**a series of points are on plain (X>0 and Y>0), find the convex hull of these points, a.k.a, the points which can form a hull that include all the other points.

**Solution:**Here only main idea is given.Basically we can use Graham scan.

- Find the point
*p0*with the smallest y coordinate; if multiple exist, choose the one with the smallest x coordinate, this point must be one of the vertices on the convex hull. - Sort the other points based on the angle of
*p0->pi*. - Put
*p0, p1 and p2*in a stack (we need at least three to form a hull), then we inspect the rest points based on the order. Assume*px*is the stack top and*py*is the one next to the top, if*py*->*pi*is at the right side of*py-*>*px*, pop*px*. We apply the same check to the new*px*and*py*until the previous condition doesn't hold. Then we push*pi*if previous there are any pop operations. If before push*pi*, there are only two elements in stack, we can push*pi*directly. - After we iterate all the remaining points, the points on the stack are those that form the convex hull. The complexity is O(nlogn), primarily the sorting cost.

**More:**Alternatively, we can use Jarvis’s march which is asymptotically faster than Graham’s scan. The time complexity is O(nh) where h is the number of the vertices on the hull. The main idea is as follow:

- Find the highest point
*p_high*and lowest point*p_low*among all the points, which takes O(n). - Start from
*p_low,*find the next point that has the smallest*p_low.*Assume this point is*p'*, then find the next point that has the smallest*p'*. Repeat such process until we find*p_high.*Up to now, we had found the left chain of the hull. - Then proceed to find the right chain of the hull. It is similar to finding the left chain. We start from
*p_high*and stop when we reach*p_low.*The only difference is that when we calculate the polar angle, we use*-x*axis instead of +x axis.

## No comments:

## Post a Comment