Polygons and Convex Hull

Mattox Beckman

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.

Example

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;
}