Graham's Scan method for solving convex hull problems

Question background

• About the convex hull
  Assuming that there are 13 points p0~p12 on the plane, make a polygon through some points, so that this polygon can "enclose" all the points, when the polygon is a convex polygon,We call this the "convex hull"
• Convex Hull Problem
  On a two-dimensional coordinate system, each point can be represented by coordinates (x,y)
  Given the number of points and the coordinates of each point, find the points that form the convex hull
  

Graham’s Scan method

Find a point on the convex hull first, and start from that point to find the points on the convex hull one by one in a counterclockwise direction

Steps

1. Put all points in the two-dimensional coordinate system, then the point with the smallest ordinate must be the point on the convex hull, as shown in the figure p0

2. Translate the coordinates of all points to make p0 as the origin, as shown above

3. Calculate the argument of each point with respect to p0$\alpha$, sorts the points in ascending order of argument.When $\alpha$ When the points are the same, the points closer to p0 are ranked first.For example, the results obtained in the above figure are p1, p2, p3, p4, p5, p6, p7, p8.It can be known from geometric knowledge that the first point p1 and the last point p8 must be points on the convex hull

4. Now that we know the first point p0 and the second point p1 on the convex hull, we put them on the stack in turn.

5. Initialize the current point to p2, and perform the following operations:

    a. Determine the difference between the vector formed by the two points at the top of the stack and the vector formed by the stack vertex and the current pointWhether the relationship is counterclockwise, that is, whether the vector obtained after the cross product is counterclockwise.(Another formulation of this question is to connect two points at the top of the stack to get a straight line to see if the current point is to the left of the straight line)b. If so, the current point is the point on the convex hull, and it is pushed into the stack.And take the next point in the sorting as the current point, and continue to judge a until all points are traversed.c. If not, the top element of the stack is not a point on the convex hull, and the top element of the stack is popped.The current point remains unchanged, and the judgment of a continues until it is a counterclockwise relationship.

6. After the final traversal, the elements in the stack are the points that form the convex hull

Flowchart

Code Link

Graham's Scan method for convex hull problem