polygon.js

/**
* Copyright 2012-2017, Plotly, Inc.
* All rights reserved.
*
* This source code is licensed under the MIT license found in the
* LICENSE file in the root directory of this source tree.
*/


'use strict';

var dot = require('./matrix').dot;
var BADNUM = require('../constants/numerical').BADNUM;

var polygon = module.exports = {};

/**
 * Turn an array of [x, y] pairs into a polygon object
 * that can test if points are inside it
 *
 * @param ptsIn Array of [x, y] pairs
 *
 * @returns polygon Object {xmin, xmax, ymin, ymax, pts, contains}
 *      (x|y)(min|max) are the bounding rect of the polygon
 *      pts is the original array, with the first pair repeated at the end
 *      contains is a function: (pt, omitFirstEdge)
 *          pt is the [x, y] pair to test
 *          omitFirstEdge truthy means points exactly on the first edge don't
 *              count. This is for use adding one polygon to another so we
 *              don't double-count the edge where they meet.
 *          returns boolean: is pt inside the polygon (including on its edges)
 */
polygon.tester = function tester(ptsIn) {
    if(Array.isArray(ptsIn[0][0])) return polygon.multitester(ptsIn);

    var pts = ptsIn.slice(),
        xmin = pts[0][0],
        xmax = xmin,
        ymin = pts[0][1],
        ymax = ymin,
        i;

    pts.push(pts[0]);
    for(i = 1; i < pts.length; i++) {
        xmin = Math.min(xmin, pts[i][0]);
        xmax = Math.max(xmax, pts[i][0]);
        ymin = Math.min(ymin, pts[i][1]);
        ymax = Math.max(ymax, pts[i][1]);
    }

    // do we have a rectangle? Handle this here, so we can use the same
    // tester for the rectangular case without sacrificing speed

    var isRect = false,
        rectFirstEdgeTest;

    if(pts.length === 5) {
        if(pts[0][0] === pts[1][0]) { // vert, horz, vert, horz
            if(pts[2][0] === pts[3][0] &&
                    pts[0][1] === pts[3][1] &&
                    pts[1][1] === pts[2][1]) {
                isRect = true;
                rectFirstEdgeTest = function(pt) { return pt[0] === pts[0][0]; };
            }
        }
        else if(pts[0][1] === pts[1][1]) { // horz, vert, horz, vert
            if(pts[2][1] === pts[3][1] &&
                    pts[0][0] === pts[3][0] &&
                    pts[1][0] === pts[2][0]) {
                isRect = true;
                rectFirstEdgeTest = function(pt) { return pt[1] === pts[0][1]; };
            }
        }
    }

    function rectContains(pt, omitFirstEdge) {
        var x = pt[0],
            y = pt[1];

        if(x === BADNUM || x < xmin || x > xmax || y === BADNUM || y < ymin || y > ymax) {
            // pt is outside the bounding box of polygon
            return false;
        }
        if(omitFirstEdge && rectFirstEdgeTest(pt)) return false;

        return true;
    }

    function contains(pt, omitFirstEdge) {
        var x = pt[0],
            y = pt[1];

        if(x === BADNUM || x < xmin || x > xmax || y === BADNUM || y < ymin || y > ymax) {
            // pt is outside the bounding box of polygon
            return false;
        }

        var imax = pts.length,
            x1 = pts[0][0],
            y1 = pts[0][1],
            crossings = 0,
            i,
            x0,
            y0,
            xmini,
            ycross;

        for(i = 1; i < imax; i++) {
            // find all crossings of a vertical line upward from pt with
            // polygon segments
            // crossings exactly at xmax don't count, unless the point is
            // exactly on the segment, then it counts as inside.
            x0 = x1;
            y0 = y1;
            x1 = pts[i][0];
            y1 = pts[i][1];
            xmini = Math.min(x0, x1);

            // outside the bounding box of this segment, it's only a crossing
            // if it's below the box.
            if(x < xmini || x > Math.max(x0, x1) || y > Math.max(y0, y1)) {
                continue;
            }
            else if(y < Math.min(y0, y1)) {
                // don't count the left-most point of the segment as a crossing
                // because we don't want to double-count adjacent crossings
                // UNLESS the polygon turns past vertical at exactly this x
                // Note that this is repeated below, but we can't factor it out
                // because
                if(x !== xmini) crossings++;
            }
            // inside the bounding box, check the actual line intercept
            else {
                // vertical segment - we know already that the point is exactly
                // on the segment, so mark the crossing as exactly at the point.
                if(x1 === x0) ycross = y;
                // any other angle
                else ycross = y0 + (x - x0) * (y1 - y0) / (x1 - x0);

                // exactly on the edge: counts as inside the polygon, unless it's the
                // first edge and we're omitting it.
                if(y === ycross) {
                    if(i === 1 && omitFirstEdge) return false;
                    return true;
                }

                if(y <= ycross && x !== xmini) crossings++;
            }
        }

        // if we've gotten this far, odd crossings means inside, even is outside
        return crossings % 2 === 1;
    }

    // detect if poly is degenerate
    var degenerate = true;
    var lastPt = pts[0];
    for(i = 1; i < pts.length; i++) {
        if(lastPt[0] !== pts[i][0] || lastPt[1] !== pts[i][1]) {
            degenerate = false;
            break;
        }
    }

    return {
        xmin: xmin,
        xmax: xmax,
        ymin: ymin,
        ymax: ymax,
        pts: pts,
        contains: isRect ? rectContains : contains,
        isRect: isRect,
        degenerate: degenerate
    };
};

