polygon.js

/*
 * GDevelop JS Platform
 * Copyright 2013-2016 Florian Rival (Florian.Rival@gmail.com). All rights reserved.
 * This project is released under the MIT License.
 */

/**
 * Polygon represents a polygon which can be used to create collisions masks for RuntimeObject.
 *
 * @memberof gdjs
 * @class Polygon
 */
gdjs.Polygon = function()
{
    /**
     * The vertices of the polygon
     * @member {Array}
     */
    this.vertices = [];

    /**
     * The edges of the polygon. This property is only valid after calling
     * computeEdges, and remains valid until vertices are modified.
     * @member {Array}
     */
    this.edges = [];

    /**
     * The center of the polygon. This property is only valid after calling
     * computeCenter, and remains valid until vertices are modified.
     * @member {Array}
     */
    this.center = [0,0];
};

gdjs.Polygon.prototype.move = function(x,y) {
	for(var i = 0, len = this.vertices.length;i<len;++i) {

		this.vertices[i][0] += x;
		this.vertices[i][1] += y;
	}
};

gdjs.Polygon.prototype.rotate = function(angle) {
	var t, cosa = Math.cos(-angle),
		sina = Math.sin(-angle); //We want a clockwise rotation

	for (var i = 0, len = this.vertices.length;i<len;++i) {
		t = this.vertices[i][0];
		this.vertices[i][0] = t*cosa + this.vertices[i][1]*sina;
		this.vertices[i][1] = -t*sina + this.vertices[i][1]*cosa;
	}
};

gdjs.Polygon.prototype.computeEdges = function() {
	var v1, v2;
	//Ensure edge array has the right size. ( And avoid recreating an edge array ).
	while ( this.edges.length < this.vertices.length ) {
		this.edges.push([0,0]);
	}
	if ( this.edges.length != this.vertices.length )
		this.edges.length = this.vertices.length;

	for (var i = 0, len = this.vertices.length;i<len;++i) {
		v1 = this.vertices[i];
		if ((i + 1) >= len) v2 = this.vertices[0];
		else v2 = this.vertices[i + 1];

		this.edges[i][0] = v2[0] - v1[0];
		this.edges[i][1] = v2[1] - v1[1];
	}
};

gdjs.Polygon.prototype.isConvex = function() {
	this.computeEdges();
	var edgesLen = this.edges.length;

	if ( edgesLen < 3 ) {
		return false;
	}

	var zProductIsPositive = (this.edges[0][0]*this.edges[0+1][1] - this.edges[0][1]*this.edges[0+1][0]) > 0;

	for (var i = 1;i<edgesLen-1;++i) {
		var zCrossProduct = this.edges[i][0]*this.edges[i+1][1] - this.edges[i][1]*this.edges[i+1][0];
		if ( (zCrossProduct > 0) !== zProductIsPositive ) return false;
	}

	var lastZCrossProduct = this.edges[edgesLen-1][0]*this.edges[0][1] - this.edges[edgesLen-1][1]*this.edges[0][0];
	if ( (lastZCrossProduct > 0) !== zProductIsPositive ) return false;

	return true;
};

gdjs.Polygon.prototype.computeCenter = function() {
	this.center[0] = 0;
	this.center[1] = 0;
	var len = this.vertices.length;

	for (var i = 0;i<len;++i) {
		this.center[0] += this.vertices[i][0];
		this.center[1] += this.vertices[i][1];
	}
	this.center[0] /= len;
	this.center[1] /= len;

	return this.center;
};

gdjs.Polygon.createRectangle = function(width, height) {
    var rect = new gdjs.Polygon();
    rect.vertices.push([-width/2.0, -height/2.0]);
    rect.vertices.push([+width/2.0, -height/2.0]);
    rect.vertices.push([+width/2.0, +height/2.0]);
    rect.vertices.push([-width/2.0, +height/2.0]);

    return rect;
};

/**
 * Do a collision test between two polygons.
 * Please note that polygons must *convexes*!
 *
 * Uses <a href="http://en.wikipedia.org/wiki/Hyperplane_separation_theorem">Separating Axis Theorem </a>.<br>
 * Based on <a href="http://www.codeproject.com/Articles/15573/2D-Polygon-Collision-Detection">this</a>
 * and <a href="http://stackoverflow.com/questions/5742329/problem-with-collision-response-sat">this</a> article.
 *
 * @return {{collision: boolean, move_axis: Array<number>}} returnValue.collision is equal to true if polygons are overlapping
 * @param {gdjs.Polygon} p1 The first polygon
 * @param {gdjs.Polygon} p2 The second polygon
 * @param {boolean | undefined} ignoreTouchingEdges If true, then edges that are touching each other, without the polygons actually overlapping, won't be considered in collision.
 */
