Not Frequent
 0/9

Convex Hull

Authors: Benjamin Qi, Neo Wang, Chuyang Wang

Smallest convex polygon containing a set of points on a grid.

Introduction

The Convex Hull is the subset of points that forms the smallest convex polygon which encloses all points in the set. To visualize this, imagine that each point is a pole. Then, imagine what happens if you were to wrap a rope around the outside of all the poles, and then pull infinitely hard, such that the connections between any two points that lie on the edge of the rope are lines. The set of points that touch the rope is the convex hull.

Convex Hull Visualization

Focus Problem – try your best to solve this problem before continuing!

With Graham Scan

Solution

C++

The Graham Scan algorithm works in 3 steps. First, it sorts all of the nn points by their counterclockwise angle around a pivot P0P_0, breaking ties by distance. This algorithm uses the leftmost (and bottommost if there is a tie), point as P0P_0.

We maintain a stack containing the points such that the following invariant holds: every three consecutive points a,b,ca,b,c of the stack form a counterclockwise turn. In other words, cc lies to the left of the line from aa to bb. This condition implies that the points of the stack form the vertices of a convex polygon.

To start the creation of the convex hull, we choose 2 points. The pivot (first point), and the second point based on our initial sorting. After that, we attempt to add each point in cand\texttt{cand} to the stack.

Denote our stack as hull\texttt{hull}, the top element of hull\texttt{hull} as hull[i]\texttt{hull}[i] and cand[j]\texttt{cand}[j] as the jj-th sorted candidate point. Before adding cand[j]\texttt{cand}[j] to the stack, we check whether hull[i1]hull[i]cand[j]\texttt{hull}[i-1] \rightarrow \texttt{hull}[i] \rightarrow \texttt{cand}[j] forms a counterclockwise turn.

  • If so, then we add cand[j]\texttt{cand}[j] to the stack and the invariant holds. Continue with cand[j+1]\texttt{cand}[j+1].
  • Otherwise, hull[i]\texttt{hull}[i] lies within the convex hull of the other points in the stack along with cand[j]\texttt{cand}[j], so we pop hull[i]\texttt{hull}[i] from the stack and continue with cand[j]\texttt{cand}[j].

Illustration

Worked Example

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define FORE(i, a, b) for (int i = (a); i <= (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define trav(a, x) for (auto &a : x)
#define f first

With Monotone Chain

Solution

With the Monotone Chain algorithm, we start by sorting the given nn points in ascending order with respect to their xx coordinates. If two points have the same xx coordinate, then we will look at the yy coordinate.

Next, we will calculate the convex hull in two parts - the upper and the lower hull. Firstly, we observe that the starting and ending points of both upper and lower hulls are the same. They are the points with the lowest and highest xx value respectively, P0P_0 and Pn1P_{n-1}. We start by adding P0P_0 and P1P_1 to the hull. (Note that P1P_1 doesn't necessarily have to be on the convex hull at the end). Then, starting from P2P_2, we iterate through the sorted points and add them to the hull. Let's denote the current point being added as PkP_{k} and the last point still on the hull as PiP_{i}. When adding new points, we want to make sure that there is no right turn among all segments of the hull, just like in the Graham Scan algorithm discussed above. To achieve this, the segment Pi1PiP_{i-1}P_i should always be on the right side of the segment Pi1PkP_{i-1}P_k. This can be calculated by using a cross-product:

  • If (PiPi1)×(PkPi1)<0(P_i - P_{i-1}) \times (P_k - P_{i-1}) < 0, the point PiP_i lies on the left side of the segment Pi1PkP_{i-1}P_k. In this case, we have to remove point PiP_i from the hull and repeat this check.
  • If (PiPi1)×(PkPi1)=0(P_i - P_{i-1}) \times (P_k - P_{i-1}) = 0, the point PiP_i lies on the segment Pi1PkP_{i-1}P_k. Whether to include multiple collinear points depends on the question, but for the given question above, we will remove the point PiP_i as well and repeat the check.
  • Otherwise, the point PiP_i lies on the right side of the segment Pi1PkP_{i-1}P_k. In this case, we can add PkP_k to the hull and process the next point Pk+1P_{k+1} from the given point list.

After all the points have been processed, we have found the lower hull and will begin to find the upper hull in the same manner. This time, we add point Pn2P_{n-2} to the hull and iterate from the end of the points, Pn3P_{n-3}, to the starting point P0P_0. (The point Pn2P_{n-2} also doesn't necessarily have to be the convex hull and could be removed if it causes a right turn).

At the end, we have got all points of the convex hull in the counterclockwise order. To do this in the clockwise order, one only has to change the condition for (PiPi1)×(PkPi1)(P_i - P_{i-1}) \times (P_k - P_{i-1}) from more than 0 to less than 0. In this case, the upper hull will be found first and then the lower hull.

This algorithm takes O(nlogn)\mathcal{O}(n \log n) time to sort the points and O(n)\mathcal{O}(n) time to calculate the hull, giving a final time complexity of O(nlogn)\mathcal{O}(n \log n).

An animation of how it works:

Worked Example

C++

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
vector<pii> points;
vector<pii> hull;
// cross product, the signed area of these there points
int area(pii O, pii P, pii Q) {

Java

import java.io.*;
import java.util.*;
public class ConvexHull {
public static void main(String[] args) throws IOException {
BufferedReader in =
new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(in.readLine());
while (N > 0) {

Rotating Calipers

Focus Problem – try your best to solve this problem before continuing!

Solution

This section is not complete.

Any help would be appreciated! Just submit a Pull Request on Github.

Problems

StatusSourceProblem NameDifficultyTags
CFEasy
Show TagsConvex
PlatNormal
Show TagsConvex
CFNormal
Show TagsConvex, PURS
Old GoldNormal
Show TagsConvex
KattisHard
Show TagsConvex
Balkan OIHard
Show TagsConvex, MST
ACVery Hard
Show TagsConvex

Module Progress:

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!