EDIT

.idea

/*!

Copyright (c) The Cytoscape Consortium

Permission is hereby granted, free of charge, to any person obtaining a copy of

this software and associated documentation files (the “Software”), to deal in

the Software without restriction, including without limitation the rights to

use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies

of the Software, and to permit persons to whom the Software is furnished to do

so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all

copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED “AS IS”, WITHOUT WARRANTY OF ANY KIND, EXPRESS OR

IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,

FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE

AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER

LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,

OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE

SOFTWARE.

*/

;(function(){ 'use strict';

  // registers the extension on a cytoscape lib ref

  var register = function( cytoscape, dagre ){

    if( !cytoscape || !dagre ){ return; } // can't register if cytoscape unspecified

    var isFunction = function(o){ return typeof o === 'function'; };

    // default layout options

    var defaults = {

      // dagre algo options, uses default value on undefined

      nodeSep: undefined, // the separation between adjacent nodes in the same rank

      edgeSep: undefined, // the separation between adjacent edges in the same rank

      rankSep: undefined, // the separation between adjacent nodes in the same rank

      rankDir: undefined, // 'TB' for top to bottom flow, 'LR' for left to right

      minLen: function( edge ){ return 1; }, // number of ranks to keep between the source and target of the edge

      edgeWeight: function( edge ){ return 1; }, // higher weight edges are generally made shorter and straighter than lower weight edges

      // general layout options

      fit: true, // whether to fit to viewport

      padding: 30, // fit padding

      animate: false, // whether to transition the node positions

      animationDuration: 500, // duration of animation in ms if enabled

      animationEasing: undefined, // easing of animation if enabled

      boundingBox: undefined, // constrain layout bounds; { x1, y1, x2, y2 } or { x1, y1, w, h }

      ready: function(){}, // on layoutready

      stop: function(){} // on layoutstop

    };

    // constructor

    // options : object containing layout options

    function DagreLayout( options ){

      var opts = this.options = {};

      for( var i in defaults ){ opts[i] = defaults[i]; }

      for( var i in options ){ opts[i] = options[i]; }

    }

    // runs the layout

    DagreLayout.prototype.run = function(){

      var options = this.options;

      var layout = this;

      var cy = options.cy; // cy is automatically populated for us in the constructor

      var eles = options.eles;

      var getVal = function( ele, val ){

        return isFunction(val) ? val.apply( ele, [ ele ] ) : val;

      };

      var bb = options.boundingBox || { x1: 0, y1: 0, w: cy.width(), h: cy.height() };

      if( bb.x2 === undefined ){ bb.x2 = bb.x1 + bb.w; }

      if( bb.w === undefined ){ bb.w = bb.x2 - bb.x1; }

      if( bb.y2 === undefined ){ bb.y2 = bb.y1 + bb.h; }

      if( bb.h === undefined ){ bb.h = bb.y2 - bb.y1; }

      var g = new dagre.graphlib.Graph({

        multigraph: true,

        compound: true

      });

      var gObj = {};

      var setGObj = function( name, val ){

        if( val != null ){

          gObj[ name ] = val;

        }

      };

      setGObj( 'nodesep', options.nodeSep );

      setGObj( 'edgesep', options.edgeSep );

      setGObj( 'ranksep', options.rankSep );

      setGObj( 'rankdir', options.rankDir );

      g.setGraph( gObj );

      g.setDefaultEdgeLabel(function() { return {}; });

      g.setDefaultNodeLabel(function() { return {}; });

      // add nodes to dagre

      var nodes = eles.nodes();

      for( var i = 0; i < nodes.length; i++ ){

        var node = nodes[i];

        var nbb = node.boundingBox();

        g.setNode( node.id(), {

          width: nbb.w,

          height: nbb.h,

          name: node.id()

        } );

        // console.log( g.node(node.id()) );

      }

      // set compound parents

      for( var i = 0; i < nodes.length; i++ ){

        var node = nodes[i];

        if( node.isChild() ){

          g.setParent( node.id(), node.parent().id() );

        }

      }

      // add edges to dagre

      var edges = eles.edges().stdFilter(function( edge ){

        return !edge.source().isParent() && !edge.target().isParent(); // dagre can't handle edges on compound nodes

      });

      for( var i = 0; i < edges.length; i++ ){

        var edge = edges[i];

        g.setEdge( edge.source().id(), edge.target().id(), {

          minlen: getVal( edge, options.minLen ),

          weight: getVal( edge, options.edgeWeight ),

          name: edge.id()

        }, edge.id() );

        // console.log( g.edge(edge.source().id(), edge.target().id(), edge.id()) );

      }

      dagre.layout( g );

      var gNodeIds = g.nodes();

      for( var i = 0; i < gNodeIds.length; i++ ){

        var id = gNodeIds[i];

        var n = g.node( id );

        cy.getElementById(id).scratch().dagre = n;

      }

      var dagreBB;

      if( options.boundingBox ){

        dagreBB = { x1: Infinity, x2: -Infinity, y1: Infinity, y2: -Infinity };

        nodes.forEach(function( node ){

          var dModel = node.scratch().dagre;

          dagreBB.x1 = Math.min( dagreBB.x1, dModel.x );

          dagreBB.x2 = Math.max( dagreBB.x2, dModel.x );

          dagreBB.y1 = Math.min( dagreBB.y1, dModel.y );

          dagreBB.y2 = Math.max( dagreBB.y2, dModel.y );

        });

        dagreBB.w = dagreBB.x2 - dagreBB.x1;

        dagreBB.h = dagreBB.y2 - dagreBB.y1;

      } else {

        dagreBB = bb;

      }

      var constrainPos = function( p ){

        if( options.boundingBox ){

          var xPct = dagreBB.w === 0 ? 0 : (p.x - dagreBB.x1) / dagreBB.w;

          var yPct = dagreBB.h === 0 ? 0 : (p.y - dagreBB.y1) / dagreBB.h;

          return {

            x: bb.x1 + xPct * bb.w,

            y: bb.y1 + yPct * bb.h

          };

        } else {

          return p;

        }

      };

      nodes.layoutPositions(layout, options, function( ele ){

        ele = typeof ele === "object" ? ele : this;

        var dModel = ele.scratch().dagre;

        return constrainPos({

          x: dModel.x,

          y: dModel.y

        });

      });

      return this; // chaining

    };

    cytoscape('layout', 'dagre', DagreLayout);

  };

  if( typeof module !== 'undefined' && module.exports ){ // expose as a commonjs module

    module.exports = function( cytoscape, dagre ){

      register( cytoscape, dagre || require('dagre') );

    };

  } else if( typeof define !== 'undefined' && define.amd ){ // expose as an amd/requirejs module

    define('cytoscape-dagre', function(){

      return register;

    });

  }

  if( typeof cytoscape !== 'undefined' && typeof dagre !== 'undefined' ){ // expose to global cytoscape (i.e. window.cytoscape)

    register( cytoscape, dagre );

  }

})();

