|
| 1 | +<!--?title Convex Hull construction --> |
| 2 | +# Convex Hull construction |
| 3 | + |
| 4 | +In this article we will discuss the problem of constructing a convex hull from a set of points. |
| 5 | + |
| 6 | +Consider $N$ points given on a plane, and the objective is to generate a convex hull, i.e. the smallest |
| 7 | +convex polygon that contains all the given points. |
| 8 | + |
| 9 | +We will see the **Graham's scan** algorithm published in 1972 by Graham, and |
| 10 | +also the **Monotone chain** algorithm published in 1979 by Andrew. Both |
| 11 | +are $\mathcal{O}(N \log N)$, and are asymptotically optimal (as it is proven that there |
| 12 | +is no algorithm asymptotically better), with the exception of a few problems where |
| 13 | +parallel or online processing is involved. |
| 14 | + |
| 15 | +## Graham's scan Algorithm |
| 16 | +The algorithm first finds the bottom-most point $P_0$. If there are multiple points |
| 17 | +with the same Y coordinate, the one with the smaller X coordinate is considered. This |
| 18 | +step takes $\mathcal{O}(N)$ time. |
| 19 | + |
| 20 | +Next, all the other points are sorted by polar angle in counterclockwise order. |
| 21 | +If the polar angle between two points is the same, the nearest point is chosen instead. |
| 22 | + |
| 23 | +Then we iterate through each point one by one, and make sure that the current |
| 24 | +point and the two before it make a counterclockwise turn, otherwise the previous |
| 25 | +point is discarded, since it would make a non-convex shape. Checking for clockwise or anticlockwise |
| 26 | +nature can be done by checking the [orientation](./geometry/oriented-triangle-area.html). |
| 27 | + |
| 28 | +We use a stack to store the points, and once we reach the original point $P_0$, |
| 29 | +the algorithm is done and we return the stack containing all the points of the |
| 30 | +convex hull in clockwise order. |
| 31 | + |
| 32 | +If you need to include the collinear points while doing a Graham scan, you need |
| 33 | +another step after sorting. You need to get the points that have the biggest |
| 34 | +polar distance from $P_0$ (these should be at the end of the sorted vector) and are collinear. |
| 35 | +The points in this line should be reversed so that we can output all the |
| 36 | +collinear points, otherwise the algorithm would get the nearest point in this |
| 37 | +line and bail. This step shouldn't be included in the non-collinear version |
| 38 | +of the algorithm, otherwise you wouldn't get the smallest convex hull. |
| 39 | + |
| 40 | +### Implementation |
| 41 | + |
| 42 | +```cpp graham_scan |
| 43 | +struct pt { |
| 44 | + double x, y; |
| 45 | +}; |
| 46 | + |
| 47 | +int orientation(pt a, pt b, pt c) { |
| 48 | + double v = a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y); |
| 49 | + if (v < 0) return -1; // clockwise |
| 50 | + if (v > 0) return +1; // counter-clockwise |
| 51 | + return 0; |
| 52 | +} |
| 53 | + |
| 54 | +bool cw(pt a, pt b, pt c, bool include_collinear) { |
| 55 | + int o = orientation(a, b, c); |
| 56 | + return o < 0 || (include_collinear && o == 0); |
| 57 | +} |
| 58 | +bool collinear(pt a, pt b, pt c) { return orientation(a, b, c) == 0; } |
| 59 | + |
| 60 | +void convex_hull(vector<pt>& a, bool include_collinear = false) { |
| 61 | + pt p0 = *min_element(a.begin(), a.end(), [](pt a, pt b) { |
| 62 | + return make_pair(a.y, a.x) < make_pair(b.y, b.x); |
| 63 | + }); |
| 64 | + sort(a.begin(), a.end(), [&p0](const pt& a, const pt& b) { |
| 65 | + int o = orientation(p0, a, b); |
| 66 | + if (o == 0) |
| 67 | + return (p0.x-a.x)*(p0.x-a.x) + (p0.y-a.y)*(p0.y-a.y) |
| 68 | + < (p0.x-b.x)*(p0.x-b.x) + (p0.y-b.y)*(p0.y-b.y); |
| 69 | + return o < 0; |
| 70 | + }); |
| 71 | + if (include_collinear) { |
| 72 | + int i = (int)a.size()-1; |
| 73 | + while (i >= 0 && collinear(p0, a[i], a.back())) i--; |
| 74 | + reverse(a.begin()+i+1, a.end()); |
| 75 | + } |
| 76 | + |
| 77 | + vector<pt> st; |
| 78 | + for (int i = 0; i < (int)a.size(); i++) { |
| 79 | + while (st.size() > 1 && !cw(st[st.size()-2], st.back(), a[i], include_collinear)) |
| 80 | + st.pop_back(); |
| 81 | + st.push_back(a[i]); |
| 82 | + } |
| 83 | + |
| 84 | + a = st; |
| 85 | +} |
| 86 | +``` |
| 87 | + |
| 88 | +## Monotone chain Algorithm |
| 89 | +The algorithm first finds the leftmost and rightmost points A and B. In the event multiple such points exist, |
| 90 | +the lowest among the left (lowest Y-coordinate) is taken as A, and the highest among the right (highest Y-coordinate) |
| 91 | +is taken as B. Clearly, A and B must both belong to the convex hull as they are the farthest away and they cannot be contained |
| 92 | +by any line formed by a pair among the given points. |
| 93 | + |
| 94 | +Now, draw a line through AB. This divides all the other points into two sets, S1 and S2, where S1 contains all the points |
| 95 | +above the line connecting A and B, and S2 contains all the points below the line joining A and B. The points that lie on |
| 96 | +the line joining A and B may belong to either set. The points A and B belong to both sets. Now the algorithm |
| 97 | +constructs the upper set S1 and the lower set S2 and then combines them to obtain the answer. |
| 98 | + |
| 99 | +To get the upper set, we sort all points by the x-coordinate. For each point we check if either - the current point is the last point, |
| 100 | +(which we defined as B), or if the orientation between the line between A and the current point and the line between the current point and B is clockwise. In those cases the |
| 101 | +current point belongs to the upper set S1. Checking for clockwise or anticlockwise nature can be done by checking the [orientation](./geometry/oriented-triangle-area.html). |
| 102 | + |
| 103 | +If the given point belongs to the upper set, we check the angle made by the line connecting the second last point and the last point in the upper convex hull, |
| 104 | +with the line connecting the last point in the upper convex hull and the current point. If the angle is not clockwise, we remove the most recent point added |
| 105 | +to the upper convex hull as the current point will be able to contain the previous point once it is added to the convex |
| 106 | +hull. |
| 107 | + |
| 108 | +The same logic applies for the lower set S2. If either - the current point is B, or the orientation of the lines, formed by A and the |
| 109 | +current point and the current point and B, is counterclockwise - then it belongs to S2. |
| 110 | + |
| 111 | +If the given point belongs to the lower set, we act similarly as for a point on the upper set except we check for a counterclockwise |
| 112 | +orientation instead of a clockwise orientation. Thus, if the angle made by the line connecting the second last point and the last point in the lower convex hull, |
| 113 | +with the line connecting the last point in the lower convex hull and the current point is not counterclockwise, we remove the most recent point added to the lower convex hull as the current point will be able to contain |
| 114 | +the previous point once added to the hull. |
| 115 | + |
| 116 | +The final convex hull is obtained from the union of the upper and lower convex hull, forming a clockwise hull, and the implementation is as follows. |
| 117 | +If you need collinear points, you just need to include them in the clockwise/counterclockwise routines, by changing `<` to `<=` and `>` to `>=`. |
| 118 | + |
| 119 | +### Implementation |
| 120 | + |
| 121 | +```cpp monotone_chain |
| 122 | +struct pt { |
| 123 | + double x, y; |
| 124 | +}; |
| 125 | + |
| 126 | +int orientation(pt a, pt b, pt c) { |
| 127 | + double v = a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y); |
| 128 | + if (v < 0) return -1; // clockwise |
| 129 | + if (v > 0) return +1; // counter-clockwise |
| 130 | + return 0; |
| 131 | +} |
| 132 | + |
| 133 | +bool cw(pt a, pt b, pt c, bool include_collinear) { |
| 134 | + int o = orientation(a, b, c); |
| 135 | + return o < 0 || (include_collinear && o == 0); |
| 136 | +} |
| 137 | +bool ccw(pt a, pt b, pt c, bool include_collinear) { |
| 138 | + int o = orientation(a, b, c); |
| 139 | + return o > 0 || (include_collinear && o == 0); |
| 140 | +} |
| 141 | + |
| 142 | +void convex_hull(vector<pt>& a, bool include_collinear = false) { |
| 143 | + if (a.size() == 1) |
| 144 | + return; |
| 145 | + |
| 146 | + sort(a.begin(), a.end(), [](pt a, pt b) { |
| 147 | + return make_pair(a.x, a.y) < make_pair(b.x, b.y); |
| 148 | + }); |
| 149 | + pt p1 = a[0], p2 = a.back(); |
| 150 | + vector<pt> up, down; |
| 151 | + up.push_back(p1); |
| 152 | + down.push_back(p1); |
| 153 | + for (int i = 1; i < (int)a.size(); i++) { |
| 154 | + if (i == a.size() - 1 || cw(p1, a[i], p2, include_collinear)) { |
| 155 | + while (up.size() >= 2 && !cw(up[up.size()-2], up[up.size()-1], a[i], include_collinear)) |
| 156 | + up.pop_back(); |
| 157 | + up.push_back(a[i]); |
| 158 | + } |
| 159 | + if (i == a.size() - 1 || ccw(p1, a[i], p2, include_collinear)) { |
| 160 | + while (down.size() >= 2 && !ccw(down[down.size()-2], down[down.size()-1], a[i], include_collinear)) |
| 161 | + down.pop_back(); |
| 162 | + down.push_back(a[i]); |
| 163 | + } |
| 164 | + } |
| 165 | + |
| 166 | + a.clear(); |
| 167 | + for (int i = 0; i < (int)up.size(); i++) |
| 168 | + a.push_back(up[i]); |
| 169 | + for (int i = down.size() - 2; i > 0; i--) |
| 170 | + a.push_back(down[i]); |
| 171 | +} |
| 172 | +``` |
| 173 | + |
| 174 | +## Practice Problems |
| 175 | + |
| 176 | +* [Kattis - Convex Hull](https://open.kattis.com/problems/convexhull) |
| 177 | +* [Kattis - Keep the Parade Safe](https://open.kattis.com/problems/parade) |
| 178 | +* [URI 1464 - Onion Layers](https://www.urionlinejudge.com.br/judge/en/problems/view/1464) |
| 179 | +* [Timus 1185: Wall](http://acm.timus.ru/problem.aspx?space=1&num=1185) |
| 180 | +* [Usaco 2014 January Contest, Gold - Cow Curling](http://usaco.org/index.php?page=viewproblem2&cpid=382) |
0 commit comments