Making a Fence

Another day and another SPOJ problem complete ( link to problem). In this one you had to implement a way to find the convex hull of a given set of points. This one wasn't that horrible since I already knew a method to perform the desired task. The only problems I encountered were, 1) what do you do about collinear points and 2) what about one and two point sets? Luckily there were examples that covered both of these issues so I adjusted my code accordingly.

The method I used is known as the Graham Scan. First you find the most lowest point, or furthest left point (I personally like to chose the lowest, but going with the furthest left doesn't really change anything). After this is done you sort the remaining points according to the angle the line connecting them and the lowest point, makes with the x-axis. Then create a stack, and add the first two points (the lowest point and the one with the smallest angel measure). I should clarify that this is not actually a stack since we will need the ability to access both the top and second elements. What you do next is easier to explain with pseudo-code in my opinion at least so here it is:

for i=3 to the size of P //P is the collection of points
. while stack.size>=2 and cross(stack.second, stack.top, P[i])<=0)
.. s.pop //remove the top element
. s.push(P[i])

Basically if a right turn is made (cross product less than 0) or collinear points (cross product equal to 0) the point at the top of the stack is not part of the convex hull. If you don't follow draw some points, if you ever make a "right turn" you are moving "out" and thus it is more efficient to not consider the point at where you turned right. (hope that helped). Supplementary stuff: This could be improved by first finding the points with the largest and smallest x and y coordinates. These four points will form a quadrilateral (assuming you have at least 4 points that is), if any point is inside this quadrilateral it is clearly not part of the convex hull, so you only need to consider the remaining points. I would like to get around to adding this to my code by I am a little stuck at finding a way to determine if a point is in the quadrilateral or not.

In case you were wondering this is a O(n*log n) algorithm.