(function webpackUniversalModuleDefinition(root, factory) {

	if(typeof exports === 'object' && typeof module === 'object')

		module.exports = factory();

	else if(typeof define === 'function' && define.amd)

		define([], factory);

	else if(typeof exports === 'object')

		exports["cytoscape"] = factory();

	else

		root["cytoscape"] = factory();

})(typeof self !== 'undefined' ? self : this, function() {

return /******/ (function(modules) { // webpackBootstrap

/******/ 	// The module cache

/******/ 	var installedModules = {};

/******/

/******/ 	// The require function

/******/ 	function __webpack_require__(moduleId) {

/******/

/******/ 		// Check if module is in cache

/******/ 		if(installedModules[moduleId]) {

/******/ 			return installedModules[moduleId].exports;

/******/ 		}

/******/ 		// Create a new module (and put it into the cache)

/******/ 		var module = installedModules[moduleId] = {

/******/ 			i: moduleId,

/******/ 			l: false,

/******/ 			exports: {}

/******/ 		};

/******/

/******/ 		// Execute the module function

/******/ 		modules[moduleId].call(module.exports, module, module.exports, __webpack_require__);

/******/

/******/ 		// Flag the module as loaded

/******/ 		module.l = true;

/******/

/******/ 		// Return the exports of the module

/******/ 		return module.exports;

/******/ 	}

/******/

/******/

/******/ 	// expose the modules object (__webpack_modules__)

/******/ 	__webpack_require__.m = modules;

/******/

/******/ 	// expose the module cache

/******/ 	__webpack_require__.c = installedModules;

/******/

/******/ 	// define getter function for harmony exports

/******/ 	__webpack_require__.d = function(exports, name, getter) {

/******/ 		if(!__webpack_require__.o(exports, name)) {

/******/ 			Object.defineProperty(exports, name, {

/******/ 				configurable: false,

/******/ 				enumerable: true,

/******/ 				get: getter

/******/ 			});

/******/ 		}

/******/ 	};

/******/

/******/ 	// getDefaultExport function for compatibility with non-harmony modules

/******/ 	__webpack_require__.n = function(module) {

/******/ 		var getter = module && module.__esModule ?

/******/ 			function getDefault() { return module['default']; } :

/******/ 			function getModuleExports() { return module; };

/******/ 		__webpack_require__.d(getter, 'a', getter);

/******/ 		return getter;

/******/ 	};

/******/

/******/ 	// Object.prototype.hasOwnProperty.call

/******/ 	__webpack_require__.o = function(object, property) { return Object.prototype.hasOwnProperty.call(object, property); };

/******/

/******/ 	// __webpack_public_path__

/******/ 	__webpack_require__.p = "";

/******/

/******/ 	// Load entry module and return exports

/******/ 	return __webpack_require__(__webpack_require__.s = 20);

/******/ })

/************************************************************************/

/******/ ([

/* 0 */

/***/ (function(module, exports, __webpack_require__) {

"use strict";

var _typeof = typeof Symbol === "function" && typeof Symbol.iterator === "symbol" ? function (obj) { return typeof obj; } : function (obj) { return obj && typeof Symbol === "function" && obj.constructor === Symbol && obj !== Symbol.prototype ? "symbol" : typeof obj; };

/*global HTMLElement DocumentTouch */

var window = __webpack_require__(3);

var navigator = window ? window.navigator : null;

var document = window ? window.document : null;

var typeofstr = _typeof('');

var typeofobj = _typeof({});

var typeoffn = _typeof(function () {});

var typeofhtmlele = typeof HTMLElement === 'undefined' ? 'undefined' : _typeof(HTMLElement);

var instanceStr = function instanceStr(obj) {

  return obj && obj.instanceString && is.fn(obj.instanceString) ? obj.instanceString() : null;

};

var is = {

  defined: function defined(obj) {

    return obj != null; // not undefined or null

  },

  string: function string(obj) {

    return obj != null && (typeof obj === 'undefined' ? 'undefined' : _typeof(obj)) == typeofstr;

  },

  fn: function fn(obj) {

    return obj != null && (typeof obj === 'undefined' ? 'undefined' : _typeof(obj)) === typeoffn;

  },

  array: function array(obj) {

    return Array.isArray ? Array.isArray(obj) : obj != null && obj instanceof Array;

  },

  plainObject: function plainObject(obj) {

    return obj != null && (typeof obj === 'undefined' ? 'undefined' : _typeof(obj)) === typeofobj && !is.array(obj) && obj.constructor === Object;

  },

  object: function object(obj) {

    return obj != null && (typeof obj === 'undefined' ? 'undefined' : _typeof(obj)) === typeofobj;

  },

  number: function number(obj) {

    return obj != null && (typeof obj === 'undefined' ? 'undefined' : _typeof(obj)) === _typeof(1) && !isNaN(obj);

  },

  integer: function integer(obj) {

    return is.number(obj) && Math.floor(obj) === obj;

  },

  bool: function bool(obj) {

    return obj != null && (typeof obj === 'undefined' ? 'undefined' : _typeof(obj)) === _typeof(true);

  },

  htmlElement: function htmlElement(obj) {

    if ('undefined' === typeofhtmlele) {

      return undefined;

    } else {

      return null != obj && obj instanceof HTMLElement;

    }

  },

  elementOrCollection: function elementOrCollection(obj) {

    return is.element(obj) || is.collection(obj);

  },

  element: function element(obj) {

    return instanceStr(obj) === 'collection' && obj._private.single;

  },

  collection: function collection(obj) {

    return instanceStr(obj) === 'collection' && !obj._private.single;

  },

  core: function core(obj) {

    return instanceStr(obj) === 'core';

  },

  style: function style(obj) {

    return instanceStr(obj) === 'style';

  },

  stylesheet: function stylesheet(obj) {

    return instanceStr(obj) === 'stylesheet';

  },

  event: function event(obj) {

    return instanceStr(obj) === 'event';

  },

  thread: function thread(obj) {

    return instanceStr(obj) === 'thread';

  },

  fabric: function fabric(obj) {

    return instanceStr(obj) === 'fabric';

  },

  emptyString: function emptyString(obj) {

    if (obj === undefined || obj === null) {

      // null is empty

      return true;

    } else if (obj === '' || obj.match(/^\s+$/)) {

      return true; // empty string is empty

    }

    return false; // otherwise, we don't know what we've got

  },

  nonemptyString: function nonemptyString(obj) {

    if (obj && is.string(obj) && obj !== '' && !obj.match(/^\s+$/)) {

      return true;

    }

    return false;

  },

  domElement: function domElement(obj) {

    if (typeof HTMLElement === 'undefined') {

      return false; // we're not in a browser so it doesn't matter

    } else {

      return obj instanceof HTMLElement;

    }

  },

  boundingBox: function boundingBox(obj) {

    return is.plainObject(obj) && is.number(obj.x1) && is.number(obj.x2) && is.number(obj.y1) && is.number(obj.y2);

  },

  promise: function promise(obj) {

    return is.object(obj) && is.fn(obj.then);

  },

  touch: function touch() {

    return window && ('ontouchstart' in window || window.DocumentTouch && document instanceof DocumentTouch);

  },

  gecko: function gecko() {

    return window && (typeof InstallTrigger !== 'undefined' || 'MozAppearance' in document.documentElement.style);

  },

  webkit: function webkit() {

    return window && (typeof webkitURL !== 'undefined' || 'WebkitAppearance' in document.documentElement.style);

  },

  chromium: function chromium() {

    return window && typeof chrome !== 'undefined';

  },

  khtml: function khtml() {

    return navigator && navigator.vendor.match(/kde/i); // probably a better way to detect this...

  },

  khtmlEtc: function khtmlEtc() {

    return is.khtml() || is.webkit() || is.chromium();

  },

  ms: function ms() {

    return navigator && navigator.userAgent.match(/msie|trident|edge/i); // probably a better way to detect this...

  },

  windows: function windows() {

    return navigator && navigator.appVersion.match(/Win/i);

  },

  mac: function mac() {

    return navigator && navigator.appVersion.match(/Mac/i);

  },

  linux: function linux() {

    return navigator && navigator.appVersion.match(/Linux/i);

  },

  unix: function unix() {

    return navigator && navigator.appVersion.match(/X11/i);

  }

};

module.exports = is;

/***/ }),

/* 1 */

/***/ (function(module, exports, __webpack_require__) {

"use strict";

/*global console */

var is = __webpack_require__(0);

var math = __webpack_require__(2);

var util = {

  MAX_INT: Number.MAX_SAFE_INTEGER || 9007199254740991,

  trueify: function trueify() {

    return true;

  },

  falsify: function falsify() {

    return false;

  },

  zeroify: function zeroify() {

    return 0;

  },

  noop: function noop() {},

  error: function error(msg) {

    /* eslint-disable */

    if (console.error) {

      console.error.apply(console, arguments);

      if (console.trace) {

        console.trace();

      }

    } else {

      console.log.apply(console, arguments);

      if (console.trace) {

        console.trace();

      }

    }

    /* eslint-enable */

  },

  clone: function clone(obj) {

    return this.extend({}, obj);

  },

  // gets a shallow copy of the argument

  copy: function copy(obj) {

    if (obj == null) {

      return obj;

    }if (is.array(obj)) {

      return obj.slice();

    } else if (is.plainObject(obj)) {

      return this.clone(obj);

    } else {

      return obj;

    }

  },

  copyArray: function copyArray(arr) {

    return arr.slice();

  },

  clonePosition: function clonePosition(pos) {

    return { x: pos.x, y: pos.y };

  },

  uuid: function uuid(a, b // placeholders

  ) {

    for ( // loop :)

    b = a = ''; // b - result , a - numeric letiable

    a++ < 36; //

    b += a * 51 & 52 // if "a" is not 9 or 14 or 19 or 24

    ? //  return a random number or 4

    (a ^ 15 // if "a" is not 15

    ? // genetate a random number from 0 to 15

    8 ^ Math.random() * (a ^ 20 ? 16 : 4) // unless "a" is 20, in which case a random number from 8 to 11

    : 4 //  otherwise 4

    ).toString(16) : '-' //  in other cases (if "a" is 9,14,19,24) insert "-"

    ) {}

    return b;

  }

};

util.makeBoundingBox = math.makeBoundingBox.bind(math);

util._staticEmptyObject = {};

util.staticEmptyObject = function () {

  return util._staticEmptyObject;

};

util.extend = Object.assign != null ? Object.assign.bind(Object) : function (tgt) {

  var args = arguments;

  for (var i = 1; i < args.length; i++) {

    var obj = args[i];

    if (obj == null) {

      continue;

    }

    var keys = Object.keys(obj);

    for (var j = 0; j < keys.length; j++) {

      var k = keys[j];

      tgt[k] = obj[k];

    }

  }

  return tgt;

};

util.assign = util.extend;

util.default = function (val, def) {

  if (val === undefined) {

    return def;

  } else {

    return val;

  }

};

util.removeFromArray = function (arr, ele, manyCopies) {

  for (var i = arr.length; i >= 0; i--) {

    if (arr[i] === ele) {

      arr.splice(i, 1);

      if (!manyCopies) {

        break;

      }

    }

  }

};

util.clearArray = function (arr) {

  arr.splice(0, arr.length);

};

util.push = function (arr, otherArr) {

  for (var i = 0; i < otherArr.length; i++) {

    var el = otherArr[i];

    arr.push(el);

  }

};

util.getPrefixedProperty = function (obj, propName, prefix) {

  if (prefix) {

    propName = this.prependCamel(prefix, propName); // e.g. (labelWidth, source) => sourceLabelWidth

  }

  return obj[propName];

};

util.setPrefixedProperty = function (obj, propName, prefix, value) {

  if (prefix) {

    propName = this.prependCamel(prefix, propName); // e.g. (labelWidth, source) => sourceLabelWidth

  }

  obj[propName] = value;

};

[__webpack_require__(21), __webpack_require__(22), { memoize: __webpack_require__(13) }, __webpack_require__(23), __webpack_require__(24), __webpack_require__(25), __webpack_require__(27)].forEach(function (req) {

  util.extend(util, req);

});

module.exports = util;

/***/ }),

/* 2 */

/***/ (function(module, exports, __webpack_require__) {

"use strict";

var math = {};

math.arePositionsSame = function (p1, p2) {

  return p1.x === p2.x && p1.y === p2.y;

};

math.copyPosition = function (p) {

  return { x: p.x, y: p.y };

};

math.modelToRenderedPosition = function (p, zoom, pan) {

  return {

    x: p.x * zoom + pan.x,

    y: p.y * zoom + pan.y

  };

};

math.renderedToModelPosition = function (p, zoom, pan) {

  return {

    x: (p.x - pan.x) / zoom,

    y: (p.y - pan.y) / zoom

  };

};

math.array2point = function (arr) {

  return {

    x: arr[0],

    y: arr[1]

  };

};

math.deg2rad = function (deg) {

  return Math.PI * deg / 180;

};

math.getAngleFromDisp = function (dispX, dispY) {

  return Math.atan2(dispY, dispX) - Math.PI / 2;

};

math.log2 = Math.log2 || function (n) {

  return Math.log(n) / Math.log(2);

};

math.signum = function (x) {

  if (x > 0) {

    return 1;

  } else if (x < 0) {

    return -1;

  } else {

    return 0;

  }

};

math.dist = function (p1, p2) {

  return Math.sqrt(math.sqdist(p1, p2));

};

math.sqdist = function (p1, p2) {

  var dx = p2.x - p1.x;

  var dy = p2.y - p1.y;

  return dx * dx + dy * dy;

};

// from http://en.wikipedia.org/wiki/Bézier_curve#Quadratic_curves

math.qbezierAt = function (p0, p1, p2, t) {

  return (1 - t) * (1 - t) * p0 + 2 * (1 - t) * t * p1 + t * t * p2;

};

math.qbezierPtAt = function (p0, p1, p2, t) {

  return {

    x: math.qbezierAt(p0.x, p1.x, p2.x, t),

    y: math.qbezierAt(p0.y, p1.y, p2.y, t)

  };

};

math.lineAt = function (p0, p1, t, d) {

  var vec = {

    x: p1.x - p0.x,

    y: p1.y - p0.y

  };

  var vecDist = math.dist(p0, p1);

  var normVec = {

    x: vec.x / vecDist,

    y: vec.y / vecDist

  };

  t = t == null ? 0 : t;

  d = d != null ? d : t * vecDist;

  return {

    x: p0.x + normVec.x * d,

    y: p0.y + normVec.y * d

  };

};

math.lineAtDist = function (p0, p1, d) {

  return math.lineAt(p0, p1, undefined, d);

};

// get angle at A via cosine law

math.triangleAngle = function (A, B, C) {

  var a = math.dist(B, C);

  var b = math.dist(A, C);

  var c = math.dist(A, B);

  return Math.acos((a * a + b * b - c * c) / (2 * a * b));

};

math.bound = function (min, val, max) {

  return Math.max(min, Math.min(max, val));

};

// makes a full bb (x1, y1, x2, y2, w, h) from implicit params

math.makeBoundingBox = function (bb) {

  if (bb == null) {

    return {

      x1: Infinity,

      y1: Infinity,

      x2: -Infinity,

      y2: -Infinity,

      w: 0,

      h: 0

    };

  } else if (bb.x1 != null && bb.y1 != null) {

    if (bb.x2 != null && bb.y2 != null && bb.x2 >= bb.x1 && bb.y2 >= bb.y1) {

      return {

        x1: bb.x1,

        y1: bb.y1,

        x2: bb.x2,

        y2: bb.y2,

        w: bb.x2 - bb.x1,

        h: bb.y2 - bb.y1

      };

    } else if (bb.w != null && bb.h != null && bb.w >= 0 && bb.h >= 0) {

      return {

        x1: bb.x1,

        y1: bb.y1,

        x2: bb.x1 + bb.w,

        y2: bb.y1 + bb.h,

        w: bb.w,

        h: bb.h

      };

    }

  }

};

math.updateBoundingBox = function (bb1, bb2) {

  // update bb1 with bb2 bounds

  bb1.x1 = Math.min(bb1.x1, bb2.x1);

  bb1.x2 = Math.max(bb1.x2, bb2.x2);

  bb1.w = bb1.x2 - bb1.x1;

  bb1.y1 = Math.min(bb1.y1, bb2.y1);

  bb1.y2 = Math.max(bb1.y2, bb2.y2);

  bb1.h = bb1.y2 - bb1.y1;

};

math.expandBoundingBoxByPoint = function (bb, x, y) {

  bb.x1 = Math.min(bb.x1, x);

  bb.x2 = Math.max(bb.x2, x);

  bb.w = bb.x2 - bb.x1;

  bb.y1 = Math.min(bb.y1, y);

  bb.y2 = Math.max(bb.y2, y);

  bb.h = bb.y2 - bb.y1;

};

math.expandBoundingBox = function (bb, padding) {

  bb.x1 -= padding;

  bb.x2 += padding;

  bb.y1 -= padding;

  bb.y2 += padding;

  bb.w = bb.x2 - bb.x1;

  bb.h = bb.y2 - bb.y1;

  return bb;

};

math.boundingBoxesIntersect = function (bb1, bb2) {

  // case: one bb to right of other

  if (bb1.x1 > bb2.x2) {

    return false;

  }

  if (bb2.x1 > bb1.x2) {

    return false;

  }

  // case: one bb to left of other

  if (bb1.x2 < bb2.x1) {

    return false;

  }

  if (bb2.x2 < bb1.x1) {

    return false;

  }

  // case: one bb above other

  if (bb1.y2 < bb2.y1) {

    return false;

  }

  if (bb2.y2 < bb1.y1) {

    return false;

  }

  // case: one bb below other

  if (bb1.y1 > bb2.y2) {

    return false;

  }

  if (bb2.y1 > bb1.y2) {

    return false;

  }

  // otherwise, must have some overlap

  return true;

};

math.inBoundingBox = function (bb, x, y) {

  return bb.x1 <= x && x <= bb.x2 && bb.y1 <= y && y <= bb.y2;

};

math.pointInBoundingBox = function (bb, pt) {

  return this.inBoundingBox(bb, pt.x, pt.y);

};

math.boundingBoxInBoundingBox = function (bb1, bb2) {

  return math.inBoundingBox(bb1, bb2.x1, bb2.y1) && math.inBoundingBox(bb1, bb2.x2, bb2.y2);

};

math.roundRectangleIntersectLine = function (x, y, nodeX, nodeY, width, height, padding) {

  var cornerRadius = this.getRoundRectangleRadius(width, height);

  var halfWidth = width / 2;

  var halfHeight = height / 2;

  // Check intersections with straight line segments

  var straightLineIntersections = void 0;

  // Top segment, left to right

  {

    var topStartX = nodeX - halfWidth + cornerRadius - padding;

    var topStartY = nodeY - halfHeight - padding;

    var topEndX = nodeX + halfWidth - cornerRadius + padding;

    var topEndY = topStartY;

    straightLineIntersections = this.finiteLinesIntersect(x, y, nodeX, nodeY, topStartX, topStartY, topEndX, topEndY, false);

    if (straightLineIntersections.length > 0) {

      return straightLineIntersections;

    }

  }

  // Right segment, top to bottom

  {

    var rightStartX = nodeX + halfWidth + padding;

    var rightStartY = nodeY - halfHeight + cornerRadius - padding;

    var rightEndX = rightStartX;

    var rightEndY = nodeY + halfHeight - cornerRadius + padding;

    straightLineIntersections = this.finiteLinesIntersect(x, y, nodeX, nodeY, rightStartX, rightStartY, rightEndX, rightEndY, false);

    if (straightLineIntersections.length > 0) {

      return straightLineIntersections;

    }

  }

  // Bottom segment, left to right

  {

    var bottomStartX = nodeX - halfWidth + cornerRadius - padding;

    var bottomStartY = nodeY + halfHeight + padding;

    var bottomEndX = nodeX + halfWidth - cornerRadius + padding;

    var bottomEndY = bottomStartY;

    straightLineIntersections = this.finiteLinesIntersect(x, y, nodeX, nodeY, bottomStartX, bottomStartY, bottomEndX, bottomEndY, false);

    if (straightLineIntersections.length > 0) {

      return straightLineIntersections;

    }

  }

  // Left segment, top to bottom

  {

    var leftStartX = nodeX - halfWidth - padding;

    var leftStartY = nodeY - halfHeight + cornerRadius - padding;

    var leftEndX = leftStartX;

    var leftEndY = nodeY + halfHeight - cornerRadius + padding;

    straightLineIntersections = this.finiteLinesIntersect(x, y, nodeX, nodeY, leftStartX, leftStartY, leftEndX, leftEndY, false);

    if (straightLineIntersections.length > 0) {

      return straightLineIntersections;

    }

  }

  // Check intersections with arc segments

  var arcIntersections = void 0;

  // Top Left

  {

    var topLeftCenterX = nodeX - halfWidth + cornerRadius;

    var topLeftCenterY = nodeY - halfHeight + cornerRadius;

    arcIntersections = this.intersectLineCircle(x, y, nodeX, nodeY, topLeftCenterX, topLeftCenterY, cornerRadius + padding);

    // Ensure the intersection is on the desired quarter of the circle

    if (arcIntersections.length > 0 && arcIntersections[0] <= topLeftCenterX && arcIntersections[1] <= topLeftCenterY) {

      return [arcIntersections[0], arcIntersections[1]];

    }

  }

  // Top Right

  {

    var topRightCenterX = nodeX + halfWidth - cornerRadius;

    var topRightCenterY = nodeY - halfHeight + cornerRadius;

    arcIntersections = this.intersectLineCircle(x, y, nodeX, nodeY, topRightCenterX, topRightCenterY, cornerRadius + padding);

    // Ensure the intersection is on the desired quarter of the circle

    if (arcIntersections.length > 0 && arcIntersections[0] >= topRightCenterX && arcIntersections[1] <= topRightCenterY) {

      return [arcIntersections[0], arcIntersections[1]];

    }

  }

  // Bottom Right

  {

    var bottomRightCenterX = nodeX + halfWidth - cornerRadius;

    var bottomRightCenterY = nodeY + halfHeight - cornerRadius;

    arcIntersections = this.intersectLineCircle(x, y, nodeX, nodeY, bottomRightCenterX, bottomRightCenterY, cornerRadius + padding);

    // Ensure the intersection is on the desired quarter of the circle

    if (arcIntersections.length > 0 && arcIntersections[0] >= bottomRightCenterX && arcIntersections[1] >= bottomRightCenterY) {

      return [arcIntersections[0], arcIntersections[1]];

    }

  }

  // Bottom Left

  {

    var bottomLeftCenterX = nodeX - halfWidth + cornerRadius;

    var bottomLeftCenterY = nodeY + halfHeight - cornerRadius;

    arcIntersections = this.intersectLineCircle(x, y, nodeX, nodeY, bottomLeftCenterX, bottomLeftCenterY, cornerRadius + padding);

    // Ensure the intersection is on the desired quarter of the circle

    if (arcIntersections.length > 0 && arcIntersections[0] <= bottomLeftCenterX && arcIntersections[1] >= bottomLeftCenterY) {

      return [arcIntersections[0], arcIntersections[1]];

    }

  }

  return []; // if nothing

};

math.inLineVicinity = function (x, y, lx1, ly1, lx2, ly2, tolerance) {

  var t = tolerance;

  var x1 = Math.min(lx1, lx2);

  var x2 = Math.max(lx1, lx2);

  var y1 = Math.min(ly1, ly2);

  var y2 = Math.max(ly1, ly2);

  return x1 - t <= x && x <= x2 + t && y1 - t <= y && y <= y2 + t;

};

math.inBezierVicinity = function (x, y, x1, y1, x2, y2, x3, y3, tolerance) {

  var bb = {

    x1: Math.min(x1, x3, x2) - tolerance,

    x2: Math.max(x1, x3, x2) + tolerance,

    y1: Math.min(y1, y3, y2) - tolerance,

    y2: Math.max(y1, y3, y2) + tolerance

  };

  // if outside the rough bounding box for the bezier, then it can't be a hit

  if (x < bb.x1 || x > bb.x2 || y < bb.y1 || y > bb.y2) {

    // console.log('bezier out of rough bb')

    return false;

  } else {

    // console.log('do more expensive check');

    return true;

  }

};

math.solveQuadratic = function (a, b, c, val) {

  c -= val;

  var r = b * b - 4 * a * c;

  if (r < 0) {

    return [];

  }

  var sqrtR = Math.sqrt(r);

  var denom = 2 * a;

  var root1 = (-b + sqrtR) / denom;

  var root2 = (-b - sqrtR) / denom;

  return [root1, root2];

};

math.solveCubic = function (a, b, c, d, result) {

  // Solves a cubic function, returns root in form [r1, i1, r2, i2, r3, i3], where

  // r is the real component, i is the imaginary component

  // An implementation of the Cardano method from the year 1545

  // http://en.wikipedia.org/wiki/Cubic_function#The_nature_of_the_roots

  b /= a;

  c /= a;

  d /= a;

  var discriminant = void 0,

      q = void 0,

      r = void 0,

      dum1 = void 0,

      s = void 0,

      t = void 0,

      term1 = void 0,

      r13 = void 0;

  q = (3.0 * c - b * b) / 9.0;

  r = -(27.0 * d) + b * (9.0 * c - 2.0 * (b * b));

  r /= 54.0;

  discriminant = q * q * q + r * r;

  result[1] = 0;

  term1 = b / 3.0;

  if (discriminant > 0) {

    s = r + Math.sqrt(discriminant);

    s = s < 0 ? -Math.pow(-s, 1.0 / 3.0) : Math.pow(s, 1.0 / 3.0);

    t = r - Math.sqrt(discriminant);

    t = t < 0 ? -Math.pow(-t, 1.0 / 3.0) : Math.pow(t, 1.0 / 3.0);

    result[0] = -term1 + s + t;

    term1 += (s + t) / 2.0;

    result[4] = result[2] = -term1;

    term1 = Math.sqrt(3.0) * (-t + s) / 2;

    result[3] = term1;

    result[5] = -term1;

    return;

  }

  result[5] = result[3] = 0;

  if (discriminant === 0) {

    r13 = r < 0 ? -Math.pow(-r, 1.0 / 3.0) : Math.pow(r, 1.0 / 3.0);

    result[0] = -term1 + 2.0 * r13;

    result[4] = result[2] = -(r13 + term1);

    return;

  }

  q = -q;

  dum1 = q * q * q;

  dum1 = Math.acos(r / Math.sqrt(dum1));

  r13 = 2.0 * Math.sqrt(q);

  result[0] = -term1 + r13 * Math.cos(dum1 / 3.0);

  result[2] = -term1 + r13 * Math.cos((dum1 + 2.0 * Math.PI) / 3.0);

  result[4] = -term1 + r13 * Math.cos((dum1 + 4.0 * Math.PI) / 3.0);

  return;

};

math.sqdistToQuadraticBezier = function (x, y, x1, y1, x2, y2, x3, y3) {

  // Find minimum distance by using the minimum of the distance

  // function between the given point and the curve

  // This gives the coefficients of the resulting cubic equation

  // whose roots tell us where a possible minimum is

  // (Coefficients are divided by 4)

  var a = 1.0 * x1 * x1 - 4 * x1 * x2 + 2 * x1 * x3 + 4 * x2 * x2 - 4 * x2 * x3 + x3 * x3 + y1 * y1 - 4 * y1 * y2 + 2 * y1 * y3 + 4 * y2 * y2 - 4 * y2 * y3 + y3 * y3;

  var b = 1.0 * 9 * x1 * x2 - 3 * x1 * x1 - 3 * x1 * x3 - 6 * x2 * x2 + 3 * x2 * x3 + 9 * y1 * y2 - 3 * y1 * y1 - 3 * y1 * y3 - 6 * y2 * y2 + 3 * y2 * y3;

  var c = 1.0 * 3 * x1 * x1 - 6 * x1 * x2 + x1 * x3 - x1 * x + 2 * x2 * x2 + 2 * x2 * x - x3 * x + 3 * y1 * y1 - 6 * y1 * y2 + y1 * y3 - y1 * y + 2 * y2 * y2 + 2 * y2 * y - y3 * y;

  var d = 1.0 * x1 * x2 - x1 * x1 + x1 * x - x2 * x + y1 * y2 - y1 * y1 + y1 * y - y2 * y;

  // debug("coefficients: " + a / a + ", " + b / a + ", " + c / a + ", " + d / a);

  var roots = [];

  // Use the cubic solving algorithm

  this.solveCubic(a, b, c, d, roots);

  var zeroThreshold = 0.0000001;

  var params = [];

  for (var index = 0; index < 6; index += 2) {

    if (Math.abs(roots[index + 1]) < zeroThreshold && roots[index] >= 0 && roots[index] <= 1.0) {

      params.push(roots[index]);

    }

  }

  params.push(1.0);

  params.push(0.0);

  var minDistanceSquared = -1;

  var curX = void 0,

      curY = void 0,

      distSquared = void 0;

  for (var i = 0; i < params.length; i++) {

    curX = Math.pow(1.0 - params[i], 2.0) * x1 + 2.0 * (1 - params[i]) * params[i] * x2 + params[i] * params[i] * x3;

    curY = Math.pow(1 - params[i], 2.0) * y1 + 2 * (1.0 - params[i]) * params[i] * y2 + params[i] * params[i] * y3;

    distSquared = Math.pow(curX - x, 2) + Math.pow(curY - y, 2);

    // debug('distance for param ' + params[i] + ": " + Math.sqrt(distSquared));

    if (minDistanceSquared >= 0) {

      if (distSquared < minDistanceSquared) {

        minDistanceSquared = distSquared;

      }

    } else {

      minDistanceSquared = distSquared;

    }

  }

  return minDistanceSquared;

};

math.sqdistToFiniteLine = function (x, y, x1, y1, x2, y2) {

  var offset = [x - x1, y - y1];

  var line = [x2 - x1, y2 - y1];

  var lineSq = line[0] * line[0] + line[1] * line[1];

  var hypSq = offset[0] * offset[0] + offset[1] * offset[1];

  var dotProduct = offset[0] * line[0] + offset[1] * line[1];

  var adjSq = dotProduct * dotProduct / lineSq;

  if (dotProduct < 0) {

    return hypSq;

  }

  if (adjSq > lineSq) {

    return (x - x2) * (x - x2) + (y - y2) * (y - y2);

  }

  return hypSq - adjSq;

};

math.pointInsidePolygonPoints = function (x, y, points) {

  var x1 = void 0,

      y1 = void 0,

      x2 = void 0,

      y2 = void 0;

  var y3 = void 0;

  // Intersect with vertical line through (x, y)

  var up = 0;

  // let down = 0;

  for (var i = 0; i < points.length / 2; i++) {

    x1 = points[i * 2];

    y1 = points[i * 2 + 1];

    if (i + 1 < points.length / 2) {

      x2 = points[(i + 1) * 2];

      y2 = points[(i + 1) * 2 + 1];

    } else {

      x2 = points[(i + 1 - points.length / 2) * 2];

      y2 = points[(i + 1 - points.length / 2) * 2 + 1];

    }

    if (x1 == x && x2 == x) {

      // then ignore

    } else if (x1 >= x && x >= x2 || x1 <= x && x <= x2) {

      y3 = (x - x1) / (x2 - x1) * (y2 - y1) + y1;

      if (y3 > y) {

        up++;

      }

      // if( y3 < y ){

      // down++;

      // }

    } else {

      continue;

    }

  }

  if (up % 2 === 0) {

    return false;

  } else {

    return true;

  }

};

math.pointInsidePolygon = function (x, y, basePoints, centerX, centerY, width, height, direction, padding) {

  //let direction = arguments[6];

  var transformedPoints = new Array(basePoints.length);

  // Gives negative angle

  var angle = void 0;

  if (direction[0] != null) {

    angle = Math.atan(direction[1] / direction[0]);

    if (direction[0] < 0) {

      angle = angle + Math.PI / 2;

    } else {

      angle = -angle - Math.PI / 2;

    }

  } else {

    angle = direction;

  }

  var cos = Math.cos(-angle);

  var sin = Math.sin(-angle);

  //    console.log("base: " + basePoints);

  for (var i = 0; i < transformedPoints.length / 2; i++) {

    transformedPoints[i * 2] = width / 2 * (basePoints[i * 2] * cos - basePoints[i * 2 + 1] * sin);

    transformedPoints[i * 2 + 1] = height / 2 * (basePoints[i * 2 + 1] * cos + basePoints[i * 2] * sin);

    transformedPoints[i * 2] += centerX;

    transformedPoints[i * 2 + 1] += centerY;

  }

  var points = void 0;

  if (padding > 0) {

    var expandedLineSet = this.expandPolygon(transformedPoints, -padding);

    points = this.joinLines(expandedLineSet);

  } else {

    points = transformedPoints;

  }

  return math.pointInsidePolygonPoints(x, y, points);

};

math.joinLines = function (lineSet) {

  var vertices = new Array(lineSet.length / 2);

  var currentLineStartX = void 0,

      currentLineStartY = void 0,

      currentLineEndX = void 0,

      currentLineEndY = void 0;

  var nextLineStartX = void 0,

      nextLineStartY = void 0,

      nextLineEndX = void 0,

      nextLineEndY = void 0;

  for (var i = 0; i < lineSet.length / 4; i++) {

    currentLineStartX = lineSet[i * 4];

    currentLineStartY = lineSet[i * 4 + 1];

    currentLineEndX = lineSet[i * 4 + 2];

    currentLineEndY = lineSet[i * 4 + 3];

    if (i < lineSet.length / 4 - 1) {

      nextLineStartX = lineSet[(i + 1) * 4];

      nextLineStartY = lineSet[(i + 1) * 4 + 1];

      nextLineEndX = lineSet[(i + 1) * 4 + 2];

      nextLineEndY = lineSet[(i + 1) * 4 + 3];

    } else {

      nextLineStartX = lineSet[0];

      nextLineStartY = lineSet[1];

      nextLineEndX = lineSet[2];

      nextLineEndY = lineSet[3];

    }

    var intersection = this.finiteLinesIntersect(currentLineStartX, currentLineStartY, currentLineEndX, currentLineEndY, nextLineStartX, nextLineStartY, nextLineEndX, nextLineEndY, true);

    vertices[i * 2] = intersection[0];

    vertices[i * 2 + 1] = intersection[1];

  }

  return vertices;

};

math.expandPolygon = function (points, pad) {

  var expandedLineSet = new Array(points.length * 2);

  var currentPointX = void 0,

      currentPointY = void 0,

      nextPointX = void 0,

      nextPointY = void 0;

  for (var i = 0; i < points.length / 2; i++) {

    currentPointX = points[i * 2];

    currentPointY = points[i * 2 + 1];

    if (i < points.length / 2 - 1) {

      nextPointX = points[(i + 1) * 2];

      nextPointY = points[(i + 1) * 2 + 1];

    } else {

      nextPointX = points[0];

      nextPointY = points[1];

    }

    // Current line: [currentPointX, currentPointY] to [nextPointX, nextPointY]

    // Assume CCW polygon winding

    var offsetX = nextPointY - currentPointY;

    var offsetY = -(nextPointX - currentPointX);

    // Normalize

    var offsetLength = Math.sqrt(offsetX * offsetX + offsetY * offsetY);

    var normalizedOffsetX = offsetX / offsetLength;

    var normalizedOffsetY = offsetY / offsetLength;

    expandedLineSet[i * 4] = currentPointX + normalizedOffsetX * pad;

    expandedLineSet[i * 4 + 1] = currentPointY + normalizedOffsetY * pad;

    expandedLineSet[i * 4 + 2] = nextPointX + normalizedOffsetX * pad;

    expandedLineSet[i * 4 + 3] = nextPointY + normalizedOffsetY * pad;

  }

  return expandedLineSet;

};

math.intersectLineEllipse = function (x, y, centerX, centerY, ellipseWradius, ellipseHradius) {

  var dispX = centerX - x;

  var dispY = centerY - y;

  dispX /= ellipseWradius;

  dispY /= ellipseHradius;

  var len = Math.sqrt(dispX * dispX + dispY * dispY);

  var newLength = len - 1;

  if (newLength < 0) {

    return [];

  }

  var lenProportion = newLength / len;

  return [(centerX - x) * lenProportion + x, (centerY - y) * lenProportion + y];

};

math.checkInEllipse = function (x, y, width, height, centerX, centerY, padding) {

  x -= centerX;

  y -= centerY;

  x /= width / 2 + padding;

  y /= height / 2 + padding;

  return x * x + y * y <= 1;

};

// Returns intersections of increasing distance from line's start point

math.intersectLineCircle = function (x1, y1, x2, y2, centerX, centerY, radius) {

  // Calculate d, direction vector of line

  var d = [x2 - x1, y2 - y1]; // Direction vector of line

  var f = [x1 - centerX, y1 - centerY];

  var a = d[0] * d[0] + d[1] * d[1];

  var b = 2 * (f[0] * d[0] + f[1] * d[1]);

  var c = f[0] * f[0] + f[1] * f[1] - radius * radius;

  var discriminant = b * b - 4 * a * c;

  if (discriminant < 0) {

    return [];

  }

  var t1 = (-b + Math.sqrt(discriminant)) / (2 * a);

  var t2 = (-b - Math.sqrt(discriminant)) / (2 * a);

  var tMin = Math.min(t1, t2);

  var tMax = Math.max(t1, t2);

  var inRangeParams = [];

  if (tMin >= 0 && tMin <= 1) {

    inRangeParams.push(tMin);

  }

  if (tMax >= 0 && tMax <= 1) {

    inRangeParams.push(tMax);

  }

  if (inRangeParams.length === 0) {

    return [];

  }

  var nearIntersectionX = inRangeParams[0] * d[0] + x1;

  var nearIntersectionY = inRangeParams[0] * d[1] + y1;

  if (inRangeParams.length > 1) {

    if (inRangeParams[0] == inRangeParams[1]) {

      return [nearIntersectionX, nearIntersectionY];

    } else {

      var farIntersectionX = inRangeParams[1] * d[0] + x1;

      var farIntersectionY = inRangeParams[1] * d[1] + y1;

      return [nearIntersectionX, nearIntersectionY, farIntersectionX, farIntersectionY];

    }

  } else {

    return [nearIntersectionX, nearIntersectionY];

  }

};

math.findCircleNearPoint = function (centerX, centerY, radius, farX, farY) {

  var displacementX = farX - centerX;

  var displacementY = farY - centerY;

  var distance = Math.sqrt(displacementX * displacementX + displacementY * displacementY);

  var unitDisplacementX = displacementX / distance;

  var unitDisplacementY = displacementY / distance;

  return [centerX + unitDisplacementX * radius, centerY + unitDisplacementY * radius];

};