text: /**
  * The `Matter.Vertices` module contains methods for creating and manipulating sets of vertices.
  * A set of vertices is an array of `Matter.Vector` with additional indexing properties inserted by `Vertices.create`.
  * A `Matter.Body` maintains a set of vertices to represent the shape of the object (its convex hull).
  *
  * See the included usage [examples](https://github.com/liabru/matter-js/tree/master/examples).
  *
  * @class Vertices
  */
  
  var Vertices = {};
  
  module.exports = Vertices;
  
  var Vector = require('../geometry/Vector');
  var Common = require('../core/Common');
  
  (function() {
  
      /**
       * Creates a new set of `Matter.Body` compatible vertices.
       * The `points` argument accepts an array of `Matter.Vector` points orientated around the origin `(0, 0)`, for example:
       *
       *     [{ x: 0, y: 0 }, { x: 25, y: 50 }, { x: 50, y: 0 }]
       *
       * The `Vertices.create` method returns a new array of vertices, which are similar to Matter.Vector objects,
       * but with some additional references required for efficient collision detection routines.
       *
       * Vertices must be specified in clockwise order.
       *
       * Note that the `body` argument is not optional, a `Matter.Body` reference must be provided.
       *
       * @method create
       * @param {vector[]} points
       * @param {body} body
       */
      Vertices.create = function(points, body) {
          var vertices = [];
  
          for (var i = 0; i < points.length; i++) {
              var point = points[i],
                  vertex = {
                      x: point.x,
                      y: point.y,
                      index: i,
                      body: body,
                      isInternal: false
                  };
  
              vertices.push(vertex);
          }
  
          return vertices;
      };
  
      /**
       * Parses a string containing ordered x y pairs separated by spaces (and optionally commas),
       * into a `Matter.Vertices` object for the given `Matter.Body`.
       * For parsing SVG paths, see `Svg.pathToVertices`.
       * @method fromPath
       * @param {string} path
       * @param {body} body
       * @return {vertices} vertices
       */
      Vertices.fromPath = function(path, body) {
          var pathPattern = /L?\s*([\-\d\.e]+)[\s,]*([\-\d\.e]+)*/ig,
              points = [];
  
          path.replace(pathPattern, function(match, x, y) {
              points.push({ x: parseFloat(x), y: parseFloat(y) });
          });
  
          return Vertices.create(points, body);
      };
  
      /**
       * Returns the centre (centroid) of the set of vertices.
       * @method centre
       * @param {vertices} vertices
       * @return {vector} The centre point
       */
      Vertices.centre = function(vertices) {
          var area = Vertices.area(vertices, true),
              centre = { x: 0, y: 0 },
              cross,
              temp,
              j;
  
          for (var i = 0; i < vertices.length; i++) {
              j = (i + 1) % vertices.length;
              cross = Vector.cross(vertices[i], vertices[j]);
              temp = Vector.mult(Vector.add(vertices[i], vertices[j]), cross);
              centre = Vector.add(centre, temp);
          }
  
          return Vector.div(centre, 6 * area);
      };
  
      /**
       * Returns the average (mean) of the set of vertices.
       * @method mean
       * @param {vertices} vertices
       * @return {vector} The average point
       */
      Vertices.mean = function(vertices) {
          var average = { x: 0, y: 0 };
  
          for (var i = 0; i < vertices.length; i++) {
              average.x += vertices[i].x;
              average.y += vertices[i].y;
          }
  
          return Vector.div(average, vertices.length);
      };
  
      /**
       * Returns the area of the set of vertices.
       * @method area
       * @param {vertices} vertices
       * @param {bool} signed
       * @return {number} The area
       */
      Vertices.area = function(vertices, signed) {
          var area = 0,
              j = vertices.length - 1;
  
          for (var i = 0; i < vertices.length; i++) {
              area += (vertices[j].x - vertices[i].x) * (vertices[j].y + vertices[i].y);
              j = i;
          }
  
          if (signed)
              return area / 2;
  
          return Math.abs(area) / 2;
      };
  
      /**
       * Returns the moment of inertia (second moment of area) of the set of vertices given the total mass.
       * @method inertia
       * @param {vertices} vertices
       * @param {number} mass
       * @return {number} The polygon's moment of inertia
       */
      Vertices.inertia = function(vertices, mass) {
          var numerator = 0,
              denominator = 0,
              v = vertices,
              cross,
              j;
  
          // find the polygon's moment of inertia, using second moment of area
          // from equations at http://www.physicsforums.com/showthread.php?t=25293
          for (var n = 0; n < v.length; n++) {
              j = (n + 1) % v.length;
              cross = Math.abs(Vector.cross(v[j], v[n]));
              numerator += cross * (Vector.dot(v[j], v[j]) + Vector.dot(v[j], v[n]) + Vector.dot(v[n], v[n]));
              denominator += cross;
          }
  
          return (mass / 6) * (numerator / denominator);
      };
  
      /**
       * Translates the set of vertices in-place.
       * @method translate
       * @param {vertices} vertices
       * @param {vector} vector
       * @param {number} scalar
       */
      Vertices.translate = function(vertices, vector, scalar) {
          var i;
          if (scalar) {
              for (i = 0; i < vertices.length; i++) {
                  vertices[i].x += vector.x * scalar;
                  vertices[i].y += vector.y * scalar;
              }
          } else {
              for (i = 0; i < vertices.length; i++) {
                  vertices[i].x += vector.x;
                  vertices[i].y += vector.y;
              }
          }
  
          return vertices;
      };
  
      /**
       * Rotates the set of vertices in-place.
       * @method rotate
       * @param {vertices} vertices
       * @param {number} angle
       * @param {vector} point
       */
      Vertices.rotate = function(vertices, angle, point) {
          if (angle === 0)
              return;
  
          var cos = Math.cos(angle),
              sin = Math.sin(angle);
  
          for (var i = 0; i < vertices.length; i++) {
              var vertice = vertices[i],
                  dx = vertice.x - point.x,
                  dy = vertice.y - point.y;
  
              vertice.x = point.x + (dx * cos - dy * sin);
              vertice.y = point.y + (dx * sin + dy * cos);
          }
  
          return vertices;
      };
  
      /**
       * Returns `true` if the `point` is inside the set of `vertices`.
       * @method contains
       * @param {vertices} vertices
       * @param {vector} point
       * @return {boolean} True if the vertices contains point, otherwise false
       */
      Vertices.contains = function(vertices, point) {
          for (var i = 0; i < vertices.length; i++) {
              var vertice = vertices[i],
                  nextVertice = vertices[(i + 1) % vertices.length];
              if ((point.x - vertice.x) * (nextVertice.y - vertice.y) + (point.y - vertice.y) * (vertice.x - nextVertice.x) > 0) {
                  return false;
              }
          }
  
          return true;
      };
  
      /**
       * Scales the vertices from a point (default is centre) in-place.
       * @method scale
       * @param {vertices} vertices
       * @param {number} scaleX
       * @param {number} scaleY
       * @param {vector} point
       */
      Vertices.scale = function(vertices, scaleX, scaleY, point) {
          if (scaleX === 1 && scaleY === 1)
              return vertices;
  
          point = point || Vertices.centre(vertices);
  
          var vertex,
              delta;
  
          for (var i = 0; i < vertices.length; i++) {
              vertex = vertices[i];
              delta = Vector.sub(vertex, point);
              vertices[i].x = point.x + delta.x * scaleX;
              vertices[i].y = point.y + delta.y * scaleY;
          }
  
          return vertices;
      };
  
      /**
       * Chamfers a set of vertices by giving them rounded corners, returns a new set of vertices.
       * The radius parameter is a single number or an array to specify the radius for each vertex.
       * @method chamfer
       * @param {vertices} vertices
       * @param {number[]} radius
       * @param {number} quality
       * @param {number} qualityMin
       * @param {number} qualityMax
       */
      Vertices.chamfer = function(vertices, radius, quality, qualityMin, qualityMax) {
          radius = radius || [8];
  
          if (!radius.length)
              radius = [radius];
  
          // quality defaults to -1, which is auto
          quality = (typeof quality !== 'undefined') ? quality : -1;
          qualityMin = qualityMin || 2;
          qualityMax = qualityMax || 14;
  
          var newVertices = [];
  
          for (var i = 0; i < vertices.length; i++) {
              var prevVertex = vertices[i - 1 >= 0 ? i - 1 : vertices.length - 1],
                  vertex = vertices[i],
                  nextVertex = vertices[(i + 1) % vertices.length],
                  currentRadius = radius[i < radius.length ? i : radius.length - 1];
  
              if (currentRadius === 0) {
                  newVertices.push(vertex);
                  continue;
              }
  
              var prevNormal = Vector.normalise({
                  x: vertex.y - prevVertex.y,
                  y: prevVertex.x - vertex.x
              });
  
              var nextNormal = Vector.normalise({
                  x: nextVertex.y - vertex.y,
                  y: vertex.x - nextVertex.x
              });
  
              var diagonalRadius = Math.sqrt(2 * Math.pow(currentRadius, 2)),
                  radiusVector = Vector.mult(Common.clone(prevNormal), currentRadius),
                  midNormal = Vector.normalise(Vector.mult(Vector.add(prevNormal, nextNormal), 0.5)),
                  scaledVertex = Vector.sub(vertex, Vector.mult(midNormal, diagonalRadius));
  
              var precision = quality;
  
              if (quality === -1) {
                  // automatically decide precision
                  precision = Math.pow(currentRadius, 0.32) * 1.75;
              }
  
              precision = Common.clamp(precision, qualityMin, qualityMax);
  
              // use an even value for precision, more likely to reduce axes by using symmetry
              if (precision % 2 === 1)
                  precision += 1;
  
              var alpha = Math.acos(Vector.dot(prevNormal, nextNormal)),
                  theta = alpha / precision;
  
              for (var j = 0; j < precision; j++) {
                  newVertices.push(Vector.add(Vector.rotate(radiusVector, theta * j), scaledVertex));
              }
          }
  
          return newVertices;
      };
  
      /**
       * Sorts the input vertices into clockwise order in place.
       * @method clockwiseSort
       * @param {vertices} vertices
       * @return {vertices} vertices
       */
      Vertices.clockwiseSort = function(vertices) {
          var centre = Vertices.mean(vertices);
  
          vertices.sort(function(vertexA, vertexB) {
              return Vector.angle(centre, vertexA) - Vector.angle(centre, vertexB);
          });
  
          return vertices;
      };
  
      /**
       * Returns true if the vertices form a convex shape (vertices must be in clockwise order).
       * @method isConvex
       * @param {vertices} vertices
       * @return {bool} `true` if the `vertices` are convex, `false` if not (or `null` if not computable).
       */
      Vertices.isConvex = function(vertices) {
          // http://paulbourke.net/geometry/polygonmesh/
          // Copyright (c) Paul Bourke (use permitted)
  
          var flag = 0,
              n = vertices.length,
              i,
              j,
              k,
              z;
  
          if (n < 3)
              return null;
  
          for (i = 0; i < n; i++) {
              j = (i + 1) % n;
              k = (i + 2) % n;
              z = (vertices[j].x - vertices[i].x) * (vertices[k].y - vertices[j].y);
              z -= (vertices[j].y - vertices[i].y) * (vertices[k].x - vertices[j].x);
  
              if (z < 0) {
                  flag |= 1;
              } else if (z > 0) {
                  flag |= 2;
              }
  
              if (flag === 3) {
                  return false;
              }
          }
  
          if (flag !== 0){
              return true;
          } else {
              return null;
          }
      };
  
      /**
       * Returns the convex hull of the input vertices as a new array of points.
       * @method hull
       * @param {vertices} vertices
       * @return [vertex] vertices
       */
      Vertices.hull = function(vertices) {
          // http://geomalgorithms.com/a10-_hull-1.html
  
          var upper = [],
              lower = [],
              vertex,
              i;
  
          // sort vertices on x-axis (y-axis for ties)
          vertices = vertices.slice(0);
          vertices.sort(function(vertexA, vertexB) {
              var dx = vertexA.x - vertexB.x;
              return dx !== 0 ? dx : vertexA.y - vertexB.y;
          });
  
          // build lower hull
          for (i = 0; i < vertices.length; i += 1) {
              vertex = vertices[i];
  
              while (lower.length >= 2
                     && Vector.cross3(lower[lower.length - 2], lower[lower.length - 1], vertex) <= 0) {
                  lower.pop();
              }
  
              lower.push(vertex);
          }
  
          // build upper hull
          for (i = vertices.length - 1; i >= 0; i -= 1) {
              vertex = vertices[i];
  
              while (upper.length >= 2
                     && Vector.cross3(upper[upper.length - 2], upper[upper.length - 1], vertex) <= 0) {
                  upper.pop();
              }
  
              upper.push(vertex);
          }
  
          // concatenation of the lower and upper hulls gives the convex hull
          // omit last points because they are repeated at the beginning of the other list
          upper.pop();
          lower.pop();
  
          return upper.concat(lower);
      };
  
  })();
  