text: /**
   * Use cross product to judge the direction of the turn.
   * Returns a positive value, if OAB makes a clockwise turn,
   * negative for counter-clockwise turn, and zero if the points are collinear.
   */
  export var cross = function cross(a, b, o) {
    return (a.y - o.y) * (b.x - o.x) - (a.x - o.x) * (b.y - o.y);
  };
  /**
   * Generate a convex hull of given points. Andrew's monotone chain algorithm.
   * @param points An array of [x, y] representing the coordinates of points.
   * @return a list of vertices of the convex hull in counter-clockwise order,
   */
  
  export var genConvexHull = function genConvexHull(items) {
    var points = items.map(function (item) {
      return {
        x: item.getModel().x,
        y: item.getModel().y
      };
    });
    points.sort(function (a, b) {
      return a.x === b.x ? a.y - b.y : a.x - b.x;
    });
  
    if (points.length === 1) {
      return points;
    } // build the lower hull
  
  
    var lower = [];
  
    for (var i = 0; i < points.length; i++) {
      while (lower.length >= 2 && cross(lower[lower.length - 2], lower[lower.length - 1], points[i]) <= 0) {
        lower.pop();
      }
  
      lower.push(points[i]);
    } // build the upper hull
  
  
    var upper = [];
  
    for (var i = points.length - 1; i >= 0; i--) {
      while (upper.length >= 2 && cross(upper[upper.length - 2], upper[upper.length - 1], points[i]) <= 0) {
        upper.pop();
      }
  
      upper.push(points[i]);
    }
  
    upper.pop();
    lower.pop();
    var strictHull = lower.concat(upper);
    return strictHull;
  };