Generate simple polygons

createNonIntersectingPolygon.js

/**
 * Calculates if a given point `point` lies above a given line `p1p2`
 * THIS FUNCTION DOES NOT RETURN BOOLEANS. It has three different return values, above = 1, below = -1, on the line = 0.
 * @param  {[x, y]} point The point to test for
 * @param  {[x, y]} p1    The starting point of a line
 * @param  {[x, y]} p2    The ending point of a line
 * @return {number}       1 = above, -1 = below, 0 = exactly on the line
 */
function pointAboveLine(point, p1, p2) {
    // first, horizontally sort the points in the line
    let first;
    let second;

    if (p1[0] > p2[0]) {
        first = p2;
        second = p1;
    } else {
        first = p1;
        second = p2;
    }

    let v1 = [second[0] - first[0], second[1] - first[1]];
    let v2 = [second[0] - point[0], second[1] - point[1]];
    let xp = v1[0] * v2[1] - v1[1] * v2[0];

    // above
    if (xp > 0) {
        return 1;
    }
    // below
    else if (xp < 0) {
        return -1;
    }
    // exactly on the line
    else {
        return 0;
    }
}

/**
 * Takes any representation of a point and transforms it into the representation
 * this geometry library understands
 *
 * @example
 * point(5, 5)         => [5, 5]
 * point({x: 5, y: 5}) => [5, 5]
 * point([5, 5])       => [5, 5]
 *
 * @return {[x, y]} A point representation understood by this geometry library
 */
function point () {
    if (arguments.length === 1) {
        // either object or array
        if (arguments[0].length !== undefined) {
            // it's an array
            return arguments[0];
        }
        return [arguments[0].x, arguments[0].y];
    } else if (arguments.length === 2) {
        // point(x, y)
        return [arguments[0], arguments[1]];
    }
}

let geometry = {
    point: point,
    pointAboveLine: pointAboveLine
}

function findSmallest (array, key) {
    if (key === undefined) {
        key = function (value) {
            return value;
        };
    }
    return array.reduce(function (a, b, i, arr) {
        if (Math.min(key(a), key(b)) === key(a)) {
            return a;
        } else {
            return b;
        }
    }, Infinity);
}

function findLargest (array, key) {
    if (key === undefined) {
        key = function (value) {
            return value;
        };
    }
    return array.reduce(function (a, b, i, arr) {
        if (Math.max(key(a), key(b)) === key(a)) {
            return a;
        } else {
            return b;
        }
    }, Infinity);
}

function createNonIntersectingPolygon(initialPoints, amountOfPoints, minimumArea, maximumArea) {
    let remainingPoints = amountOfPoints - initialPoints.length;

    // algorithm to generate non intersecting polygons
    // http://stackoverflow.com/a/20623817/2302759

    // This way of generating new points is beyond bad
    // both the minimum and maximum area constraints are not satisfied
    // and all polygons end up biased to the right, this is because that made sense for my application
    // please take the time to find a better way to do this
    let lmax = Math.sqrt(maximumArea);
    let points = initialPoints;
    for (var i = 0; i < remainingPoints; i++) {
        points.push({
            x: initialPoints[0].x + ((Math.random() - 0.5) * 2) * lmax,
            y: initialPoints[0].y + Math.random() * lmax
        });
    }

    // (1) find the leftmost point p
    let leftmost = findSmallest(points, (point) => point.x);
    // (2) find rightmost point q
    let rightmost = findLargest(points, (point) => point.x);

    // (3) Partition the points into A, the set of points below pq
    //     and B, the set of points above pq
    let A = points.filter(function (point) {
        return geometry.pointAboveLine(geometry.point(point), geometry.point(leftmost), geometry.point(rightmost)) === -1;
    });
    let B = points.filter(function (point) {
        return geometry.pointAboveLine(geometry.point(point), geometry.point(leftmost), geometry.point(rightmost)) === 1;
    });

    // (4) sort A by increasing x-coordinates
    A = A.sort((p1, p2) => p1.x - p2.x);

    // (5) sort B by decreasing x-coordinates
    B = B.sort((p1, p2) => p2.x - p1.x);

    // (6) assemble a polygon in this order [p, ...A, q, ...B];

    return [leftmost, ...A, rightmost, ...B];
}