• Customer Support: admin@thealgorists.com
  • Feedback: We are listening to your every feedback, and taking action to constantly improve your learning experience. If you have any feedback, please use this form: https://thealgorists.com/Feedback.
  • If you are a student, email to admin@thealgorists.com to get special student discount.







In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. Convex means that the polygon has no corner that is bent inwards. If S is a set of points, then convex hull is the smallest convex polygon which covers all the points of S.



From above diagram it is quite clear that once we look Convex hull as combination of one upper hull and one lower hull, the problem of constructing convex hull for a given set of points naturally becomes a great candidate for Sweep Line algorithm.
If you think enough, you would be able to convince yourself that
  1. if you sweep a vertical line across the plane either from left to right or from right to left (depending on whether we want to form the convex hull in clockwise manner or counterclockwise), and while doing so if you collect the point (from the given set of points) with the highest y-coordinate at any x-coordinate, you would get the upper portion of convex hull. Let's call it upper hull.
  2. if you sweep a vertical line across the plane either from right to left or from left to right (depending on whether we want to form the convex hull in clockwise manner or counterclockwise), and while doing so if you collect the point (from the given set of points) with the lowest y-coordinate at any x-coordinate, you would get the lower hull.

Another thing worth noting from the above diagram is that:
  • Take any ordered set of 3 consecutive points on the UPPER hull from ordered from left to right. Let's suppose these 3 points are U1, U2 and U3,
    U1 being the leftmost point and U3 rightmost. Now let's imagine we have directed edges from U1 to U2, U2 to U3 and U3 to back to U1. For any such points U1, U2, U3 on the upper hull you will notice that the orientation of the cycle U1-> U2 -> U3 -> U1 is CLOCKWISE. Please see the below section on Orientation for more information.



  • Take any ordered set of 3 consecutive points on the LOWER hull from ordered from right to left. Let's suppose these 3 points are L3, L2 and L1,
    p3 being the rightmost point and p1 leftmost. Now let's imagine we have directed edges from L3 to L2, L2 to L1 and L1 to back to L3. For any such points L3, L2, L1 on the lower hull you will notice that the orientation of the cycle L3 -> L2 -> L1 -> L3 is CLOCKWISE.


Orientation:


The above picture gives a very clear idea about orientation of three ordered points.
Now, given three ordered points how do we determine their orientation? Answer is by using the concept of Slope. Slope of a straight line P1P2 is the tan of the angle it forms with the X-axis. If coordinates of point P1 is (x1, y1), and that of P2 is (x2, y2), and the angle between P1P2 and X-axis is theta, then
Slope = tan theta = delta Y / delta X = (y2 - y1) / (x2 - x1)

From the above diagram it is very easy to say that:
  1. p1p2 and p2p3 will be collinear if and only if:
    Angle P3P2X2 (or, angle beta) = Angle P2P1X1 (or, angle theta), i.e.,
    (y3 - y2) / (x3 - x2) = (y2 - y1) / (x2 - x1),
    or, (y3 - y2) * (x2 - x1) = (y2 - y1) * (x3 - x2) , multiplied each side by (x3 - x2) * (x2 - x1)
    or, (y3 - y2) * (x2 - x1) - (y2 - y1) * (x3 - x2) = 0
  2. Orientation of p1p2p3 will be clockwise if and only if:
    Angle P3P2X2 (or, angle beta) < Angle P2P1X1 (or, angle theta), i.e.,
    (y3 - y2) / (x3 - x2) < (y2 - y1) / (x2 - x1),
    or, (y3 - y2) * (x2 - x1) < (y2 - y1) * (x3 - x2) , multiplied each side by (x3 - x2) * (x2 - x1)
    or, (y3 - y2) * (x2 - x1) - (y2 - y1) * (x3 - x2) < 0
  3. Orientation of p1p2p3 will be counterclockwise if and only if:
    Angle P3P2X2 (or, angle beta) > Angle P2P1X1 (or, angle theta), i.e.,
    (y3 - y2) / (x3 - x2) > (y2 - y1) / (x2 - x1),
    or, (y3 - y2) * (x2 - x1) > (y2 - y1) * (x3 - x2) , multiplied each side by (x3 - x2) * (x2 - x1)
    or, (y3 - y2) * (x2 - x1) - (y2 - y1) * (x3 - x2) > 0

    // Method to find orientation of ordered triplet  
    // (p1, p2, p3). The function returns  
    // following values  
    // zero: p, q and r are colinear 
    // negative integer: p1 -> p2 -> p3 -> p1 forms Clockwise cycle 
    // positive integer: p1 -> p2 -> p3 -> p1 forms Counterclockwise cycle
    private int direction(int[] p1, int[] p2, int[] p3) {
        return ((p2[1] - p1[1]) * (p3[0] - p2[0])) - ((p3[1] - p2[1]) * (p2[0] - p1[0]));
    }

So, now that we have knowledge about all the bits and pieces we need to implement the algorithm to compute Convex Hull, let's look at the complete implementation below:


Please subscribe to access the complete working solution.
After subscribing please come back and refresh this page.





Related Must-Read Topics:

  1. 1d Range Search
  2. Closest Pair
  3. Dual Line Sweep
    & Rectangles Union
  4. 2D Intervals Union
    & Skyline Problem
  5. Overlapping 1D Intervals
  6. Merging Overlapping 1D Intervals
  7. Separating Overlapping 1D Intervals


The above content is written by:

Abhishek Dey

Abhishek Dey

A Visionary Software Engineer With A Mission To Empower Every Person & Every Organization On The Planet To Achieve More

Microsoft | University of Florida

View LinkedIn profile


If you have any feedback, please use this form: https://thealgorists.com/Feedback.




Subscribe to Our Youtube Channel

Follow Us On LinkedIn
wave