# Polygons and Convex Hull

## Objectives

• The the ccw function to check if a polygon is convex or not.
• Compute the perimeter and area or an arbitrary polygon
• Find a polygon (convex hull) that fits a set of points.
• Most code samples from Competitive Programming 3.

## Representation

• Represent a polygon using a vector of points.
• Add them in clockwise or counterclockwise order.
• The first point should be re-added as the last point.
vii mypoly;
mypoly.push_back(ii(2,2));
mypoly.push_back(ii(27,10));
mypoly.push_back(ii(30,25));
mypoly.push_back(ii(6,20));
mypoly.push_back(ii(2,20));
mypoly.push_back(ii(2,2));


## Getting the Area

$A = {1\over 2} \left[\begin{array}{ll} x_0 & y_0 \\ x_1 & y_1 \\ x_2 & y_2 \\ \cdots & \cdots \\ x_n & y_n \\ \end{array} \right]$

$= \begin{array}{l} x_0 y_1 + x_1 y_2 + \cdots + x_n y_0 \\ - x_1 y_0 - x_2 y_1 - \cdots - x_0 y_n \end{array}$

double area(const vector<point> &P) {
double result = 0.0, x1, y1, x2, y2;
for (int i = 0; i < (int)P.size()-1; i++) {
x1 = P[i].x; x2 = P[i+1].x;
y1 = P[i].y; y2 = P[i+1].y;
result += (x1 * y2 - x2 * y1);
}
return fabs(result) / 2.0;
}


## Is it Convex?

• Check if all turns on the perimeter turn the same way.
double cross(vec a, vec b) {
return a.x*b.y - a.y*b.x;
}

point ccw(point p, point q, point r) {
return cross(toVec(p,q), toVec(p,r)) > EPS;
}

bool isConvex(const vector<point> &P) {
int sz = (int)P.size();
if (sz <= 3) return false; // a point/sz=2 or a line/sz=3 is not convex
bool isLeft = ccw(P[0], P[1], P[2]); // remember one result
for (int i = 1; i < sz-1; i++)       // then compare with the others
if (ccw(P[i], P[i+1], P[(i+2) == sz ? 1 : i+2]) != isLeft)
return false; // different sign -> this polygon is concave
return true;        // this polygon is convex
}


## Convex Hull

• Given: a bunch of points
• We want: a minimal convex polygon to contain them.
• Basic algorithm:
• Pick lowest point (and rightmost, if tie) as a pivot
• Sort the points by the angle to the pivot. Call these $$p_1, p_2$$, etc.
• Push pivot, $$p_1$$, to a stack.
• Repeat from $$p_2$$:
• Push point to stack
• If (angle of top three points) is clockwise, delete midpoint from stack.

## Sorting by Angle

point pivot(0, 0);
bool angleCmp(point a, point b) {// angle-sorting function
if (collinear(pivot, a, b)) // special case
return dist(pivot, a) < dist(pivot, b);
// check which one is closer
double d1x = a.x - pivot.x, d1y = a.y - pivot.y;
double d2x = b.x - pivot.x, d2y = b.y - pivot.y;
return (atan2(d1y, d1x) - atan2(d2y, d2x)) < 0; }


## Convex Hull

vector<point> CH(vector<point> P) {
int i, j, n = (int)P.size();
if (n <= 3) {
if (!(P[0] == P[n-1])) P.push_back(P[0]); // safeguard from corner case
return P;
}

// first, find P0 = point with lowest Y and if tie: rightmost X
int P0 = 0;
for (i = 1; i < n; i++)
if (P[i].y < P[P0].y || (P[i].y == P[P0].y && P[i].x > P[P0].x))
P0 = i;
point temp = P[0]; P[0] = P[P0]; P[P0] = temp; // swap P[P0] with P[0]
pivot = P[0];
sort(++P.begin(), P.end(), angleCmp);



## Convex Hull Code, 2

   vector<point> S;
S.push_back(P[n-1]); S.push_back(P[0]); S.push_back(P[1]);
i = 2;
while (i < n) {
// note: N must be >= 3 for this method to work
j = (int)S.size()-1;
if (ccw(S[j-1], S[j], P[i])) S.push_back(P[i++]); // left turn, accept
else S.pop_back();
}
return S;
}