Description: Graham scan algorithm: the general idea is not a convex hull vertex points from a point focus on remove.
Identify S with the minimum y coordinate of the point p (select the left-most point to break a tie)
According to the connection point and p x-axis positive direction into the angle, sort the points in S (small to large), and p up front.
Scan sorted S-collection from p. These points on the convex hull of every three successive points p1, p2, p3, meet the following properties: p3, in vector <p1,p2> the left side if the successive three points p1 is p2, p3 does not meet the the above properties, then p2 is definitely not the vertex of the convex hull should be immediately removed.
To Search:
File list (Check if you may need any files):
graham.cpp
Download