Editing Graham scan (section)

== Algorithm ==
{{uncited-section|date=February 2024}}
[[Image:Graham Scan.svg|frame|right|As one can see, PAB and ABC are counterclockwise, but BCD is not. The algorithm detects this situation and discards previously chosen segments until the turn taken is counterclockwise (ABD in this case).]]

The first step in this algorithm is to find the point with the lowest y-coordinate. If the lowest y-coordinate exists in more than one point in the set, the point with the lowest x-coordinate out of the candidates should be chosen. Call this point ''P''. This step takes [[Big O notation|O]](''n''), where ''n'' is the number of points in question.

Next, the set of points must be sorted in increasing order of the angle they and the point ''P'' make with the x-axis. Any general-purpose [[sorting algorithm]] is appropriate for this, for example [[heapsort]] (which is O(''n'' log ''n'')).

Sorting in order of angle does not require computing the angle.  It is possible to use any function of the angle which is monotonic in the [[Interval (mathematics)|interval]] <math>[0,\pi]</math> .  The cosine is easily computed using the [[dot product]], or the slope of the line may be used. If numeric precision is at stake, the comparison function used by the sorting algorithm can use the sign of the [[cross product]] to determine relative angles.

If several points are of the same angle, either break ties by increasing distance ([[Taxicab geometry|Manhattan]] or [[Chebyshev distance|Chebyshev]] distance may be used instead of [[Euclidean distance|Euclidean]] for easier computation, since the points lie on the same ray), or delete all but the furthest point.

The algorithm proceeds by considering each of the points in the sorted array in sequence. For each point, it is first determined whether traveling from the two points immediately preceding this point constitutes making a left turn or a right turn. If a right turn, the second-to-last point is not part of the convex hull, and lies 'inside' it. The same determination is then made for the set of the latest point and the two points that immediately precede the point found to have been inside the hull, and is repeated until a "left turn" set is encountered, at which point the algorithm moves on to the next point in the set of points in the sorted array minus any points that were found to be inside the hull; there is no need to consider these points again. (If at any stage the three points are collinear, one may opt either to discard or to report it, since in some applications it is required to find all points on the boundary of the convex hull.)

Again, determining whether three points constitute a "left turn" or a "right turn" does not require computing the actual angle between the two line segments, and can actually be achieved with simple arithmetic only. For three points <math>P_1 = (x_1,y_1)</math>, <math>P_2 = (x_2,y_2)</math> and <math>P_3 = (x_3,y_3)</math>, compute the ''z''-coordinate of the [[cross product]] of the two [[Vector (geometric)|vectors]] <math>\overrightarrow{P_1P_2}</math> and <math>\overrightarrow{P_1P_3}</math>, which is given by the expression <math>(x_2-x_1)(y_3-y_1)-(y_2-y_1)(x_3-x_1)</math>. If the result is 0, the points are collinear; if it is positive, the three points constitute a "left turn" or counter-clockwise orientation, otherwise a "right turn" or clockwise orientation (for counter-clockwise numbered points).

This process will eventually return to the point at which it started, at which point the algorithm is completed and the stack now contains the points on the convex hull in counterclockwise order.