/**
 * Test multiple polygons
 */
polygon.multitester = function multitester(list) {
    var testers = [],
        xmin = list[0][0][0],
        xmax = xmin,
        ymin = list[0][0][1],
        ymax = ymin;

    for(var i = 0; i < list.length; i++) {
        var tester = polygon.tester(list[i]);
        tester.subtract = list[i].subtract;
        testers.push(tester);
        xmin = Math.min(xmin, tester.xmin);
        xmax = Math.max(xmax, tester.xmax);
        ymin = Math.min(ymin, tester.ymin);
        ymax = Math.max(ymax, tester.ymax);
    }

    function contains(pt, arg) {
        var yes = false;
        for(var i = 0; i < testers.length; i++) {
            if(testers[i].contains(pt, arg)) {
                // if contained by subtract polygon - exclude the point
                yes = testers[i].subtract === false;
            }
        }

        return yes;
    }

    return {
        xmin: xmin,
        xmax: xmax,
        ymin: ymin,
        ymax: ymax,
        pts: [],
        contains: contains,
        isRect: false,
        degenerate: false
    };
};

/**
 * Test if a segment of a points array is bent or straight
 *
 * @param pts Array of [x, y] pairs
 * @param start the index of the proposed start of the straight section
 * @param end the index of the proposed end point
 * @param tolerance the max distance off the line connecting start and end
 *      before the line counts as bent
 * @returns boolean: true means this segment is bent, false means straight
 */
var isBent = polygon.isSegmentBent = function isBent(pts, start, end, tolerance) {
    var startPt = pts[start],
        segment = [pts[end][0] - startPt[0], pts[end][1] - startPt[1]],
        segmentSquared = dot(segment, segment),
        segmentLen = Math.sqrt(segmentSquared),
        unitPerp = [-segment[1] / segmentLen, segment[0] / segmentLen],
        i,
        part,
        partParallel;

    for(i = start + 1; i < end; i++) {
        part = [pts[i][0] - startPt[0], pts[i][1] - startPt[1]];
        partParallel = dot(part, segment);

        if(partParallel < 0 || partParallel > segmentSquared ||
            Math.abs(dot(part, unitPerp)) > tolerance) return true;
    }
    return false;
};

/**
 * Make a filtering polygon, to minimize the number of segments
 *
 * @param pts Array of [x, y] pairs (must start with at least 1 pair)
 * @param tolerance the maximum deviation from straight allowed for
 *      removing points to simplify the polygon
 *
 * @returns Object {addPt, raw, filtered}
 *      addPt is a function(pt: [x, y] pair) to add a raw point and
 *          continue filtering
 *      raw is all the input points
 *      filtered is the resulting filtered Array of [x, y] pairs
 */
polygon.filter = function filter(pts, tolerance) {
    var ptsFiltered = [pts[0]],
        doneRawIndex = 0,
        doneFilteredIndex = 0;

    function addPt(pt) {
        pts.push(pt);
        var prevFilterLen = ptsFiltered.length,
            iLast = doneRawIndex;
        ptsFiltered.splice(doneFilteredIndex + 1);

        for(var i = iLast + 1; i < pts.length; i++) {
            if(i === pts.length - 1 || isBent(pts, iLast, i + 1, tolerance)) {
                ptsFiltered.push(pts[i]);
                if(ptsFiltered.length < prevFilterLen - 2) {
                    doneRawIndex = i;
                    doneFilteredIndex = ptsFiltered.length - 1;
                }
                iLast = i;
            }
        }
    }

    if(pts.length > 1) {
        var lastPt = pts.pop();
        addPt(lastPt);
    }

    return {
        addPt: addPt,
        raw: pts,
        filtered: ptsFiltered
    };
};