Expand description
Implementation of Andrew’s monotone chain convex hull algorithm The runtime is $O(n\log n)$ by sorting the points lexicographically by their lon/lat coordinates, and by subsequently constructing upper and lower hulls.
Note that the sorting order is lon/lat to make sure the x coordinate has higher precedence than the y coordinate – an invariant of the algorithm.