Show:

File: src/geometry/Vertices.js

                                /**
                                * 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) {
                                        scalar = typeof scalar !== 'undefined' ? scalar : 1;
                                
                                        var verticesLength = vertices.length,
                                            translateX = vector.x * scalar,
                                            translateY = vector.y * scalar,
                                            i;
                                        
                                        for (i = 0; i < verticesLength; i++) {
                                            vertices[i].x += translateX;
                                            vertices[i].y += translateY;
                                        }
                                
                                        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),
                                            pointX = point.x,
                                            pointY = point.y,
                                            verticesLength = vertices.length,
                                            vertex,
                                            dx,
                                            dy,
                                            i;
                                
                                        for (i = 0; i < verticesLength; i++) {
                                            vertex = vertices[i];
                                            dx = vertex.x - pointX;
                                            dy = vertex.y - pointY;
                                            vertex.x = pointX + (dx * cos - dy * sin);
                                            vertex.y = pointY + (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) {
                                        var pointX = point.x,
                                            pointY = point.y,
                                            verticesLength = vertices.length,
                                            vertex = vertices[verticesLength - 1],
                                            nextVertex;
                                
                                        for (var i = 0; i < verticesLength; i++) {
                                            nextVertex = vertices[i];
                                
                                            if ((pointX - vertex.x) * (nextVertex.y - vertex.y) 
                                                + (pointY - vertex.y) * (vertex.x - nextVertex.x) > 0) {
                                                return false;
                                            }
                                
                                            vertex = nextVertex;
                                        }
                                
                                        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) {
                                        if (typeof radius === 'number') {
                                            radius = [radius];
                                        } else {
                                            radius = radius || [8];
                                        }
                                
                                        // 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);
                                    };
                                
                                })();
                                
                                    
0.18.0