I know a couple algo’s for convex hull, but they involve stuff like line sweep etc (which I dont mind but still.)
I was thinking of this algorithm, I dont know if this is a standard algorithm or not, I just came up with it. Can someone validate its feasibility (when it comes to computational geometry I’m never sure)
Sort the given points from left to right (increasing x coordinate).
Now maintain a stack of points. We say the points a,b,c are counterclockwise if \angle abc is positive (ccw angle is positive) and clockwise otherwise.
At any moment, let t denote the top of the stack, and s the second-top point. Let c denote the point under consideration.
We first push the leftmost point on to the stack.
Now traverse the sorted points from left to right. At any moment,
- If \angle stc is counterclockwise (or neither), push c onto the stack (or if the stack has only one point).
- Otherwise, pop points off the stack until \angle stc is counterclockwise and then push c.
Now repeat the above but with clockwise instead of counterclockwise. The two stacks obtained are the lower and upper hulls of the point set, and the have two common points (the leftmost point is the first point of both, and the rightmost point is the last point of both).
Now we can merge the counterclockwise one to the reverse of the clockwise hull to get the overall counterclockwise oriented convex hull.
Is the above algorithm correct?
Q2 : And how can I make convex hull dynamic?
Thanks
**Edit: ** There seems to be a Graham’s scan algorithm which is the same as this it seems.
Though, how can I make it online/dynamic?