Week 1

Convex Hull Algorithms

Jarvis Algorithm or gift wrapping algorithm

To understand the Jarvis’s Convex Hull Algorithm at first we have to

take a glance the detecting process of orientation of given three

cartesian 2D points. 

Picture - 1

In the above picture the orientation of Points A, B and C is

Clockwise, Orientation of Points D, E and F is Counter Clockwise and 

Orientation of Points G, H and I is Linear.

According to the picture, if the Orientation of Points X, Y and Z is

Clockwise then Orientation of Points Z, Y and X must be Counter

Clockwise and vice versa. 

Suppose we have three cartesian 2D points

$ X(x_{1},y_{1}) $ , $ Y(x_{2},y_{2}) $ and $ Z(x_{3},y_{3}) $.

The slope of XY is $$ m1 = \frac{ y_{2} - y_{1} } { x_{2} - x_{1} } $$

The slope of YZ is $$ m2 = \frac{ y_{3} - y_{2} } { x_{3} - x_{2} } $$

If m1 > m2,   X, Y and Z orientation will be clockwise, 

If m1 < m2,   X, Y and Z orientation will be counter clockwise and 

If m1 = m2,  X, Y and Z orientation will be linear.

So, if (m1 - m2) is negative the orientation is counter clockwise. 

For Counter clockwise orientation  - 

$$ \frac { y_{2} - y_{1} } { x_{2} - x_{1} } - \frac { y_{3} - y_{2} } { x_{3} - x_{2} } < 0$$

$$ => \frac { ( y_{2} - y_{1} ) ( x_{3} - x_{2} ) - ( y_{3} - y_{2} ) ( x_{2} - x_{1} ) } { ( x_{2}-x_{1} ) (x_{3}-x_{2}) } < 0$$

$$ => ( y_{2} - y_{1} ) ( x_{3} - x_{2} ) - ( y_{3} - y_{2} ) ( x_{2} - x_{1} ) < 0 $$

Orientation Check [C++ code]

Jarvis algrithm

At first choose the leftmost point L ( the point, which x coordinate is smallest  ).Choose the next point where orientation( L , P, i ) is always counterclockwise, where i refers all points. Then 

Set L = P, and find the next point until P = L. The algorithm select the next point such a way where there is no point j where orientation( privious_point , j , next_point ) is counterclockwise. 

The algorithm also works for clockwise direction.

Jarvis algorithm [C++code]
input points :

The Time Complexity of Jarvis's algorithm is $O(n^2)$.
Grahum Scan algorithm ....