gdjs.Polygon.collisionTest = function(p1, p2, ignoreTouchingEdges) {
    //Algorithm core :

    p1.computeEdges();
    p2.computeEdges();

    var edge = gdjs.Polygon.collisionTest._statics.edge;
    var move_axis = gdjs.Polygon.collisionTest._statics.move_axis;

    var result = gdjs.Polygon.collisionTest._statics.result;
    var minDist = Number.MAX_VALUE;

    edge[0] = 0;
    edge[1] = 0;
    edge[0] = 0;
    edge[1] = 0;

    result.collision = false;
    result.move_axis[0] = 0;
    result.move_axis[1] = 0;

    //Iterate over all the edges composing the polygons
    for (var i = 0, len1 = p1.vertices.length, len2 = p2.vertices.length; i < len1+len2; i++) {
        if (i < len1) { // or <=
            edge = p1.edges[i];
        } else {
            edge = p2.edges[i - len1];
        }

        var axis = gdjs.Polygon.collisionTest._statics.axis; //Get the axis to which polygons will be projected
				axis[0] = -edge[1];
				axis[1] = edge[0];
        gdjs.Polygon.normalise(axis);

				var minMaxA = gdjs.Polygon.collisionTest._statics.minMaxA;
				var minMaxB = gdjs.Polygon.collisionTest._statics.minMaxB;
        gdjs.Polygon.project(axis, p1, minMaxA); //Do projection on the axis.
        gdjs.Polygon.project(axis, p2, minMaxB);

        //If the projections on the axis do not overlap, then their is no collision
        var dist = gdjs.Polygon.distance(minMaxA[0], minMaxA[1], minMaxB[0], minMaxB[1]);
        if (dist > 0 || (dist === 0 && ignoreTouchingEdges)) {
            result.collision = false;
            result.move_axis[0] = 0;
            result.move_axis[1] = 0;
            return result;
        }

        var absDist = Math.abs(dist);

        if (absDist < minDist) {
            minDist = absDist;
            move_axis[0] = axis[0];
            move_axis[1] = axis[1];
        }
    }

    result.collision = true;

    //Ensure move axis is correctly oriented.
    var p1Center = p1.computeCenter();
    var p2Center = p2.computeCenter();
    var d = [p1Center[0]-p2Center[0], p1Center[1]-p2Center[1]];
    if (gdjs.Polygon.dotProduct(d, move_axis) < 0) {
        move_axis[0] = -move_axis[0];
        move_axis[1] = -move_axis[1];
    }

    //Add the magnitude to the move axis.
    result.move_axis[0] = move_axis[0] * minDist;
    result.move_axis[1] = move_axis[1] * minDist;

    return result;
};

//Arrays and data structure that are (re)used by gdjs.Polygon.collisionTest to
//avoid any allocation.
gdjs.Polygon.collisionTest._statics = {
	minMaxA: [0,0],
	minMaxB: [0,0],
	edge: [0,0],
	axis: [0,0],
	move_axis: [0,0],
	result: {
		collision:false,
		move_axis:[0,0]
	}
};

/**
 * Do a raycast test.<br>
 * Please note that the polygon must be <b>convex</b>!
 * 
 * For some theory, check <a href="https://www.codeproject.com/Tips/862988/Find-the-Intersection-Point-of-Two-Line-Segments">Find the Intersection Point of Two Line Segments</a>.
 *
 * @param {gdjs.Polygon} poly The polygon to test
 * @param {number} startX The raycast start point X
 * @param {number} startY The raycast start point Y
 * @param {number} endX The raycast end point X
 * @param {number} endY The raycast end point Y
 * @return A raycast result with the contact points and distances
 */
gdjs.Polygon.raycastTest = function(poly, startX, startY, endX, endY)
{
    var result = gdjs.Polygon.raycastTest._statics.result;
    result.collision = false;

    if ( poly.vertices.length < 2 )
    {
        return result;
    }

    poly.computeEdges();
    var p = gdjs.Polygon.raycastTest._statics.p;
    var q = gdjs.Polygon.raycastTest._statics.q;
    var r = gdjs.Polygon.raycastTest._statics.r;
    var s = gdjs.Polygon.raycastTest._statics.s;
    var minSqDist = Number.MAX_VALUE;

    // Ray segment: p + t*r, with p = start and r = end - start
    p[0] = startX;
    p[1] = startY;
    r[0] = endX - startX;
    r[1] = endY - startY;

    for(var i=0; i<poly.edges.length; i++)
    {
        // Edge segment: q + u*s
        q[0] = poly.vertices[i][0];
        q[1] = poly.vertices[i][1];
        s[0] = poly.edges[i][0];
        s[1] = poly.edges[i][1];
        var deltaQP = gdjs.Polygon.raycastTest._statics.deltaQP;
        deltaQP[0] = q[0] - p[0];
        deltaQP[1] = q[1] - p[1];
        var crossRS = gdjs.Polygon.crossProduct(r, s);
        var t = gdjs.Polygon.crossProduct(deltaQP, s) / crossRS;
        var u = gdjs.Polygon.crossProduct(deltaQP, r) / crossRS;

        // Collinear
        if ( Math.abs(crossRS) <= 0.0001 && Math.abs(gdjs.Polygon.crossProduct(deltaQP, r)) <= 0.0001 )
        {
            // Project the ray and the edge to work on floats, keeping linearity through t
            var axis = gdjs.Polygon.raycastTest._statics.axis;
            axis[0] = r[0];
            axis[1] = r[1];
            gdjs.Polygon.normalise(axis);
            var rayA = 0;
            var rayB = gdjs.Polygon.dotProduct(axis, r);
            var edgeA = gdjs.Polygon.dotProduct(axis, deltaQP);
            var edgeB = gdjs.Polygon.dotProduct(axis, [deltaQP[0] + s[0], deltaQP[1] + s[1]]);
            // Get overlapping range
            var minOverlap = Math.max(Math.min(rayA, rayB), Math.min(edgeA, edgeB));
            var maxOverlap = Math.min(Math.max(rayA, rayB), Math.max(edgeA, edgeB));
            if( minOverlap > maxOverlap ){
                return result;
            }
            result.collision = true;
            // Zero distance ray
            if( rayB === 0 ){
                result.closeX = startX;
                result.closeY = startY;
                result.closeSqDist = 0;
                result.farX = startX;
                result.farY = startY;
                result.farSqDist = 0;
            }
            var t1 = minOverlap / Math.abs(rayB);
            var t2 = maxOverlap / Math.abs(rayB);
            result.closeX = startX + t1*r[0];
            result.closeY = startY + t1*r[1];
            result.closeSqDist = t1*t1*(r[0]*r[0] + r[1]*r[1]);
            result.farX = startX + t2*r[0];
            result.farY = startY + t2*r[1];
            result.farSqDist = t2*t2*(r[0]*r[0] + r[1]*r[1]);

            return result;
        }
        // One point intersection
        else if ( crossRS !== 0 && 0<=t && t<=1 && 0<=u && u<=1 )
        {
            var x = p[0] + t*r[0];
            var y = p[1] + t*r[1];
            
            var sqDist = (x-startX)*(x-startX) + (y-startY)*(y-startY);
            if ( sqDist < minSqDist )
            {
                if ( !result.collision ){
                    result.farX = x;
                    result.farY = y;
                    result.farSqDist = sqDist;
                }
                minSqDist = sqDist;
                result.closeX = x;
                result.closeY = y;
                result.closeSqDist = sqDist;
                result.collision = true;
            }
            else
            {
                result.farX = x;
                result.farY = y;
                result.farSqDist = sqDist;
            }
        }
    }

    return result;
};

gdjs.Polygon.raycastTest._statics = {
    p: [0,0],
    q: [0,0],
    r: [0,0],
    s: [0,0],
    deltaQP: [0,0],
    axis: [0,0],
    result: {
        collision: false,
        closeX: 0,
        closeY: 0,
        closeSqDist: 0,
        farX: 0,
        farY: 0,
        farSqDist: 0
    }
}

//Tools functions :
gdjs.Polygon.normalise = function(v)
{
    var len = Math.sqrt(v[0]*v[0] + v[1]*v[1]);

    if (len != 0) {
        v[0] /= len;
        v[1] /= len;
    }
}

gdjs.Polygon.dotProduct = function(a, b)
{
    var dp = a[0]*b[0] + a[1]*b[1];

    return dp;
}

gdjs.Polygon.crossProduct = function(a, b)
{
    var cp = a[0]*b[1] - a[1]*b[0];

    return cp;
}

gdjs.Polygon.project = function(axis, p, result)
{
    var dp = gdjs.Polygon.dotProduct(axis, p.vertices[0]);
		result[0] = dp;
		result[1] = dp;

    for (var i = 1, len = p.vertices.length; i < len; ++i) {
        dp = gdjs.Polygon.dotProduct(axis, p.vertices[i]);

        if (dp < result[0])
            result[0] = dp;
        else if (dp > result[1])
            result[1] = dp;
    }
}

gdjs.Polygon.distance = function(minA, maxA, minB, maxB)
{
    if (minA < minB) return minB - maxA;
    else return minA - maxB;
}

/**
 * Check if a point is inside a polygon.
 *
 * Uses <a href="https://wrf.ecse.rpi.edu//Research/Short_Notes/pnpoly.html">PNPOLY</a> by W. Randolph Franklin.
 *
 * @param {gdjs.Polygon} poly The polygon to test
 * @param {number} x The point x coordinate
 * @param {number} y The point y coordinate
 * @return {boolean} true if the point is inside the polygon
 */
gdjs.Polygon.isPointInside = function(poly, x, y)
{
    var inside = false;
    var vi, vj;
    for (var i = 0, j = poly.vertices.length-1; i < poly.vertices.length; j = i++) {
        vi = poly.vertices[i];
        vj = poly.vertices[j];
        if ( ((vi[1]>y) != (vj[1]>y)) && (x < (vj[0]-vi[0]) * (y-vi[1]) / (vj[1]-vi[1]) + vi[0]) )
            inside = !inside;
    }

    return inside;
};