requirebin sketch

index.js

var fc = require('fc');
var center = require('ctx-translate-center');
var poly = require('ctx-render-polyline');
var points = require('ctx-render-points');
var bounds2 = require('2d-bounds');
var gridlines = require('ctx-render-grid-lines');
var isect = require('robust-segment-intersect');
var createSDF = require('sdf-polygon-2d');
var area = require('2d-polygon-area');
var segseg = require('segseg');
var sign = require('signum');

var TAU = Math.PI*2;
var min = Math.min;
var max = Math.max;
var abs = Math.abs;
var polyline = [
  [-10, -100],
  [-100, -100],
  [-100, -10],
  [-100, 100],
  [0, 0],

  [100, 0],
];


window.dump = function() {
  console.log(JSON.stringify(polyline, null, '  '))
}

function pointinbox(point, minx, miny, maxx, maxy) {
  var x = point[0];
  var y = point[1];
  return x >= minx && x <= maxx && y >= miny && y <= maxy;
}

function line(ctx, x1, y1, x2, y2, color) {
  ctx.beginPath();
    ctx.moveTo(x1, y1);
    ctx.lineTo(x2, y2);
    ctx.strokeStyle = color || "grey"
    ctx.stroke();
}

function midpoint(c, n) {
  return [(c[0] + n[0])/2, (c[1] + n[1])/2];
}

function closest(p, c, target) {

  var pd = Math.abs(p-target);
  var cd = Math.abs(c-target);

  return pd < cd ? 1 : 0;
}

var EPS = .000001;
function near(a, b) {
  return Math.abs(a-b) < EPS;
}

function vecNear(a, b) {
  return near(a[0], b[0]) && near(a[1], b[1]);
}


function gridfill(ctx, r, minx, miny, maxx, maxy, results) {
  var lx = min(minx, maxx);
  var ly = min(miny, maxy);
  var ux = max(minx, maxx);
  var uy = max(miny, maxy);

  var offset = 1;
  var offset2 = offset * 2
  var inside = 'hsla(114, 19%, 25%, 1)';
  var border = 'hsla(228, 19%, 25%, 1)';
  var outside = 'hsla(0, 19%, 25%, .7)';
  var sdf = createSDF([polyline])
  var block = [0, 0];
  var r2 = (r/2)|0;

  var contour = [];
  // a map of x,y => [index]
  var map = {}

  for (var x = lx; x < ux; x+=r) {
    for (var y = ly; y < uy; y+=r) {
      var oy = min(r - offset2, uy - y);
      var ox = min(r - offset2, ux - x);
      var dist = sdf(x + r2, y + r2);

      // TODO: test all 4 corners and see if an edge
      //       goes through this box.  If so, split the edge (how?)
      //       and continue on..

      var res = [false, false, false, false];

      /*
        test the corners of the box

        0-------1
        |       |
        |       |
        |       |
        3-------2
      */


      var tests = [[x, y], [x+r, y], [x+r, y+r], [x, y+r]];
      var potentialCrossings = [
        [0, 1],
        [1, 2],
        [2, 3],
        [3, 0],
      ];

      var distances = tests.map(function(a) {
        return sdf(a[0], a[1]);
      });


      var crossings = potentialCrossings.map(function(t) {
        if (sign(distances[t[0]] - r) !== sign(distances[t[1]] - r)) {
          return true;
        } else {
          return false;
        }
      })

      crossings.map(function(c, i) {
        if (c) {
          var edge = [[
            tests[potentialCrossings[i][0]][0],
            tests[potentialCrossings[i][0]][1],
            distances[potentialCrossings[i][0]]
          ],
          [
            tests[potentialCrossings[i][1]][0],
            tests[potentialCrossings[i][1]][1],
            distances[potentialCrossings[i][1]]
          ]];


          // bisect the quad edge to find the closest point to zero-crossing
          var ssss = 100, d = c, updateIndex;
          var lastDistance = Infinity;
          var mid;
          var midpointDistance;
          while(ssss--) {
            // bisect the quad current edge
            mid = midpoint(edge[0], edge[1]);
            midpointDistance = sdf(mid[0], mid[1]);
            if (Math.abs(midpointDistance - r) < .1 || midpointDistance > lastDistance) {
              found = true;
              ctx.beginPath()
              ctx.arc(mid[0], mid[1], 5, 0, Math.PI*2, false);
              ctx.strokeStyle = "green";
              ctx.stroke();

              contour.push([mid, x, y, midpointDistance]);
              break;
            }

            updateIndex = closest(edge[0][2], edge[1][2], r);
            edge[updateIndex][0] = mid[0];
            edge[updateIndex][1] = mid[1];
            edge[updateIndex][2] = midpointDistance;
          }

          if (ssss <= 0) {
            contour.push([mid, x, y, midpointDistance]);
            ctx.beginPath()
            ctx.arc(mid[0], mid[1], 5, 0, Math.PI*2, false);
            ctx.fillStyle = "orange";
            ctx.fill();
          }
        }
      })
    }
  }

  var gridpoints = {};

  var points = {};
  contour.forEach(function(point) {
    var gridkey = point[1] + ',' + point[2];
    if (!gridpoints[gridkey]) {
      gridpoints[gridkey] = [];
    }
    var local = gridpoints[gridkey];
    var found = false;
    for (var i = 0; i<local.length; i++) {
      var lp = local[i][0];
      if (vecNear(lp, point[0])) {
        return;
      }
    }

    gridpoints[gridkey].push(point);

    var p = point[0]
    var key = p[0] + ',' + p[1];
    if (!points[key]) {
      points[key] = 1;
    }
  });

  console.log(contour.length, Object.keys(points).length)

  Object.keys(gridpoints).map(function(key) {
    var pair = gridpoints[key];
    if (pair.length < 2) {
      return;
    }

    ctx.beginPath()
    ctx.moveTo(pair[0][0][0], pair[0][0][1]);
    pair.forEach(function(p, i) {
      ctx.lineTo(p[0][0], p[0][1]);
    });

    ctx.strokeStyle = 'red';
    ctx.stroke();
  })


  // TODO: join end to end these contours

  // poly(ctx, contour);
  // ctx.strokeStyle="green"
  // ctx.stroke();
}


var r = 20;
var b = [0, 0, 0, 0];
var ctx = fc(function() {
  ctx.clear();
  center(ctx);

  bounds2(polyline, b);

  b[0] = ((Math.floor(b[0]/r) * r) - r*2)|0;
  b[1] = ((Math.floor(b[1]/r) * r) - r*2)|0;
  b[2] = ((Math.ceil(b[2]/r) * r) + r*2)|0;
  b[3] = ((Math.ceil(b[3]/r) * r) + r*2)|0;

  var gridspacing = r;
  ctx.beginPath();
    gridlines(ctx, gridspacing, b[0], b[1], b[2], b[3]);
    ctx.strokeStyle = "rgba(222, 228, 244, .1)";
    ctx.stroke();

  ctx.strokeStyle = "grey";
  var pad = 3;
  ctx.strokeRect(b[0]-pad, b[1]-pad, Math.ceil(b[2] - b[0]) + pad*2, Math.ceil(b[3] - b[1]) + pad*2) ;
  var results = [];
  gridfill(ctx, gridspacing, b[0], b[1], b[2], b[3], results);

  ctx.beginPath();
    poly(ctx, polyline);
  ctx.closePath();
  ctx.strokeStyle = "hsl(17, 80%, 56%)";
  ctx.stroke();

  ctx.beginPath();
    points(ctx, 3, polyline)
    ctx.fillStyle = "hsl(49, 60%, 56%)";
    ctx.fill();

  if (mouse.dragging || mouse.near) {
    ctx.beginPath();
      var p = mouse.dragging === false ? mouse.near : mouse.down;
      var sr = 10;
      ctx.moveTo(p[0] + sr, p[1])
      ctx.arc(p[0], p[1], sr, 0, TAU, false);
      ctx.strokeStyle = 'hsl(49, 60%, 56%)';
      ctx.stroke();
  }
  results.forEach(function(seg) {
    if(seg.length < 2) {
      ctx.fillStyle = "red";
      ctx.fillRect(seg[0][2] + r/4, seg[0][3] + r/4, r/2, r/2);


      return;
    }
    ctx.strokeStyle = "green"
    line(ctx, seg[0][0], seg[0][1], seg[1][0], seg[1][1], 'red');

  });
});

var mouse = {
  down: false,
  dragging: false,
  near: false,
  pos: [0, 0]
};

function nearPolyline(mouse, polyline) {
  var m = mouse.pos;
  for (var i=0; i<polyline.length; i++) {
    var p = polyline[i];
    var dx = p[0]-m[0];
    var dy = p[1]-m[1];
    var d = Math.sqrt(dx*dx + dy*dy);

    if (d < min(10, r)) {
      return p;
    }
  }
  return false;
}

document.addEventListener('mousemove', function(ev) {
  mouse.pos[0] = ev.clientX - (ctx.canvas.width/2)|0;
  mouse.pos[1] = ev.clientY - (ctx.canvas.height/2)|0;

  if (mouse.down !== false) {
    if (!mouse.dragging) {
      mouse.dragging = true;
    } else {
      var p = mouse.down;
      p[0] = mouse.pos[0];
      p[1] = mouse.pos[1];
    }
  } else {
    mouse.near = nearPolyline(mouse, polyline);
  }
  ctx.dirty();
});

document.addEventListener('mouseup', function(ev) {
  mouse.down = false;
  mouse.dragging = false;
  ctx.dirty();
});

document.addEventListener('mousedown', function(ev) {
  mouse.down = nearPolyline(mouse, polyline);
});

minified.js

require=function e(t,n,r){function s(o,u){if(!n[o]){if(!t[o]){var a=typeof require=="function"&&require;if(!u&&a)return a(o,!0);if(i)return i(o,!0);var f=new Error("Cannot find module '"+o+"'");throw f.code="MODULE_NOT_FOUND",f}var l=n[o]={exports:{}};t[o][0].call(l.exports,function(e){var n=t[o][1][e];return s(n?n:e)},l,l.exports,e,t,n,r)}return n[o].exports}var i=typeof require=="function"&&require;for(var o=0;o<r.length;o++)s(r[o]);return s}({fc:[function(require,module,exports){(function(){var performance=window.performance||{};var performanceNow=performance.now||performance.now||performance.mozNow||performance.msNow||performance.oNow||performance.webkitNow||function(){return(new Date).getTime()};performanceNow=performanceNow.bind(performance);function fc(fn,autorun,dimensions){document.body.style.margin="0px";document.body.style.padding="0px";var canvas=document.createElement("canvas");document.body.appendChild(canvas);canvas.style.position="absolute";canvas.style.left="0px";canvas.style.top="0px";var ctx;dimensions=dimensions||2;if(dimensions===2){ctx=canvas.getContext("2d")}else if(dimensions===3){ctx=canvas.getContext("webgl")||canvas.getContext("experimental-webgl")}if(!ctx){return}var last=performanceNow(),request;function requestFrame(){if(request===null){request=requestAnimationFrame(tick)}}function tick(){request=null;var time=performanceNow();var delta=time-last;last=time;ctx.reset();dimensions===2&&ctx.save();fn&&fn.call(ctx,delta);dimensions===2&&ctx.restore();if(autorun){requestFrame()}}if(dimensions===2){ctx.reset=function fc_reset(){canvas.width=0;canvas.width=window.innerWidth;canvas.height=window.innerHeight};ctx.clear=function fc_clear(color){var orig=ctx.fillStyle;ctx.fillStyle=color||"#223";ctx.fillRect(0,0,canvas.width,canvas.height);ctx.fillStyle=orig}}else{ctx.reset=function fc_reset(){if(canvas.width!==window.innerWidth){canvas.width=window.innerWidth}if(canvas.height!==window.innerHeight){canvas.height=window.innerHeight}}}setTimeout(tick,0);ctx.dirty=function fc_dirty(){last=performanceNow();requestFrame()};ctx.stop=function fc_stop(){autorun=false;request&&cancelAnimationFrame(request);request=null};ctx.start=function fc_start(){autorun=true;requestFrame()};(window.attachEvent||window.addEventListener)("resize",ctx.dirty);ctx.reset();ctx.canvas=canvas;return ctx}if(typeof module!=="undefined"&&typeof module.exports!=="undefined"){module.exports=fc}if(typeof window!=="undefined"){window.fc=window.fc||fc}})()},{}]},{},[]);require=function e(t,n,r){function s(o,u){if(!n[o]){if(!t[o]){var a=typeof require=="function"&&require;if(!u&&a)return a(o,!0);if(i)return i(o,!0);var f=new Error("Cannot find module '"+o+"'");throw f.code="MODULE_NOT_FOUND",f}var l=n[o]={exports:{}};t[o][0].call(l.exports,function(e){var n=t[o][1][e];return s(n?n:e)},l,l.exports,e,t,n,r)}return n[o].exports}var i=typeof require=="function"&&require;for(var o=0;o<r.length;o++)s(r[o]);return s}({"ctx-translate-center":[function(require,module,exports){module.exports=center;function center(ctx){var w=ctx.canvas.width/2|0;var h=ctx.canvas.height/2|0;ctx.translate(w,h)}},{}]},{},[]);require=function e(t,n,r){function s(o,u){if(!n[o]){if(!t[o]){var a=typeof require=="function"&&require;if(!u&&a)return a(o,!0);if(i)return i(o,!0);var f=new Error("Cannot find module '"+o+"'");throw f.code="MODULE_NOT_FOUND",f}var l=n[o]={exports:{}};t[o][0].call(l.exports,function(e){var n=t[o][1][e];return s(n?n:e)},l,l.exports,e,t,n,r)}return n[o].exports}var i=typeof require=="function"&&require;for(var o=0;o<r.length;o++)s(r[o]);return s}({"ctx-render-polyline":[function(require,module,exports){module.exports=renderPolyline;function renderPolyline(ctx,a){var l=a.length;var a0=a[0];ctx.moveTo(a0[0],a0[1]);for(var i=1;i<l;i++){var c=a[i];ctx.lineTo(c[0],c[1])}}},{}]},{},[]);require=function e(t,n,r){function s(o,u){if(!n[o]){if(!t[o]){var a=typeof require=="function"&&require;if(!u&&a)return a(o,!0);if(i)return i(o,!0);var f=new Error("Cannot find module '"+o+"'");throw f.code="MODULE_NOT_FOUND",f}var l=n[o]={exports:{}};t[o][0].call(l.exports,function(e){var n=t[o][1][e];return s(n?n:e)},l,l.exports,e,t,n,r)}return n[o].exports}var i=typeof require=="function"&&require;for(var o=0;o<r.length;o++)s(r[o]);return s}({"ctx-render-points":[function(require,module,exports){var TAU=Math.PI*2;module.exports=renderPoints;function renderPoints(ctx,radius,array){var l=array.length;for(var i=0;i<l;i++){var point=array[i];var p0=point[0];var p1=point[1];ctx.moveTo(p0+radius,p1);ctx.arc(p0,p1,radius,0,TAU,false)}}},{}]},{},[]);require=function e(t,n,r){function s(o,u){if(!n[o]){if(!t[o]){var a=typeof require=="function"&&require;if(!u&&a)return a(o,!0);if(i)return i(o,!0);var f=new Error("Cannot find module '"+o+"'");throw f.code="MODULE_NOT_FOUND",f}var l=n[o]={exports:{}};t[o][0].call(l.exports,function(e){var n=t[o][1][e];return s(n?n:e)},l,l.exports,e,t,n,r)}return n[o].exports}var i=typeof require=="function"&&require;for(var o=0;o<r.length;o++)s(r[o]);return s}({"2d-bounds":[function(require,module,exports){module.exports=bounds2;var min=Math.min;var max=Math.max;function bounds2(array,out){out=out||[0,0,0,0];var lx=Infinity;var ly=Infinity;var ux=-Infinity;var uy=-Infinity;var l=array.length;for(var i=0;i<l;i++){var p=array[i];var x=p[0];var y=p[1];lx=min(lx,x);ux=max(ux,x);ly=min(ly,y);uy=max(uy,y)}out[0]=lx;out[1]=ly;out[2]=ux;out[3]=uy;return out}},{}]},{},[]);require=function e(t,n,r){function s(o,u){if(!n[o]){if(!t[o]){var a=typeof require=="function"&&require;if(!u&&a)return a(o,!0);if(i)return i(o,!0);var f=new Error("Cannot find module '"+o+"'");throw f.code="MODULE_NOT_FOUND",f}var l=n[o]={exports:{}};t[o][0].call(l.exports,function(e){var n=t[o][1][e];return s(n?n:e)},l,l.exports,e,t,n,r)}return n[o].exports}var i=typeof require=="function"&&require;for(var o=0;o<r.length;o++)s(r[o]);return s}({"ctx-render-grid-lines":[function(require,module,exports){module.exports=gridlines;var min=Math.min;var max=Math.max;var abs=Math.abs;function gridlines(ctx,spacing,minx,miny,maxx,maxy){var lx=min(minx,maxx);var ly=min(miny,maxy);var ux=max(minx,maxx);var uy=max(miny,maxy);spacing=abs(spacing|0);if(!spacing){return}for(var x=lx;x<=ux;x+=spacing){ctx.moveTo(x,ly);ctx.lineTo(x,uy)}for(var y=ly;y<=uy;y+=spacing){ctx.moveTo(lx,y);ctx.lineTo(ux,y)}}},{}]},{},[]);require=function e(t,n,r){function s(o,u){if(!n[o]){if(!t[o]){var a=typeof require=="function"&&require;if(!u&&a)return a(o,!0);if(i)return i(o,!0);var f=new Error("Cannot find module '"+o+"'");throw f.code="MODULE_NOT_FOUND",f}var l=n[o]={exports:{}};t[o][0].call(l.exports,function(e){var n=t[o][1][e];return s(n?n:e)},l,l.exports,e,t,n,r)}return n[o].exports}var i=typeof require=="function"&&require;for(var o=0;o<r.length;o++)s(r[o]);return s}({1:[function(require,module,exports){"use strict";module.exports=fastTwoSum;function fastTwoSum(a,b,result){var x=a+b;var bv=x-a;var av=x-bv;var br=b-bv;var ar=a-av;if(result){result[0]=ar+br;result[1]=x;return result}return[ar+br,x]}},{}],2:[function(require,module,exports){"use strict";var twoProduct=require("two-product");var twoSum=require("two-sum");module.exports=scaleLinearExpansion;function scaleLinearExpansion(e,scale){var n=e.length;if(n===1){var ts=twoProduct(e[0],scale);if(ts[0]){return ts}return[ts[1]]}var g=new Array(2*n);var q=[.1,.1];var t=[.1,.1];var count=0;twoProduct(e[0],scale,q);if(q[0]){g[count++]=q[0]}for(var i=1;i<n;++i){twoProduct(e[i],scale,t);var pq=q[1];twoSum(pq,t[0],q);if(q[0]){g[count++]=q[0]}var a=t[1];var b=q[1];var x=a+b;var bv=x-a;var y=b-bv;q[1]=x;if(y){g[count++]=y}}if(q[1]){g[count++]=q[1]}if(count===0){g[count++]=0}g.length=count;return g}},{"two-product":5,"two-sum":1}],3:[function(require,module,exports){"use strict";module.exports=robustSubtract;function scalarScalar(a,b){var x=a+b;var bv=x-a;var av=x-bv;var br=b-bv;var ar=a-av;var y=ar+br;if(y){return[y,x]}return[x]}function robustSubtract(e,f){var ne=e.length|0;var nf=f.length|0;if(ne===1&&nf===1){return scalarScalar(e[0],-f[0])}var n=ne+nf;var g=new Array(n);var count=0;var eptr=0;var fptr=0;var abs=Math.abs;var ei=e[eptr];var ea=abs(ei);var fi=-f[fptr];var fa=abs(fi);var a,b;if(ea<fa){b=ei;eptr+=1;if(eptr<ne){ei=e[eptr];ea=abs(ei)}}else{b=fi;fptr+=1;if(fptr<nf){fi=-f[fptr];fa=abs(fi)}}if(eptr<ne&&ea<fa||fptr>=nf){a=ei;eptr+=1;if(eptr<ne){ei=e[eptr];ea=abs(ei)}}else{a=fi;fptr+=1;if(fptr<nf){fi=-f[fptr];fa=abs(fi)}}var x=a+b;var bv=x-a;var y=b-bv;var q0=y;var q1=x;var _x,_bv,_av,_br,_ar;while(eptr<ne&&fptr<nf){if(ea<fa){a=ei;eptr+=1;if(eptr<ne){ei=e[eptr];ea=abs(ei)}}else{a=fi;fptr+=1;if(fptr<nf){fi=-f[fptr];fa=abs(fi)}}b=q0;x=a+b;bv=x-a;y=b-bv;if(y){g[count++]=y}_x=q1+x;_bv=_x-q1;_av=_x-_bv;_br=x-_bv;_ar=q1-_av;q0=_ar+_br;q1=_x}while(eptr<ne){a=ei;b=q0;x=a+b;bv=x-a;y=b-bv;if(y){g[count++]=y}_x=q1+x;_bv=_x-q1;_av=_x-_bv;_br=x-_bv;_ar=q1-_av;q0=_ar+_br;q1=_x;eptr+=1;if(eptr<ne){ei=e[eptr]}}while(fptr<nf){a=fi;b=q0;x=a+b;bv=x-a;y=b-bv;if(y){g[count++]=y}_x=q1+x;_bv=_x-q1;_av=_x-_bv;_br=x-_bv;_ar=q1-_av;q0=_ar+_br;q1=_x;fptr+=1;if(fptr<nf){fi=-f[fptr]}}if(q0){g[count++]=q0}if(q1){g[count++]=q1}if(!count){g[count++]=0}g.length=count;return g}},{}],4:[function(require,module,exports){"use strict";module.exports=linearExpansionSum;function scalarScalar(a,b){var x=a+b;var bv=x-a;var av=x-bv;var br=b-bv;var ar=a-av;var y=ar+br;if(y){return[y,x]}return[x]}function linearExpansionSum(e,f){var ne=e.length|0;var nf=f.length|0;if(ne===1&&nf===1){return scalarScalar(e[0],f[0])}var n=ne+nf;var g=new Array(n);var count=0;var eptr=0;var fptr=0;var abs=Math.abs;var ei=e[eptr];var ea=abs(ei);var fi=f[fptr];var fa=abs(fi);var a,b;if(ea<fa){b=ei;eptr+=1;if(eptr<ne){ei=e[eptr];ea=abs(ei)}}else{b=fi;fptr+=1;if(fptr<nf){fi=f[fptr];fa=abs(fi)}}if(eptr<ne&&ea<fa||fptr>=nf){a=ei;eptr+=1;if(eptr<ne){ei=e[eptr];ea=abs(ei)}}else{a=fi;fptr+=1;if(fptr<nf){fi=f[fptr];fa=abs(fi)}}var x=a+b;var bv=x-a;var y=b-bv;var q0=y;var q1=x;var _x,_bv,_av,_br,_ar;while(eptr<ne&&fptr<nf){if(ea<fa){a=ei;eptr+=1;if(eptr<ne){ei=e[eptr];ea=abs(ei)}}else{a=fi;fptr+=1;if(fptr<nf){fi=f[fptr];fa=abs(fi)}}b=q0;x=a+b;bv=x-a;y=b-bv;if(y){g[count++]=y}_x=q1+x;_bv=_x-q1;_av=_x-_bv;_br=x-_bv;_ar=q1-_av;q0=_ar+_br;q1=_x}while(eptr<ne){a=ei;b=q0;x=a+b;bv=x-a;y=b-bv;if(y){g[count++]=y}_x=q1+x;_bv=_x-q1;_av=_x-_bv;_br=x-_bv;_ar=q1-_av;q0=_ar+_br;q1=_x;eptr+=1;if(eptr<ne){ei=e[eptr]}}while(fptr<nf){a=fi;b=q0;x=a+b;bv=x-a;y=b-bv;if(y){g[count++]=y}_x=q1+x;_bv=_x-q1;_av=_x-_bv;_br=x-_bv;_ar=q1-_av;q0=_ar+_br;q1=_x;fptr+=1;if(fptr<nf){fi=f[fptr]}}if(q0){g[count++]=q0}if(q1){g[count++]=q1}if(!count){g[count++]=0}g.length=count;return g}},{}],5:[function(require,module,exports){"use strict";module.exports=twoProduct;var SPLITTER=+(Math.pow(2,27)+1);function twoProduct(a,b,result){var x=a*b;var c=SPLITTER*a;var abig=c-a;var ahi=c-abig;var alo=a-ahi;var d=SPLITTER*b;var bbig=d-b;var bhi=d-bbig;var blo=b-bhi;var err1=x-ahi*bhi;var err2=err1-alo*bhi;var err3=err2-ahi*blo;var y=alo*blo-err3;if(result){result[0]=y;result[1]=x;return result}return[y,x]}},{}],6:[function(require,module,exports){"use strict";var twoProduct=require("two-product");var robustSum=require("robust-sum");var robustScale=require("robust-scale");var robustSubtract=require("robust-subtract");var NUM_EXPAND=5;var EPSILON=1.1102230246251565e-16;var ERRBOUND3=(3+16*EPSILON)*EPSILON;var ERRBOUND4=(7+56*EPSILON)*EPSILON;function cofactor(m,c){var result=new Array(m.length-1);for(var i=1;i<m.length;++i){var r=result[i-1]=new Array(m.length-1);for(var j=0,k=0;j<m.length;++j){if(j===c){continue}r[k++]=m[i][j]}}return result}function matrix(n){var result=new Array(n);for(var i=0;i<n;++i){result[i]=new Array(n);for(var j=0;j<n;++j){result[i][j]=["m",j,"[",n-i-1,"]"].join("")}}return result}function sign(n){if(n&1){return"-"}return""}function generateSum(expr){if(expr.length===1){return expr[0]}else if(expr.length===2){return["sum(",expr[0],",",expr[1],")"].join("")}else{var m=expr.length>>1;return["sum(",generateSum(expr.slice(0,m)),",",generateSum(expr.slice(m)),")"].join("")}}function determinant(m){if(m.length===2){return[["sum(prod(",m[0][0],",",m[1][1],"),prod(-",m[0][1],",",m[1][0],"))"].join("")]}else{var expr=[];for(var i=0;i<m.length;++i){expr.push(["scale(",generateSum(determinant(cofactor(m,i))),",",sign(i),m[0][i],")"].join(""))}return expr}}function orientation(n){var pos=[];var neg=[];var m=matrix(n);var args=[];for(var i=0;i<n;++i){if((i&1)===0){pos.push.apply(pos,determinant(cofactor(m,i)))}else{neg.push.apply(neg,determinant(cofactor(m,i)))}args.push("m"+i)}var posExpr=generateSum(pos);var negExpr=generateSum(neg);var funcName="orientation"+n+"Exact";var code=["function ",funcName,"(",args.join(),"){var p=",posExpr,",n=",negExpr,",d=sub(p,n);return d[d.length-1];};return ",funcName].join("");var proc=new Function("sum","prod","scale","sub",code);return proc(robustSum,twoProduct,robustScale,robustSubtract)}var orientation3Exact=orientation(3);var orientation4Exact=orientation(4);var CACHED=[function orientation0(){return 0},function orientation1(){return 0},function orientation2(a,b){return b[0]-a[0]},function orientation3(a,b,c){var l=(a[1]-c[1])*(b[0]-c[0]);var r=(a[0]-c[0])*(b[1]-c[1]);var det=l-r;var s;if(l>0){if(r<=0){return det}else{s=l+r}}else if(l<0){if(r>=0){return det}else{s=-(l+r)}}else{return det}var tol=ERRBOUND3*s;if(det>=tol||det<=-tol){return det}return orientation3Exact(a,b,c)},function orientation4(a,b,c,d){var adx=a[0]-d[0];var bdx=b[0]-d[0];var cdx=c[0]-d[0];var ady=a[1]-d[1];var bdy=b[1]-d[1];var cdy=c[1]-d[1];var adz=a[2]-d[2];var bdz=b[2]-d[2];var cdz=c[2]-d[2];var bdxcdy=bdx*cdy;var cdxbdy=cdx*bdy;var cdxady=cdx*ady;var adxcdy=adx*cdy;var adxbdy=adx*bdy;var bdxady=bdx*ady;var det=adz*(bdxcdy-cdxbdy)+bdz*(cdxady-adxcdy)+cdz*(adxbdy-bdxady);var permanent=(Math.abs(bdxcdy)+Math.abs(cdxbdy))*Math.abs(adz)+(Math.abs(cdxady)+Math.abs(adxcdy))*Math.abs(bdz)+(Math.abs(adxbdy)+Math.abs(bdxady))*Math.abs(cdz);var tol=ERRBOUND4*permanent;if(det>tol||-det>tol){return det}return orientation4Exact(a,b,c,d)}];function slowOrient(args){var proc=CACHED[args.length];if(!proc){proc=CACHED[args.length]=orientation(args.length)}return proc.apply(undefined,args)}function generateOrientationProc(){while(CACHED.length<=NUM_EXPAND){CACHED.push(orientation(CACHED.length))}var args=[];var procArgs=["slow"];for(var i=0;i<=NUM_EXPAND;++i){args.push("a"+i);procArgs.push("o"+i)}var code=["function getOrientation(",args.join(),"){switch(arguments.length){case 0:case 1:return 0;"];for(var i=2;i<=NUM_EXPAND;++i){code.push("case ",i,":return o",i,"(",args.slice(0,i).join(),");")}code.push("}var s=new Array(arguments.length);for(var i=0;i<arguments.length;++i){s[i]=arguments[i]};return slow(s);}return getOrientation");procArgs.push(code.join(""));var proc=Function.apply(undefined,procArgs);module.exports=proc.apply(undefined,[slowOrient].concat(CACHED));for(var i=0;i<=NUM_EXPAND;++i){module.exports[i]=CACHED[i]}}generateOrientationProc()},{"robust-scale":2,"robust-subtract":3,"robust-sum":4,"two-product":5}],"robust-segment-intersect":[function(require,module,exports){"use strict";module.exports=segmentsIntersect;var orient=require("robust-orientation")[3];function checkCollinear(a0,a1,b0,b1){for(var d=0;d<2;++d){var x0=a0[d];var y0=a1[d];var l0=Math.min(x0,y0);var h0=Math.max(x0,y0);var x1=b0[d];var y1=b1[d];var l1=Math.min(x1,y1);var h1=Math.max(x1,y1);if(h1<l0||h0<l1){return false}}return true}function segmentsIntersect(a0,a1,b0,b1){var x0=orient(a0,b0,b1);var y0=orient(a1,b0,b1);if(x0>0&&y0>0||x0<0&&y0<0){return false}var x1=orient(b0,a0,a1);var y1=orient(b1,a0,a1);if(x1>0&&y1>0||x1<0&&y1<0){return false}if(x0===0&&y0===0&&x1===0&&y1===0){return checkCollinear(a0,a1,b0,b1)}return true}},{"robust-orientation":6}]},{},[]);require=function e(t,n,r){function s(o,u){if(!n[o]){if(!t[o]){var a=typeof require=="function"&&require;if(!u&&a)return a(o,!0);if(i)return i(o,!0);var f=new Error("Cannot find module '"+o+"'");throw f.code="MODULE_NOT_FOUND",f}var l=n[o]={exports:{}};t[o][0].call(l.exports,function(e){var n=t[o][1][e];return s(n?n:e)},l,l.exports,e,t,n,r)}return n[o].exports}var i=typeof require=="function"&&require;for(var o=0;o<r.length;o++)s(r[o]);return s}({1:[function(require,module,exports){var segseg=require("segseg");var preprocessPolygon=require("point-in-big-polygon");function Node(vec,alpha,intersection){this.vec=vec;this.alpha=alpha||0;this.intersect=!!intersection}Node.prototype={vec:null,next:null,next:null,prev:null,nextPoly:null,neighbor:null,intersect:null,entry:null,visited:false,alpha:0,nextNonIntersection:function nodeNextNonIntersection(){var a=this;while(a&&a.intersect){a=a.next}return a},last:function nodeLast(){var a=this;while(a.next&&a.next!==this){a=a.next}return a},createLoop:function nodeCreateLoop(){var last=this.last();last.prev.next=this;this.prev=last.prev},firstNodeOfInterest:function nodeFirstNodeOfInterest(){var a=this;if(a){do{a=a.next}while(a!==this&&(!a.intersect||a.intersect&&a.visited))}return a},insertBetween:function nodeInsertBetween(first,last){var a=first;while(a!==last&&a.alpha<this.alpha){a=a.next}this.next=a;this.prev=a.prev;if(this.prev){this.prev.next=this}this.next.prev=this}};function createLinkedList(vecs){var l=vecs.length;var ret,where;for(var i=0;i<l;i++){var current=vecs[i];if(!ret){where=ret=new Node(current)}else{where.next=new Node(current);where.next.prev=where;where=where.next}}return ret}function distance(v1,v2){var x=v1[0]-v2[0];var y=v1[1]-v2[1];return Math.sqrt(x*x+y*y)}function clean(array){var seen={};var cur=array.length-1;while(cur--){var c=array[cur];var p=array[cur+1];if(c[0]===p[0]&&c[1]===p[1]){array.splice(cur,1)}}return array}function identifyIntersections(subjectList,clipList){var subject,clip;var auxs=subjectList.last();auxs.next=new Node(subjectList.vec,auxs);auxs.next.prev=auxs;var auxc=clipList.last();auxc.next=new Node(clipList.vec,auxc);auxc.next.prev=auxc;for(subject=subjectList;subject.next;subject=subject.next){if(!subject.intersect){for(clip=clipList;clip.next;clip=clip.next){if(!clip.intersect){var a=subject.vec,b=subject.next.nextNonIntersection().vec,c=clip.vec,d=clip.next.nextNonIntersection().vec;var i=segseg(a,b,c,d);if(i&&i!==true){var intersectionSubject=new Node(i,distance(a,i)/distance(a,b),true);var intersectionClip=new Node(i,distance(c,i)/distance(c,d),true);intersectionSubject.neighbor=intersectionClip;intersectionClip.neighbor=intersectionSubject;intersectionSubject.insertBetween(subject,subject.next.nextNonIntersection());intersectionClip.insertBetween(clip,clip.next.nextNonIntersection())}}}}}}function identifyIntersectionType(subjectList,clipList,clipTest,subjectTest,type){var subject,clip;var se=clipTest(subjectList.vec)<0;if(type==="and"){se=!se}for(subject=subjectList;subject.next;subject=subject.next){if(subject.intersect){subject.entry=se;se=!se}}var ce=subjectTest(clipList.vec)>0;if(type==="or"){ce=!ce}for(clip=clipList;clip.next;clip=clip.next){if(clip.intersect){clip.entry=ce;ce=!ce}}}function collectClipResults(subjectList,clipList){subjectList.createLoop();clipList.createLoop();var crt,results=[],result;while((crt=subjectList.firstNodeOfInterest())!==subjectList){result=[];for(;!crt.visited;crt=crt.neighbor){result.push(crt.vec);var forward=crt.entry;while(true){crt.visited=true;crt=forward?crt.next:crt.prev;if(crt.intersect){crt.visited=true;break}else{result.push(crt.vec)}}}results.push(clean(result))}return results}function polygonBoolean(subjectPoly,clipPoly,operation){var subjectList=createLinkedList(subjectPoly);var clipList=createLinkedList(clipPoly);var clipContains=preprocessPolygon([clipPoly]);var subjectContains=preprocessPolygon([subjectPoly]);var subject,clip;var isects=identifyIntersections(subjectList,clipList);identifyIntersectionType(subjectList,clipList,clipContains,subjectContains,operation);return collectClipResults(subjectList,clipList)}module.exports=polygonBoolean},{"point-in-big-polygon":12,segseg:14}],2:[function(require,module,exports){"use strict";module.exports=fastTwoSum;function fastTwoSum(a,b,result){var x=a+b;var bv=x-a;var av=x-bv;var br=b-bv;var ar=a-av;if(result){result[0]=ar+br;result[1]=x;return result}return[ar+br,x]}},{}],3:[function(require,module,exports){"use strict";var twoProduct=require("two-product");var twoSum=require("two-sum");module.exports=scaleLinearExpansion;function scaleLinearExpansion(e,scale){var n=e.length;if(n===1){var ts=twoProduct(e[0],scale);if(ts[0]){return ts}return[ts[1]]}var g=new Array(2*n);var q=[.1,.1];var t=[.1,.1];var count=0;twoProduct(e[0],scale,q);if(q[0]){g[count++]=q[0]}for(var i=1;i<n;++i){twoProduct(e[i],scale,t);var pq=q[1];twoSum(pq,t[0],q);if(q[0]){g[count++]=q[0]}var a=t[1];var b=q[1];var x=a+b;var bv=x-a;var y=b-bv;q[1]=x;if(y){g[count++]=y}}if(q[1]){g[count++]=q[1]}if(count===0){g[count++]=0}g.length=count;return g}},{"two-product":6,"two-sum":2}],4:[function(require,module,exports){"use strict";module.exports=robustSubtract;function scalarScalar(a,b){var x=a+b;var bv=x-a;var av=x-bv;var br=b-bv;var ar=a-av;var y=ar+br;if(y){return[y,x]}return[x]}function robustSubtract(e,f){var ne=e.length|0;var nf=f.length|0;if(ne===1&&nf===1){return scalarScalar(e[0],-f[0])}var n=ne+nf;var g=new Array(n);var count=0;var eptr=0;var fptr=0;var abs=Math.abs;var ei=e[eptr];var ea=abs(ei);var fi=-f[fptr];var fa=abs(fi);var a,b;if(ea<fa){b=ei;eptr+=1;if(eptr<ne){ei=e[eptr];ea=abs(ei)}}else{b=fi;fptr+=1;if(fptr<nf){fi=-f[fptr];fa=abs(fi)}}if(eptr<ne&&ea<fa||fptr>=nf){a=ei;eptr+=1;if(eptr<ne){ei=e[eptr];ea=abs(ei)}}else{a=fi;fptr+=1;if(fptr<nf){fi=-f[fptr];fa=abs(fi)}}var x=a+b;var bv=x-a;var y=b-bv;var q0=y;var q1=x;var _x,_bv,_av,_br,_ar;while(eptr<ne&&fptr<nf){if(ea<fa){a=ei;eptr+=1;if(eptr<ne){ei=e[eptr];ea=abs(ei)}}else{a=fi;fptr+=1;if(fptr<nf){fi=-f[fptr];fa=abs(fi)}}b=q0;x=a+b;bv=x-a;y=b-bv;if(y){g[count++]=y}_x=q1+x;_bv=_x-q1;_av=_x-_bv;_br=x-_bv;_ar=q1-_av;q0=_ar+_br;q1=_x}while(eptr<ne){a=ei;b=q0;x=a+b;bv=x-a;y=b-bv;if(y){g[count++]=y}_x=q1+x;_bv=_x-q1;_av=_x-_bv;_br=x-_bv;_ar=q1-_av;q0=_ar+_br;q1=_x;eptr+=1;if(eptr<ne){ei=e[eptr]}}while(fptr<nf){a=fi;b=q0;x=a+b;bv=x-a;y=b-bv;if(y){g[count++]=y}_x=q1+x;_bv=_x-q1;_av=_x-_bv;_br=x-_bv;_ar=q1-_av;q0=_ar+_br;q1=_x;fptr+=1;if(fptr<nf){fi=-f[fptr]}}if(q0){g[count++]=q0}if(q1){g[count++]=q1}if(!count){g[count++]=0}g.length=count;return g}},{}],5:[function(require,module,exports){"use strict";module.exports=linearExpansionSum;function scalarScalar(a,b){var x=a+b;var bv=x-a;var av=x-bv;var br=b-bv;var ar=a-av;var y=ar+br;if(y){return[y,x]}return[x]}function linearExpansionSum(e,f){var ne=e.length|0;var nf=f.length|0;if(ne===1&&nf===1){return scalarScalar(e[0],f[0])}var n=ne+nf;var g=new Array(n);var count=0;var eptr=0;var fptr=0;var abs=Math.abs;var ei=e[eptr];var ea=abs(ei);var fi=f[fptr];var fa=abs(fi);var a,b;if(ea<fa){b=ei;eptr+=1;if(eptr<ne){ei=e[eptr];ea=abs(ei)}}else{b=fi;fptr+=1;if(fptr<nf){fi=f[fptr];fa=abs(fi)}}if(eptr<ne&&ea<fa||fptr>=nf){a=ei;eptr+=1;if(eptr<ne){ei=e[eptr];ea=abs(ei)}}else{a=fi;fptr+=1;if(fptr<nf){fi=f[fptr];fa=abs(fi)}}var x=a+b;var bv=x-a;var y=b-bv;var q0=y;var q1=x;var _x,_bv,_av,_br,_ar;while(eptr<ne&&fptr<nf){if(ea<fa){a=ei;eptr+=1;if(eptr<ne){ei=e[eptr];ea=abs(ei)}}else{a=fi;fptr+=1;if(fptr<nf){fi=f[fptr];fa=abs(fi)}}b=q0;x=a+b;bv=x-a;y=b-bv;if(y){g[count++]=y}_x=q1+x;_bv=_x-q1;_av=_x-_bv;_br=x-_bv;_ar=q1-_av;q0=_ar+_br;q1=_x}while(eptr<ne){a=ei;b=q0;x=a+b;bv=x-a;y=b-bv;if(y){g[count++]=y}_x=q1+x;_bv=_x-q1;_av=_x-_bv;_br=x-_bv;_ar=q1-_av;q0=_ar+_br;q1=_x;eptr+=1;if(eptr<ne){ei=e[eptr]}}while(fptr<nf){a=fi;b=q0;x=a+b;bv=x-a;y=b-bv;if(y){g[count++]=y}_x=q1+x;_bv=_x-q1;_av=_x-_bv;_br=x-_bv;_ar=q1-_av;q0=_ar+_br;q1=_x;fptr+=1;if(fptr<nf){fi=f[fptr]}}if(q0){g[count++]=q0}if(q1){g[count++]=q1}if(!count){g[count++]=0}g.length=count;return g}},{}],6:[function(require,module,exports){"use strict";module.exports=twoProduct;var SPLITTER=+(Math.pow(2,27)+1);function twoProduct(a,b,result){var x=a*b;var c=SPLITTER*a;var abig=c-a;var ahi=c-abig;var alo=a-ahi;var d=SPLITTER*b;var bbig=d-b;var bhi=d-bbig;var blo=b-bhi;var err1=x-ahi*bhi;var err2=err1-alo*bhi;var err3=err2-ahi*blo;var y=alo*blo-err3;if(result){result[0]=y;result[1]=x;return result}return[y,x]}},{}],7:[function(require,module,exports){"use strict";var twoProduct=require("two-product");var robustSum=require("robust-sum");var robustScale=require("robust-scale");var robustSubtract=require("robust-subtract");var NUM_EXPAND=5;var EPSILON=1.1102230246251565e-16;var ERRBOUND3=(3+16*EPSILON)*EPSILON;var ERRBOUND4=(7+56*EPSILON)*EPSILON;function cofactor(m,c){var result=new Array(m.length-1);for(var i=1;i<m.length;++i){var r=result[i-1]=new Array(m.length-1);for(var j=0,k=0;j<m.length;++j){if(j===c){continue}r[k++]=m[i][j]}}return result}function matrix(n){var result=new Array(n);for(var i=0;i<n;++i){result[i]=new Array(n);for(var j=0;j<n;++j){result[i][j]=["m",j,"[",n-i-1,"]"].join("")}}return result}function sign(n){if(n&1){return"-"}return""}function generateSum(expr){if(expr.length===1){return expr[0]}else if(expr.length===2){return["sum(",expr[0],",",expr[1],")"].join("")}else{var m=expr.length>>1;return["sum(",generateSum(expr.slice(0,m)),",",generateSum(expr.slice(m)),")"].join("")}}function determinant(m){if(m.length===2){return[["sum(prod(",m[0][0],",",m[1][1],"),prod(-",m[0][1],",",m[1][0],"))"].join("")]}else{var expr=[];for(var i=0;i<m.length;++i){expr.push(["scale(",generateSum(determinant(cofactor(m,i))),",",sign(i),m[0][i],")"].join(""))}return expr}}function orientation(n){var pos=[];var neg=[];var m=matrix(n);var args=[];for(var i=0;i<n;++i){if((i&1)===0){pos.push.apply(pos,determinant(cofactor(m,i)))}else{neg.push.apply(neg,determinant(cofactor(m,i)))}args.push("m"+i)}var posExpr=generateSum(pos);var negExpr=generateSum(neg);var funcName="orientation"+n+"Exact";var code=["function ",funcName,"(",args.join(),"){var p=",posExpr,",n=",negExpr,",d=sub(p,n);return d[d.length-1];};return ",funcName].join("");var proc=new Function("sum","prod","scale","sub",code);return proc(robustSum,twoProduct,robustScale,robustSubtract)}var orientation3Exact=orientation(3);var orientation4Exact=orientation(4);var CACHED=[function orientation0(){return 0},function orientation1(){return 0},function orientation2(a,b){return b[0]-a[0]},function orientation3(a,b,c){var l=(a[1]-c[1])*(b[0]-c[0]);var r=(a[0]-c[0])*(b[1]-c[1]);var det=l-r;var s;if(l>0){if(r<=0){return det}else{s=l+r}}else if(l<0){if(r>=0){return det}else{s=-(l+r)}}else{return det}var tol=ERRBOUND3*s;if(det>=tol||det<=-tol){return det}return orientation3Exact(a,b,c)},function orientation4(a,b,c,d){var adx=a[0]-d[0];var bdx=b[0]-d[0];var cdx=c[0]-d[0];var ady=a[1]-d[1];var bdy=b[1]-d[1];var cdy=c[1]-d[1];var adz=a[2]-d[2];var bdz=b[2]-d[2];var cdz=c[2]-d[2];var bdxcdy=bdx*cdy;var cdxbdy=cdx*bdy;var cdxady=cdx*ady;var adxcdy=adx*cdy;var adxbdy=adx*bdy;var bdxady=bdx*ady;var det=adz*(bdxcdy-cdxbdy)+bdz*(cdxady-adxcdy)+cdz*(adxbdy-bdxady);var permanent=(Math.abs(bdxcdy)+Math.abs(cdxbdy))*Math.abs(adz)+(Math.abs(cdxady)+Math.abs(adxcdy))*Math.abs(bdz)+(Math.abs(adxbdy)+Math.abs(bdxady))*Math.abs(cdz);var tol=ERRBOUND4*permanent;if(det>tol||-det>tol){return det}return orientation4Exact(a,b,c,d)}];function slowOrient(args){var proc=CACHED[args.length];if(!proc){proc=CACHED[args.length]=orientation(args.length)}return proc.apply(undefined,args)}function generateOrientationProc(){while(CACHED.length<=NUM_EXPAND){CACHED.push(orientation(CACHED.length))}var args=[];var procArgs=["slow"];for(var i=0;i<=NUM_EXPAND;++i){args.push("a"+i);procArgs.push("o"+i)}var code=["function getOrientation(",args.join(),"){switch(arguments.length){case 0:case 1:return 0;"];for(var i=2;i<=NUM_EXPAND;++i){code.push("case ",i,":return o",i,"(",args.slice(0,i).join(),");")}code.push("}var s=new Array(arguments.length);for(var i=0;i<arguments.length;++i){s[i]=arguments[i]};return slow(s);}return getOrientation");procArgs.push(code.join(""));var proc=Function.apply(undefined,procArgs);module.exports=proc.apply(undefined,[slowOrient].concat(CACHED));for(var i=0;i<=NUM_EXPAND;++i){module.exports[i]=CACHED[i]}}generateOrientationProc()},{"robust-scale":3,"robust-subtract":4,"robust-sum":5,"two-product":6}],8:[function(require,module,exports){"use strict";module.exports=orderSegments;var orient=require("robust-orientation");function horizontalOrder(a,b){var bl,br;if(b[0][0]<b[1][0]){bl=b[0];br=b[1]}else if(b[0][0]>b[1][0]){bl=b[1];br=b[0]}else{var alo=Math.min(a[0][1],a[1][1]);var ahi=Math.max(a[0][1],a[1][1]);var blo=Math.min(b[0][1],b[1][1]);var bhi=Math.max(b[0][1],b[1][1]);if(ahi<blo){return ahi-blo}if(alo>bhi){return alo-bhi}return ahi-bhi}var al,ar;if(a[0][1]<a[1][1]){al=a[0];ar=a[1]}else{al=a[1];ar=a[0]}var d=orient(br,bl,al);if(d){return d}d=orient(br,bl,ar);if(d){return d}return ar-br}function orderSegments(b,a){var al,ar;if(a[0][0]<a[1][0]){al=a[0];ar=a[1]}else if(a[0][0]>a[1][0]){al=a[1];ar=a[0]}else{return horizontalOrder(a,b)}var bl,br;if(b[0][0]<b[1][0]){bl=b[0];br=b[1]}else if(b[0][0]>b[1][0]){bl=b[1];br=b[0]}else{return-horizontalOrder(b,a)}var d1=orient(al,ar,br);var d2=orient(al,ar,bl);if(d1<0){if(d2<=0){return d1}}else if(d1>0){if(d2>=0){return d1}}else if(d2){return d2}d1=orient(br,bl,ar);d2=orient(br,bl,al);if(d1<0){if(d2<=0){return d1}}else if(d1>0){if(d2>=0){return d1}}else if(d2){return d2}return ar[0]-br[0]}},{"robust-orientation":7}],9:[function(require,module,exports){"use strict";function compileSearch(funcName,predicate,reversed,extraArgs,useNdarray,earlyOut){var code=["function ",funcName,"(a,l,h,",extraArgs.join(","),"){",earlyOut?"":"var i=",reversed?"l-1":"h+1",";while(l<=h){var m=(l+h)>>>1,x=a",useNdarray?".get(m)":"[m]"];if(earlyOut){if(predicate.indexOf("c")<0){code.push(";if(x===y){return m}else if(x<=y){")}else{code.push(";var p=c(x,y);if(p===0){return m}else if(p<=0){")}}else{code.push(";if(",predicate,"){i=m;")}if(reversed){code.push("l=m+1}else{h=m-1}")}else{code.push("h=m-1}else{l=m+1}")}code.push("}");if(earlyOut){code.push("return -1};")}else{code.push("return i};")}return code.join("")}function compileBoundsSearch(predicate,reversed,suffix,earlyOut){var result=new Function([compileSearch("A","x"+predicate+"y",reversed,["y"],false,earlyOut),compileSearch("B","x"+predicate+"y",reversed,["y"],true,earlyOut),compileSearch("P","c(x,y)"+predicate+"0",reversed,["y","c"],false,earlyOut),compileSearch("Q","c(x,y)"+predicate+"0",reversed,["y","c"],true,earlyOut),"function dispatchBsearch",suffix,"(a,y,c,l,h){if(a.shape){if(typeof(c)==='function'){return Q(a,(l===undefined)?0:l|0,(h===undefined)?a.shape[0]-1:h|0,y,c)}else{return B(a,(c===undefined)?0:c|0,(l===undefined)?a.shape[0]-1:l|0,y)}}else{if(typeof(c)==='function'){return P(a,(l===undefined)?0:l|0,(h===undefined)?a.length-1:h|0,y,c)}else{return A(a,(c===undefined)?0:c|0,(l===undefined)?a.length-1:l|0,y)}}}return dispatchBsearch",suffix].join(""));return result()}module.exports={ge:compileBoundsSearch(">=",false,"GE"),gt:compileBoundsSearch(">",false,"GT"),lt:compileBoundsSearch("<",true,"LT"),le:compileBoundsSearch("<=",true,"LE"),eq:compileBoundsSearch("-",true,"EQ",true)}},{}],10:[function(require,module,exports){"use strict";module.exports=createRBTree;var RED=0;var BLACK=1;function RBNode(color,key,value,left,right,count){this._color=color;this.key=key;this.value=value;this.left=left;this.right=right;this._count=count}function cloneNode(node){return new RBNode(node._color,node.key,node.value,node.left,node.right,node._count)}function repaint(color,node){return new RBNode(color,node.key,node.value,node.left,node.right,node._count)}function recount(node){node._count=1+(node.left?node.left._count:0)+(node.right?node.right._count:0)}function RedBlackTree(compare,root){this._compare=compare;this.root=root}var proto=RedBlackTree.prototype;Object.defineProperty(proto,"keys",{get:function(){var result=[];this.forEach(function(k,v){result.push(k)});return result}});Object.defineProperty(proto,"values",{get:function(){var result=[];

this.forEach(function(k,v){result.push(v)});return result}});Object.defineProperty(proto,"length",{get:function(){if(this.root){return this.root._count}return 0}});proto.insert=function(key,value){var cmp=this._compare;var n=this.root;var n_stack=[];var d_stack=[];while(n){var d=cmp(key,n.key);n_stack.push(n);d_stack.push(d);if(d<=0){n=n.left}else{n=n.right}}n_stack.push(new RBNode(RED,key,value,null,null,1));for(var s=n_stack.length-2;s>=0;--s){var n=n_stack[s];if(d_stack[s]<=0){n_stack[s]=new RBNode(n._color,n.key,n.value,n_stack[s+1],n.right,n._count+1)}else{n_stack[s]=new RBNode(n._color,n.key,n.value,n.left,n_stack[s+1],n._count+1)}}for(var s=n_stack.length-1;s>1;--s){var p=n_stack[s-1];var n=n_stack[s];if(p._color===BLACK||n._color===BLACK){break}var pp=n_stack[s-2];if(pp.left===p){if(p.left===n){var y=pp.right;if(y&&y._color===RED){p._color=BLACK;pp.right=repaint(BLACK,y);pp._color=RED;s-=1}else{pp._color=RED;pp.left=p.right;p._color=BLACK;p.right=pp;n_stack[s-2]=p;n_stack[s-1]=n;recount(pp);recount(p);if(s>=3){var ppp=n_stack[s-3];if(ppp.left===pp){ppp.left=p}else{ppp.right=p}}break}}else{var y=pp.right;if(y&&y._color===RED){p._color=BLACK;pp.right=repaint(BLACK,y);pp._color=RED;s-=1}else{p.right=n.left;pp._color=RED;pp.left=n.right;n._color=BLACK;n.left=p;n.right=pp;n_stack[s-2]=n;n_stack[s-1]=p;recount(pp);recount(p);recount(n);if(s>=3){var ppp=n_stack[s-3];if(ppp.left===pp){ppp.left=n}else{ppp.right=n}}break}}}else{if(p.right===n){var y=pp.left;if(y&&y._color===RED){p._color=BLACK;pp.left=repaint(BLACK,y);pp._color=RED;s-=1}else{pp._color=RED;pp.right=p.left;p._color=BLACK;p.left=pp;n_stack[s-2]=p;n_stack[s-1]=n;recount(pp);recount(p);if(s>=3){var ppp=n_stack[s-3];if(ppp.right===pp){ppp.right=p}else{ppp.left=p}}break}}else{var y=pp.left;if(y&&y._color===RED){p._color=BLACK;pp.left=repaint(BLACK,y);pp._color=RED;s-=1}else{p.left=n.right;pp._color=RED;pp.right=n.left;n._color=BLACK;n.right=p;n.left=pp;n_stack[s-2]=n;n_stack[s-1]=p;recount(pp);recount(p);recount(n);if(s>=3){var ppp=n_stack[s-3];if(ppp.right===pp){ppp.right=n}else{ppp.left=n}}break}}}}n_stack[0]._color=BLACK;return new RedBlackTree(cmp,n_stack[0])};function doVisitFull(visit,node){if(node.left){var v=doVisitFull(visit,node.left);if(v){return v}}var v=visit(node.key,node.value);if(v){return v}if(node.right){return doVisitFull(visit,node.right)}}function doVisitHalf(lo,compare,visit,node){var l=compare(lo,node.key);if(l<=0){if(node.left){var v=doVisitHalf(lo,compare,visit,node.left);if(v){return v}}var v=visit(node.key,node.value);if(v){return v}}if(node.right){return doVisitHalf(lo,compare,visit,node.right)}}function doVisit(lo,hi,compare,visit,node){var l=compare(lo,node.key);var h=compare(hi,node.key);var v;if(l<=0){if(node.left){v=doVisit(lo,hi,compare,visit,node.left);if(v){return v}}if(h>0){v=visit(node.key,node.value);if(v){return v}}}if(h>0&&node.right){return doVisit(lo,hi,compare,visit,node.right)}}proto.forEach=function rbTreeForEach(visit,lo,hi){if(!this.root){return}switch(arguments.length){case 1:return doVisitFull(visit,this.root);break;case 2:return doVisitHalf(lo,this._compare,visit,this.root);break;case 3:if(this._compare(lo,hi)>=0){return}return doVisit(lo,hi,this._compare,visit,this.root);break}};Object.defineProperty(proto,"begin",{get:function(){var stack=[];var n=this.root;while(n){stack.push(n);n=n.left}return new RedBlackTreeIterator(this,stack)}});Object.defineProperty(proto,"end",{get:function(){var stack=[];var n=this.root;while(n){stack.push(n);n=n.right}return new RedBlackTreeIterator(this,stack)}});proto.at=function(idx){if(idx<0){return new RedBlackTreeIterator(this,[])}var n=this.root;var stack=[];while(true){stack.push(n);if(n.left){if(idx<n.left._count){n=n.left;continue}idx-=n.left._count}if(!idx){return new RedBlackTreeIterator(this,stack)}idx-=1;if(n.right){if(idx>=n.right._count){break}n=n.right}else{break}}return new RedBlackTreeIterator(this,[])};proto.ge=function(key){var cmp=this._compare;var n=this.root;var stack=[];var last_ptr=0;while(n){var d=cmp(key,n.key);stack.push(n);if(d<=0){last_ptr=stack.length}if(d<=0){n=n.left}else{n=n.right}}stack.length=last_ptr;return new RedBlackTreeIterator(this,stack)};proto.gt=function(key){var cmp=this._compare;var n=this.root;var stack=[];var last_ptr=0;while(n){var d=cmp(key,n.key);stack.push(n);if(d<0){last_ptr=stack.length}if(d<0){n=n.left}else{n=n.right}}stack.length=last_ptr;return new RedBlackTreeIterator(this,stack)};proto.lt=function(key){var cmp=this._compare;var n=this.root;var stack=[];var last_ptr=0;while(n){var d=cmp(key,n.key);stack.push(n);if(d>0){last_ptr=stack.length}if(d<=0){n=n.left}else{n=n.right}}stack.length=last_ptr;return new RedBlackTreeIterator(this,stack)};proto.le=function(key){var cmp=this._compare;var n=this.root;var stack=[];var last_ptr=0;while(n){var d=cmp(key,n.key);stack.push(n);if(d>=0){last_ptr=stack.length}if(d<0){n=n.left}else{n=n.right}}stack.length=last_ptr;return new RedBlackTreeIterator(this,stack)};proto.find=function(key){var cmp=this._compare;var n=this.root;var stack=[];while(n){var d=cmp(key,n.key);stack.push(n);if(d===0){return new RedBlackTreeIterator(this,stack)}if(d<=0){n=n.left}else{n=n.right}}return new RedBlackTreeIterator(this,[])};proto.remove=function(key){var iter=this.find(key);if(iter){return iter.remove()}return this};proto.get=function(key){var cmp=this._compare;var n=this.root;while(n){var d=cmp(key,n.key);if(d===0){return n.value}if(d<=0){n=n.left}else{n=n.right}}return};function RedBlackTreeIterator(tree,stack){this.tree=tree;this._stack=stack}var iproto=RedBlackTreeIterator.prototype;Object.defineProperty(iproto,"valid",{get:function(){return this._stack.length>0}});Object.defineProperty(iproto,"node",{get:function(){if(this._stack.length>0){return this._stack[this._stack.length-1]}return null},enumerable:true});iproto.clone=function(){return new RedBlackTreeIterator(this.tree,this._stack.slice())};function swapNode(n,v){n.key=v.key;n.value=v.value;n.left=v.left;n.right=v.right;n._color=v._color;n._count=v._count}function fixDoubleBlack(stack){var n,p,s,z;for(var i=stack.length-1;i>=0;--i){n=stack[i];if(i===0){n._color=BLACK;return}p=stack[i-1];if(p.left===n){s=p.right;if(s.right&&s.right._color===RED){s=p.right=cloneNode(s);z=s.right=cloneNode(s.right);p.right=s.left;s.left=p;s.right=z;s._color=p._color;n._color=BLACK;p._color=BLACK;z._color=BLACK;recount(p);recount(s);if(i>1){var pp=stack[i-2];if(pp.left===p){pp.left=s}else{pp.right=s}}stack[i-1]=s;return}else if(s.left&&s.left._color===RED){s=p.right=cloneNode(s);z=s.left=cloneNode(s.left);p.right=z.left;s.left=z.right;z.left=p;z.right=s;z._color=p._color;p._color=BLACK;s._color=BLACK;n._color=BLACK;recount(p);recount(s);recount(z);if(i>1){var pp=stack[i-2];if(pp.left===p){pp.left=z}else{pp.right=z}}stack[i-1]=z;return}if(s._color===BLACK){if(p._color===RED){p._color=BLACK;p.right=repaint(RED,s);return}else{p.right=repaint(RED,s);continue}}else{s=cloneNode(s);p.right=s.left;s.left=p;s._color=p._color;p._color=RED;recount(p);recount(s);if(i>1){var pp=stack[i-2];if(pp.left===p){pp.left=s}else{pp.right=s}}stack[i-1]=s;stack[i]=p;if(i+1<stack.length){stack[i+1]=n}else{stack.push(n)}i=i+2}}else{s=p.left;if(s.left&&s.left._color===RED){s=p.left=cloneNode(s);z=s.left=cloneNode(s.left);p.left=s.right;s.right=p;s.left=z;s._color=p._color;n._color=BLACK;p._color=BLACK;z._color=BLACK;recount(p);recount(s);if(i>1){var pp=stack[i-2];if(pp.right===p){pp.right=s}else{pp.left=s}}stack[i-1]=s;return}else if(s.right&&s.right._color===RED){s=p.left=cloneNode(s);z=s.right=cloneNode(s.right);p.left=z.right;s.right=z.left;z.right=p;z.left=s;z._color=p._color;p._color=BLACK;s._color=BLACK;n._color=BLACK;recount(p);recount(s);recount(z);if(i>1){var pp=stack[i-2];if(pp.right===p){pp.right=z}else{pp.left=z}}stack[i-1]=z;return}if(s._color===BLACK){if(p._color===RED){p._color=BLACK;p.left=repaint(RED,s);return}else{p.left=repaint(RED,s);continue}}else{s=cloneNode(s);p.left=s.right;s.right=p;s._color=p._color;p._color=RED;recount(p);recount(s);if(i>1){var pp=stack[i-2];if(pp.right===p){pp.right=s}else{pp.left=s}}stack[i-1]=s;stack[i]=p;if(i+1<stack.length){stack[i+1]=n}else{stack.push(n)}i=i+2}}}}iproto.remove=function(){var stack=this._stack;if(stack.length===0){return this.tree}var cstack=new Array(stack.length);var n=stack[stack.length-1];cstack[cstack.length-1]=new RBNode(n._color,n.key,n.value,n.left,n.right,n._count);for(var i=stack.length-2;i>=0;--i){var n=stack[i];if(n.left===stack[i+1]){cstack[i]=new RBNode(n._color,n.key,n.value,cstack[i+1],n.right,n._count)}else{cstack[i]=new RBNode(n._color,n.key,n.value,n.left,cstack[i+1],n._count)}}n=cstack[cstack.length-1];if(n.left&&n.right){var split=cstack.length;n=n.left;while(n.right){cstack.push(n);n=n.right}var v=cstack[split-1];cstack.push(new RBNode(n._color,v.key,v.value,n.left,n.right,n._count));cstack[split-1].key=n.key;cstack[split-1].value=n.value;for(var i=cstack.length-2;i>=split;--i){n=cstack[i];cstack[i]=new RBNode(n._color,n.key,n.value,n.left,cstack[i+1],n._count)}cstack[split-1].left=cstack[split]}n=cstack[cstack.length-1];if(n._color===RED){var p=cstack[cstack.length-2];if(p.left===n){p.left=null}else if(p.right===n){p.right=null}cstack.pop();for(var i=0;i<cstack.length;++i){cstack[i]._count--}return new RedBlackTree(this.tree._compare,cstack[0])}else{if(n.left||n.right){if(n.left){swapNode(n,n.left)}else if(n.right){swapNode(n,n.right)}n._color=BLACK;for(var i=0;i<cstack.length-1;++i){cstack[i]._count--}return new RedBlackTree(this.tree._compare,cstack[0])}else if(cstack.length===1){return new RedBlackTree(this.tree._compare,null)}else{for(var i=0;i<cstack.length;++i){cstack[i]._count--}var parent=cstack[cstack.length-2];fixDoubleBlack(cstack);if(parent.left===n){parent.left=null}else{parent.right=null}}}return new RedBlackTree(this.tree._compare,cstack[0])};Object.defineProperty(iproto,"key",{get:function(){if(this._stack.length>0){return this._stack[this._stack.length-1].key}return},enumerable:true});Object.defineProperty(iproto,"value",{get:function(){if(this._stack.length>0){return this._stack[this._stack.length-1].value}return},enumerable:true});Object.defineProperty(iproto,"index",{get:function(){var idx=0;var stack=this._stack;if(stack.length===0){var r=this.tree.root;if(r){return r._count}return 0}else if(stack[stack.length-1].left){idx=stack[stack.length-1].left._count}for(var s=stack.length-2;s>=0;--s){if(stack[s+1]===stack[s].right){++idx;if(stack[s].left){idx+=stack[s].left._count}}}return idx},enumerable:true});iproto.next=function(){var stack=this._stack;if(stack.length===0){return}var n=stack[stack.length-1];if(n.right){n=n.right;while(n){stack.push(n);n=n.left}}else{stack.pop();while(stack.length>0&&stack[stack.length-1].right===n){n=stack[stack.length-1];stack.pop()}}};Object.defineProperty(iproto,"hasNext",{get:function(){var stack=this._stack;if(stack.length===0){return false}if(stack[stack.length-1].right){return true}for(var s=stack.length-1;s>0;--s){if(stack[s-1].left===stack[s]){return true}}return false}});iproto.update=function(value){var stack=this._stack;if(stack.length===0){throw new Error("Can't update empty node!")}var cstack=new Array(stack.length);var n=stack[stack.length-1];cstack[cstack.length-1]=new RBNode(n._color,n.key,value,n.left,n.right,n._count);for(var i=stack.length-2;i>=0;--i){n=stack[i];if(n.left===stack[i+1]){cstack[i]=new RBNode(n._color,n.key,n.value,cstack[i+1],n.right,n._count)}else{cstack[i]=new RBNode(n._color,n.key,n.value,n.left,cstack[i+1],n._count)}}return new RedBlackTree(this.tree._compare,cstack[0])};iproto.prev=function(){var stack=this._stack;if(stack.length===0){return}var n=stack[stack.length-1];if(n.left){n=n.left;while(n){stack.push(n);n=n.right}}else{stack.pop();while(stack.length>0&&stack[stack.length-1].left===n){n=stack[stack.length-1];stack.pop()}}};Object.defineProperty(iproto,"hasPrev",{get:function(){var stack=this._stack;if(stack.length===0){return false}if(stack[stack.length-1].left){return true}for(var s=stack.length-1;s>0;--s){if(stack[s-1].right===stack[s]){return true}}return false}});function defaultCompare(a,b){if(a<b){return-1}if(a>b){return 1}return 0}function createRBTree(compare){return new RedBlackTree(compare||defaultCompare,null)}},{}],11:[function(require,module,exports){"use strict";module.exports=createSlabDecomposition;var bounds=require("binary-search-bounds");var createRBTree=require("functional-red-black-tree");var orient=require("robust-orientation");var orderSegments=require("./lib/order-segments");function SlabDecomposition(slabs,coordinates,horizontal){this.slabs=slabs;this.coordinates=coordinates;this.horizontal=horizontal}var proto=SlabDecomposition.prototype;function compareHorizontal(e,y){return e.y-y}function searchBucket(root,p){var lastNode=null;while(root){var seg=root.key;var l,r;if(seg[0][0]<seg[1][0]){l=seg[0];r=seg[1]}else{l=seg[1];r=seg[0]}var o=orient(l,r,p);if(o<0){root=root.left}else if(o>0){if(p[0]!==seg[1][0]){lastNode=root;root=root.right}else{var val=searchBucket(root.right,p);if(val){return val}root=root.left}}else{if(p[0]!==seg[1][0]){return root}else{var val=searchBucket(root.right,p);if(val){return val}root=root.left}}}return lastNode}proto.castUp=function(p){var bucket=bounds.le(this.coordinates,p[0]);if(bucket<0){return-1}var root=this.slabs[bucket];var hitNode=searchBucket(this.slabs[bucket],p);var lastHit=-1;if(hitNode){lastHit=hitNode.value}if(this.coordinates[bucket]===p[0]){var lastSegment=null;if(hitNode){lastSegment=hitNode.key}if(bucket>0){var otherHitNode=searchBucket(this.slabs[bucket-1],p);if(otherHitNode){if(lastSegment){if(orderSegments(otherHitNode.key,lastSegment)>0){lastSegment=otherHitNode.key;lastHit=otherHitNode.value}}else{lastHit=otherHitNode.value;lastSegment=otherHitNode.key}}}var horiz=this.horizontal[bucket];if(horiz.length>0){var hbucket=bounds.ge(horiz,p[1],compareHorizontal);if(hbucket<horiz.length){var e=horiz[hbucket];if(p[1]===e.y){if(e.closed){return e.index}else{while(hbucket<horiz.length-1&&horiz[hbucket+1].y===p[1]){hbucket=hbucket+1;e=horiz[hbucket];if(e.closed){return e.index}}if(e.y===p[1]&&!e.start){hbucket=hbucket+1;if(hbucket>=horiz.length){return lastHit}e=horiz[hbucket]}}}if(e.start){if(lastSegment){var o=orient(lastSegment[0],lastSegment[1],[p[0],e.y]);if(lastSegment[0][0]>lastSegment[1][0]){o=-o}if(o>0){lastHit=e.index}}else{lastHit=e.index}}else if(e.y!==p[1]){lastHit=e.index}}}}return lastHit};function IntervalSegment(y,index,start,closed){this.y=y;this.index=index;this.start=start;this.closed=closed}function Event(x,segment,create,index){this.x=x;this.segment=segment;this.create=create;this.index=index}function createSlabDecomposition(segments){var numSegments=segments.length;var numEvents=2*numSegments;var events=new Array(numEvents);for(var i=0;i<numSegments;++i){var s=segments[i];var f=s[0][0]<s[1][0];events[2*i]=new Event(s[0][0],s,f,i);events[2*i+1]=new Event(s[1][0],s,!f,i)}events.sort(function(a,b){var d=a.x-b.x;if(d){return d}d=a.create-b.create;if(d){return d}return Math.min(a.segment[0][1],a.segment[1][1])-Math.min(b.segment[0][1],b.segment[1][1])});var tree=createRBTree(orderSegments);var slabs=[];var lines=[];var horizontal=[];var lastX=-Infinity;for(var i=0;i<numEvents;){var x=events[i].x;var horiz=[];while(i<numEvents){var e=events[i];if(e.x!==x){break}i+=1;if(e.segment[0][0]===e.x&&e.segment[1][0]===e.x){if(e.create){if(e.segment[0][1]<e.segment[1][1]){horiz.push(new IntervalSegment(e.segment[0][1],e.index,true,true));horiz.push(new IntervalSegment(e.segment[1][1],e.index,false,false))}else{horiz.push(new IntervalSegment(e.segment[1][1],e.index,true,false));horiz.push(new IntervalSegment(e.segment[0][1],e.index,false,true))}}}else{if(e.create){tree=tree.insert(e.segment,e.index)}else{tree=tree.remove(e.segment)}}}slabs.push(tree.root);lines.push(x);horizontal.push(horiz)}return new SlabDecomposition(slabs,lines,horizontal)}},{"./lib/order-segments":8,"binary-search-bounds":9,"functional-red-black-tree":10,"robust-orientation":7}],12:[function(require,module,exports){"use strict";module.exports=preprocessPolygon;var orient=require("robust-orientation");var makeSlabs=require("slab-decomposition");function dummyFunction(p){return-1}function createClassifyPoint(segments,slabs,outside,orientation){function classifyPoint(p){var index=slabs.castUp(p);if(index<0){return outside}var seg=segments[index];if(!orientation){return orient(p,seg[0],seg[1])}else{return orient(p,seg[1],seg[0])}}return classifyPoint}function preprocessPolygon(loops,orientation){orientation=!!orientation;var numLoops=loops.length;var numSegments=0;for(var i=0;i<numLoops;++i){numSegments+=loops[i].length}if(numSegments===0){return dummyFunction}var segments=new Array(numSegments);var ptr=0;for(var i=0;i<numLoops;++i){var loop=loops[i];var numVertices=loop.length;for(var s=numVertices-1,t=0;t<numVertices;s=t++){segments[ptr++]=[loop[s],loop[t]]}}var slabs=makeSlabs(segments);var outside;var root=slabs.slabs[0];if(root){while(root.left){root=root.left}var h=root.key;if(h[0][0]<h[1][0]){outside=-1}else{outside=1}}else{var h=segments[slabs.horizontal[0][0].index];if(h[0][1]<h[1][1]){outside=1}else{outside=-1}}if(orientation){outside=-outside}return createClassifyPoint(segments,slabs,outside,orientation)}},{"robust-orientation":7,"slab-decomposition":11}],13:[function(require,module,exports){if(typeof require!=="undefined"){var Vec2=require("vec2");var segseg=require("segseg")}var isArray=function(a){return Object.prototype.toString.call(a)==="[object Array]"};var defined=function(a){return typeof a!=="undefined"};var definedOr=function(a,defaultValue){return defined(a)?a:defaultValue};var finite=function(a){return a!==Infinity&&a!==-Infinity};var det=function(x1,y1,x2,y2){return x1*y2-y1*x2};function Line2(slope,yintercept,x2,y2){this._listeners=[];if(!(this instanceof Line2)){return new Line2(slope,yintercept,x2,y2)}if(defined(x2)&&defined(y2)){return Line2.fromPoints(slope,yintercept,x2,y2)}else{if(defined(slope)){this.slope(slope)}if(defined(yintercept)){this.yintercept(yintercept)}}}Line2.prototype._yintercept=null;Line2.prototype._xintercept=null;Line2.prototype._slope=null;Line2.prototype.change=function(fn){if(typeof fn==="function"){this._listeners.push(fn);return fn}};Line2.prototype.ignore=function(fn){if(!fn){this._listeners=[]}else{this._listeners=this._listeners.filter(function(a){return a!==fn})}};Line2.prototype.notify=function(fn){var fns=this._listeners,l=fns.length;for(var i=0;i<l;i++){fns[i](this)}};Line2.prototype.yintercept=function(val){if(defined(val)){if(finite(val)){val=Vec2.clean(val)}if(this._yintercept!==val){this._yintercept=val;if(!this.isHorizontal()){this._xintercept=this.solveForX(0)}this.notify()}}return definedOr(this._yintercept,null)};Line2.prototype.xintercept=function(val){if(defined(val)){if(finite(val)){val=Vec2.clean(val)}if(this._xintercept!==val){if(!this.isVertical()){var diff=this._xintercept-val;this._yintercept-=diff*-this._slope}this._xintercept=val;this.notify()}}return definedOr(this._xintercept,null)};Line2.prototype.slope=function(val){if(defined(val)){if(finite(val)){val=Vec2.clean(val)}if(this._slope!==val){var old=this._slope;this._slope=val;if(old!==null){var x=this.solveForX(0);if(!finite(x)){x=null}this._xintercept=x}this.notify()}}return definedOr(this._slope,null)};Line2.prototype.intersectSegment=function(x1,y1,x2,y2){var dx=x2-x1;var dy=y2-y1;var lx1,ly1,lx2,ly2;var horizontal=this.isHorizontal();var vertical=this.isVertical();if(dx===0){if(vertical){return x1===this.xintercept()}}else if(dy===0){if(horizontal){return y1===this.yintercept()}}else{if(dy/dx===this.slope()){return y1===this.solveForY(x1)}}if(x1>x2){lx1=x2-10;lx2=x1+10}else{lx1=x1-10;lx2=x2+10}var isect;if(this.isHorizontal()){y=this.yintercept();isect=segseg(lx1,y,lx2,y,x1,y1,x2,y2)}else if(this.isVertical()){if(y1>y2){ly1=y2-10;ly2=y1+10}else{ly1=y1-10;ly2=y2+10}var x=this.xintercept();isect=segseg(x,ly1,x,ly2,x1,y1,x2,y2)}else{ly1=this.solveForY(lx1);ly2=this.solveForY(lx2);isect=segseg(lx1,ly1,lx2,ly2,x1,y1,x2,y2)}if(isect&&isect!==true){return Vec2.fromArray(isect)}return isect};Line2.prototype.createPerpendicular=function(vec){if(this.isVertical()){return new Line2(0,vec.y)}else if(this.isHorizontal()){var l=new Line2;l.xintercept(vec.x);l.slope(Infinity);return l}else{var perpSlope=-1/this.slope();return new Line2(perpSlope,vec.y-perpSlope*vec.x)}};Line2.prototype.intersectCircle=function(vec,radius){var r2=radius*radius,slope=this.slope(),yintercept=this.yintercept(),f,g,v1,v2;if(this.isHorizontal()){f=1;g=0}else if(this.isVertical()){slope=radius;yintercept=r2;f=0;g=slope}else{f=1/slope;g=1}var x0=this.isVertical()?this.xintercept():1;var y0=yintercept+slope;var f2=f*f;var g2=g*g;var tmp=f*(vec.y-y0)-g*(vec.x-x0);tmp*=tmp;var den=f2+g2;var discriminant=Math.sqrt(r2*(f2+g2)-tmp);if(isNaN(discriminant)){return[]}discriminant/=den;var num=f*(vec.x-x0)+g*(vec.y-y0);var t1=num/den+discriminant;var t2=num/den-discriminant;v1=new Vec2(x0+t1*f,y0+t1*g);v2=new Vec2(x0+t2*f,y0+t2*g);var ret=[v1];if(!v1.equal(v2)){ret.push(v2)}return ret};Line2.prototype.solveForX=function(y){if(this.isVertical()){return this.xintercept()}else{return(y-this.yintercept())/this.slope()}};Line2.prototype.solveForY=function(x){if(this.isHorizontal()){return this.yintercept()}else{return this.slope()*x+this.yintercept()}};Line2.prototype.intersect=function(line,y1,x2,y2){if(defined(y1)&&defined(y2)||defined(line.end)){return this.intersectSegment(line,y1,x2,y2)}var s1=this.slope();var s2=line.slope();if(s1===s2){return this.yintercept()===line.yintercept()&&this.xintercept()===line.xintercept()}if(finite(s1)&&finite(s2)){if(this.isHorizontal()){return new Vec2(line.solveForX(this.yintercept()),this.yintercept())}if(line.isHorizontal()){return new Vec2(this.solveForX(line.yintercept()),line.yintercept())}var x1=line.solveForX(-1);y1=line.solveForY(x1);x2=line.solveForX(1);y2=line.solveForY(x2);var x3=this.solveForX(-1);var y3=this.solveForY(x3);var x4=this.solveForX(1);var y4=this.solveForY(x4);var a=det(x1,y1,x2,y2);var b=det(x3,y3,x4,y4);var xnum=det(a,x1-x2,b,x3-x4);var ynum=det(a,y1-y2,b,y3-y4);var den=det(x1-x2,y1-y2,x3-x4,y3-y4);return Vec2(xnum/den,ynum/den)}else{var slope,yi,x=this.xintercept()||line.xintercept();if(!finite(s1)){slope=s2;yi=line.yintercept()}else{slope=s1;yi=this.yintercept()}if(slope!==0){return Vec2(x,x*slope+yi)}else{return Vec2(x,yi)}}};Line2.fromPoints=function(x1,y1,x2,y2){if(isArray(y1)){y2=y1[1];x2=y1[0]}else if(defined(y1)&&defined(y1.x)&&defined(y1.y)){y2=y1.y;x2=y1.x}if(isArray(x1)){y1=x1[1];x1=x1[0]}else if(defined(x1)&&defined(x1.x)&&defined(x1.y)){y1=x1.y;x1=x1.x}var line=new Line2;var slope=(y2-y1)/(x2-x1);line.slope(slope);if(line.isHorizontal()){line.yintercept(y1)}else if(line.isVertical()){line.xintercept(x2)}else{line.yintercept(y1-slope*x1)}return line};Line2.prototype.isHorizontal=function(){return!this.slope()};Line2.prototype.isVertical=function(){return!finite(this.slope())};Line2.prototype.closestPointTo=function(vec){var yi=this.yintercept();var xi=this.xintercept();var s=this.slope();if(this.isHorizontal()){return Vec2(vec.x,yi)}else if(this.isVertical()){return Vec2(xi,vec.y)}else{return this.intersect(this.createPerpendicular(vec))}};Line2.prototype.containsPoint=function(vec,y){var x=vec;if(!defined(y)){y=vec.y;x=vec.x}if(this.isHorizontal()){return y===this.yintercept()}else if(this.isVertical()){return x===this.xintercept()}else{return y===this.solveForY(x)}};if(typeof module!=="undefined"&&typeof module.exports=="object"){module.exports=Line2}if(typeof window!=="undefined"){window.Line2=window.Line2||Line2}},{segseg:14,vec2:15}],14:[function(require,module,exports){function segseg(x1,y1,x2,y2,x3,y3,x4,y4){if(arguments.length===4){var p1=x1;var p2=y1;var p3=x2;var p4=y2;if(p1.length&&p1.length===2){x1=p1[0];y1=p1[1];x2=p2[0];y2=p2[1];x3=p3[0];y3=p3[1];x4=p4[0];y4=p4[1]}else{x1=p1.x;y1=p1.y;x2=p2.x;y2=p2.y;x3=p3.x;y3=p3.y;x4=p4.x;y4=p4.y}}var a1,a2,b1,b2,c1,c2;var r1,r2,r3,r4;var denom,offset;var x,y;a1=y2-y1;b1=x1-x2;c1=x2*y1-x1*y2;r3=a1*x3+b1*y3+c1;r4=a1*x4+b1*y4+c1;if(r3!==0&&r4!==0&&(r3>=0&&r4>=0||r3<0&&r4<0)){return}a2=y4-y3;b2=x3-x4;c2=x4*y3-x3*y4;r1=a2*x1+b2*y1+c2;r2=a2*x2+b2*y2+c2;if(r1!==0&&r2!==0&&(r1>=0&&r2>=0||r1<0&&r2<0)){return}denom=a1*b2-a2*b1;if(denom===0){return true}offset=denom<0?-denom/2:denom/2;x=b1*c2-b2*c1;y=a2*c1-a1*c2;return[(x<0?x:x)/denom,(y<0?y:y)/denom]}if(typeof module!=="undefined"&&module.exports){module.exports=segseg}if(typeof window!=="undefined"){window.segseg=window.segseg||segseg}},{}],15:[function(require,module,exports){(function inject(clean,precision,undef){function Vec2(x,y){if(!(this instanceof Vec2)){return new Vec2(x,y)}if("object"===typeof x&&x){this.y=x.y||0;this.x=x.x||0;return}this.x=Vec2.clean(x||0);this.y=Vec2.clean(y||0)}Vec2.prototype={change:function(fn){if(fn){if(this.observers){this.observers.push(fn)}else{this.observers=[fn]}}else if(this.observers){for(var i=this.observers.length-1;i>=0;i--){this.observers[i](this)}}return this},ignore:function(fn){if(this.observers){var o=this.observers,l=o.length;while(l--){o[l]===fn&&o.splice(l,1)}}return this},set:function(x,y,silent){if("number"!=typeof x){silent=y;y=x.y;x=x.x}if(this.x===x&&this.y===y)return this;this.x=Vec2.clean(x);this.y=Vec2.clean(y);if(silent!==false)return this.change()},zero:function(){return this.set(0,0)},clone:function(){return new Vec2(this.x,this.y)},negate:function(returnNew){if(returnNew){return new Vec2(-this.x,-this.y)}else{return this.set(-this.x,-this.y)}},add:function(vec2,returnNew){if(!returnNew){this.x+=vec2.x;this.y+=vec2.y;return this.change()}else{return new Vec2(this.x+vec2.x,this.y+vec2.y)}},subtract:function(vec2,returnNew){if(!returnNew){this.x-=vec2.x;this.y-=vec2.y;return this.change()}else{return new Vec2(this.x-vec2.x,this.y-vec2.y)}},multiply:function(vec2,returnNew){var x,y;if("number"!==typeof vec2){x=vec2.x;y=vec2.y}else{x=y=vec2}if(!returnNew){return this.set(this.x*x,this.y*y)}else{return new Vec2(this.x*x,this.y*y)}},rotate:function(r,inverse,returnNew){var x=this.x,y=this.y,cos=Math.cos(r),sin=Math.sin(r),rx,ry;inverse=inverse?-1:1;rx=cos*x-inverse*sin*y;ry=inverse*sin*x+cos*y;if(returnNew){return new Vec2(rx,ry)}else{return this.set(rx,ry)}},length:function(){var x=this.x,y=this.y;return Math.sqrt(x*x+y*y)},lengthSquared:function(){var x=this.x,y=this.y;return x*x+y*y},distance:function(vec2){var x=this.x-vec2.x;var y=this.y-vec2.y;return Math.sqrt(x*x+y*y)},normalize:function(returnNew){var length=this.length();var invertedLength=length<Number.MIN_VALUE?0:1/length;if(!returnNew){return this.set(this.x*invertedLength,this.y*invertedLength)}else{return new Vec2(this.x*invertedLength,this.y*invertedLength)}},equal:function(v,w){if(w===undef){w=v.y;v=v.x}return Vec2.clean(v)===this.x&&Vec2.clean(w)===this.y},abs:function(returnNew){var x=Math.abs(this.x),y=Math.abs(this.y);if(returnNew){return new Vec2(x,y)}else{return this.set(x,y)}},min:function(v,returnNew){var tx=this.x,ty=this.y,vx=v.x,vy=v.y,x=tx<vx?tx:vx,y=ty<vy?ty:vy;if(returnNew){return new Vec2(x,y)}else{return this.set(x,y)}},max:function(v,returnNew){var tx=this.x,ty=this.y,vx=v.x,vy=v.y,x=tx>vx?tx:vx,y=ty>vy?ty:vy;if(returnNew){return new Vec2(x,y)}else{return this.set(x,y)}},clamp:function(low,high,returnNew){var ret=this.min(high,true).max(low);if(returnNew){return ret}else{return this.set(ret.x,ret.y)}},lerp:function(vec,amount){return this.add(vec.subtract(this,true).multiply(amount),true)},skew:function(){return new Vec2(-this.y,this.x)},dot:function(b){return Vec2.clean(this.x*b.x+b.y*this.y)},perpDot:function(b){return Vec2.clean(this.x*b.y-this.y*b.x)},angleTo:function(vec){return Math.atan2(this.perpDot(vec),this.dot(vec))},divide:function(vec2,returnNew){var x,y;if("number"!==typeof vec2){x=vec2.x;y=vec2.y}else{x=y=vec2}if(x===0||y===0){throw new Error("division by zero")}if(isNaN(x)||isNaN(y)){throw new Error("NaN detected")}if(returnNew){return new Vec2(this.x/x,this.y/y)}return this.set(this.x/x,this.y/y)},isPointOnLine:function(start,end){return(start.y-this.y)*(start.x-end.x)===(start.y-end.y)*(start.x-this.x)},toArray:function(){return[this.x,this.y]},fromArray:function(array){return this.set(array[0],array[1])},toJSON:function(){return{x:this.x,y:this.y}},toString:function(){return"("+this.x+", "+this.y+")"}};Vec2.fromArray=function(array){return new Vec2(array[0],array[1])};Vec2.precision=precision||8;var p=Math.pow(10,Vec2.precision);Vec2.clean=clean||function(val){if(isNaN(val)){throw new Error("NaN detected")}if(!isFinite(val)){throw new Error("Infinity detected")}if(Math.round(val)===val){return val}return Math.round(val*p)/p};Vec2.inject=inject;if(!clean){Vec2.fast=inject(function(k){return k});if(typeof module!=="undefined"&&typeof module.exports=="object"){module.exports=Vec2}else{window.Vec2=window.Vec2||Vec2}}return Vec2})()},{}],16:[function(require,module,exports){if(typeof require!=="undefined"){var Vec2=require("vec2");var segseg=require("segseg");var Line2=require("line2");var polygonBoolean=require("2d-polygon-boolean")}var PI=Math.PI;var TAU=PI*2;var toTAU=function(rads){if(rads<0){rads+=TAU}return rads};var isArray=function(a){return Object.prototype.toString.call(a)==="[object Array]"};var isFunction=function(a){return typeof a==="function"};var defined=function(a){return typeof a!=="undefined"};function Polygon(points){if(points instanceof Polygon){return points}if(!(this instanceof Polygon)){return new Polygon(points)}if(!Array.isArray(points)){points=points?[points]:[]}this.points=points.map(function(point){if(Array.isArray(point)){return Vec2.fromArray(point)}else if(!(point instanceof Vec2)){if(typeof point.x!=="undefined"&&typeof point.y!=="undefined"){return Vec2(point.x,point.y)}}else{return point}})}Polygon.prototype={each:function(fn){for(var i=0;i<this.points.length;i++){if(fn.call(this,this.point(i-1),this.point(i),this.point(i+1),i)===false){break}}return this},insert:function(vec,index){this.points.splice(index,0,vec)},point:function(idx){var el=idx%this.points.length;if(el<0){el=this.points.length+el}return this.points[el]},dedupe:function(returnNew){var seen={};var points=this.points.filter(function(a){var key=a.x+":"+a.y;if(!seen[key]){seen[key]=true;return true}});if(returnNew){return new Polygon(points)}else{this.points=points;return this}},remove:function(vec){if(typeof vec==="number"){this.points.splice(vec,1)}else{this.points=this.points.filter(function(point){return point!==vec})}return this},clean:function(returnNew){var last=this.point(-1);var points=this.points.filter(function(a){var ret=false;if(!last.equal(a)){ret=true}last=a;return ret});if(returnNew){return new Polygon(points)}else{this.points=points;return this}},simplify:function(){var clean=function(v){return Math.round(v*1e4)/1e4};var collinear=function(a,b,c){var r=a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y);return clean(r)===0};this.points=this.points.filter(Boolean);var newPoly=[];for(var i=0;i<this.points.length;i++){var p=this.point(i-1);var n=this.point(i+1);var c=this.point(i);var angle=c.subtract(p,true).angleTo(c.subtract(n,true));if(!collinear(p,c,n)&&clean(angle)){newPoly.push(c)}}this.points=newPoly;return this},winding:function(){return this.area()>0},rewind:function(cw){cw=!!cw;var winding=this.winding();if(winding!==cw){this.points.reverse()}return this},area:function(){var area=0;var first=this.point(0);this.each(function(prev,current,next,idx){if(idx<2){return}var edge1=first.subtract(current,true);var edge2=first.subtract(prev,true);area+=edge1.x*edge2.y-edge1.y*edge2.x});return area/2},closestPointTo:function(vec){var points=[],l=this.points.length,dist=Infinity,found=null,foundIndex=0,foundOnPoint=false,i;for(i=0;i<l;i++){var a=this.point(i-1);var b=this.point(i);var ab=b.subtract(a,true);var veca=vec.subtract(a,true);var vecadot=veca.dot(ab);var abdot=ab.dot(ab);var t=Math.min(Math.max(vecadot/abdot,0),1);var point=ab.multiply(t).add(a);

var length=vec.subtract(point,true).lengthSquared();if(length<dist){found=point;foundIndex=i;foundOnPoint=t===0||t===1;dist=length}}found.prev=this.point(foundIndex-1);found.next=this.point(foundIndex+1);if(foundOnPoint){found.current=this.point(foundIndex)}return found},center:function(){var aabb=this.aabb();return Vec2(aabb.x+aabb.w/2,aabb.y+aabb.h/2)},scale:function(amount,origin,returnTrue){var obj=this;if(returnTrue){obj=this.clone()}if(!origin){origin=obj.center()}obj.each(function(p,c){c.multiply(amount)});var originDiff=origin.multiply(amount,true).subtract(origin);obj.each(function(p,c){c.subtract(originDiff)});return obj},containsPoint:function(point){var c=false;this.each(function(prev,current,next){(prev.y<=point.y&&point.y<current.y||current.y<=point.y&&point.y<prev.y)&&point.x<(current.x-prev.x)*(point.y-prev.y)/(current.y-prev.y)+prev.x&&(c=!c)});return c},containsPolygon:function(subject){if(isArray(subject)){subject=new Polygon(subject)}for(var i=0;i<subject.points.length;i++){if(!this.containsPoint(subject.points[i])){return false}}for(var i=0;i<this.points.length;i++){var outer=this.line(i);for(var j=0;j<subject.points.length;j++){var inner=subject.line(j);var isect=segseg(outer[0],outer[1],inner[0],inner[1]);if(isect&&isect!==true){return false}}}return true},aabb:function(){if(this.points.length<2){return{x:0,y:0,w:0,h:0}}var xmin,xmax,ymax,ymin,point1=this.point(1);xmax=xmin=point1.x;ymax=ymin=point1.y;this.each(function(p,c){if(c.x>xmax){xmax=c.x}if(c.x<xmin){xmin=c.x}if(c.y>ymax){ymax=c.y}if(c.y<ymin){ymin=c.y}});return{x:xmin,y:ymin,w:xmax-xmin,h:ymax-ymin}},offset:function(delta,prune){var res=[];this.rewind(false).simplify().each(function(p,c,n,i){var e1=c.subtract(p,true).normalize();var e2=c.subtract(n,true).normalize();var r=delta/Math.sin(Math.acos(e1.dot(e2))/2);var d=e1.add(e2,true).normalize().multiply(r,true);var angle=toTAU(e1.angleTo(e2));var o=e1.perpDot(e2)<0?c.add(d,true):c.subtract(d,true);if(angle>TAU*.75||angle<TAU*.25){o.computeSegments=angle;c.color="white";c.radius=3}o.point=c;res.push(o)});var parline=function(a,b){var normal=a.subtract(b,true);var angle=Vec2(1,0).angleTo(normal);var bisector=Vec2(delta,0).rotate(angle+Math.PI/2);bisector.add(b);var cperp=bisector.add(normal,true);var l=new Line2(bisector.x,bisector.y,cperp.x,cperp.y);var n=a.add(normal,true);var l2=new Line2(a.x,a.y,n.x,n.y);return l};var offsetPolygon=Polygon(res);var ret=[];offsetPolygon.each(function(p,c,n,i){var isect=segseg(c,c.point,n,n.point);if(isect){var pp=offsetPolygon.point(i-2);var nn=offsetPolygon.point(i+2);var ppline=parline(pp.point,p.point);var pline=parline(p.point,c.point);var nline=parline(c.point,n.point);var nnline=parline(n.point,nn.point);var computed=pline.intersect(nnline);computed.color="yellow";computed.point=c.point;ret.push(computed)}else{ret.push(c)}});return ret.length?Polygon(ret):offsetPolygon},line:function(idx){return[this.point(idx),this.point(idx+1)]},lines:function(fn){var idx=0;this.each(function(p,start,end){fn(start,end,idx++)});return this},selfIntersections:function(){var ret=[];var poly=this;var l=this.points.length+1;for(var i=0;i<=l+1;i++){var s=this.point(i);var e=this.point(i+1);for(var i2=i-2;i2<=l+1;i2++){var s2=this.point(i2);var e2=this.point(i2+1);if(!s2.equal(e)&&!s2.equal(s)&&!e2.equal(s)&&!e2.equal(e)){var isect=segseg(s,e,s2,e2);if(isect&&isect!==true){var vec=Vec2.fromArray(isect);vec.s=i+s.subtract(vec,true).length()/s.subtract(e,true).length();vec.b=i2+s2.subtract(vec,true).length()/s2.subtract(e2,true).length();vec.si=i;vec.bi=i2;vec.color="red";vec.radius=5;ret.push(vec)}}}}var poly=Polygon(ret).clean();return poly},pruneSelfIntersections:function(){var selfIntersections=this.selfIntersections();var belongTo=function(s1,b1,s2,b2){return s1>s2&&b1<b2};var contain=function(s1,b1,s2,b2){return s1<s2&&b1>b2};var interfere=function(s1,b1,s2,b2){return s1<s2&&s2<b1&&b2>b1||s2<b1&&b1<b2&&s1<s2};function Node(value,depth){this.value=value;this.depth=this.depth;this.children=[]}var rootVec=this.point(0).clone();rootVec.s=0;rootVec.b=this.points.length-1+.99;var root=new Node(rootVec);var last=root;var tree=[rootVec];selfIntersections.each(function(p,c,n){console.log("belongTo:",belongTo(last.s,last.b,c.s,c.b),"contain:",contain(last.s,last.b,c.s,c.b),"interfere:",interfere(last.s,last.b,c.s,c.b));tree.push(c);last=c});var ret=[];if(tree.length<2){return[this]}tree.sort(function(a,b){return a.s-b.s});for(var i=0;i<tree.length;i+=2){var poly=[];var next=i<tree.length-1?tree[i+1]:null;if(next){for(var j=Math.floor(tree[i].s);j<=Math.floor(next.s);j++){poly.push(this.point(j))}poly.push(next);for(var j=Math.floor(next.b+1);j<=Math.floor(tree[i].b);j++){poly.push(this.point(j))}}else{poly.push(tree[i]);for(var k=Math.floor(tree[i].s+1);k<=Math.floor(tree[i].b);k++){poly.push(this.point(k))}}ret.push(new Polygon(poly))}return ret},get length(){return this.points.length},clone:function(){var points=[];this.each(function(p,c){points.push(c.clone())});return new Polygon(points)},rotate:function(rads,origin,returnNew){origin=origin||this.center();var obj=returnNew?this.clone():this;return obj.each(function(p,c){c.subtract(origin).rotate(rads).add(origin)})},translate:function(vec2,returnNew){var obj=returnNew?this.clone():this;obj.each(function(p,c){c.add(vec2)});return obj},equal:function(poly){var current=poly.length;while(current--){if(!this.point(current).equal(poly.point(current))){return false}}return true},containsCircle:function(x,y,radius){var position=new Vec2(x,y);if(!this.containsPoint(position)){return false}var closestPoint=this.closestPointTo(position);if(closestPoint.distance(position)>=radius){return true}},contains:function(thing){if(!thing){return false}if(defined(thing.radius)&&thing.position){var radius;if(isFunction(thing.radius)){radius=thing.radius()}else{radius=thing.radius}return this.containsCircle(thing.position.x,thing.position.y,radius)}else if(typeof thing.points!=="undefined"){var points,l;if(isFunction(thing.containsPolygon)){points=thing.points}else if(isArray(thing.points)){points=thing.points}return this.containsPolygon(points)}else if(defined(thing.x1)&&defined(thing.x2)&&defined(thing.y1)&&defined(thing.y2)){return this.containsPolygon([new Vec2(thing.x1,thing.y1),new Vec2(thing.x2,thing.y1),new Vec2(thing.x2,thing.y2),new Vec2(thing.x1,thing.y2)])}else if(defined(thing.x)&&defined(thing.y)){var x2,y2;if(defined(thing.w)&&defined(thing.h)){x2=thing.x+thing.w;y2=thing.y+thing.h}if(defined(thing.width)&&defined(thing.height)){x2=thing.x+thing.width;y2=thing.y+thing.height}return this.containsPolygon([new Vec2(thing.x,thing.y),new Vec2(x2,thing.y),new Vec2(x2,y2),new Vec2(thing.x,y2)])}return false},union:function(other){return Polygon(polygonBoolean(this.toArray(),other.toArray(),"or")[0])},cut:function(other){return polygonBoolean(this.toArray(),other.toArray(),"not").map(function(r){return new Polygon(r)})},intersect:function(other){return polygonBoolean(this.toArray(),other.toArray(),"and").map(function(r){return new Polygon(r)})},toArray:function(){var l=this.length;var ret=Array(l);for(var i=0;i<l;i++){ret[i]=this.points[i].toArray()}return ret},toString:function(){return this.points.join(",")}};if(typeof module!=="undefined"&&module.exports){module.exports=Polygon}if(typeof window!=="undefined"){window.Polygon=Polygon}},{"2d-polygon-boolean":1,line2:13,segseg:14,vec2:15}],17:[function(require,module,exports){arguments[4][2][0].apply(exports,arguments)},{dup:2}],18:[function(require,module,exports){arguments[4][3][0].apply(exports,arguments)},{dup:3,"two-product":21,"two-sum":17}],19:[function(require,module,exports){arguments[4][4][0].apply(exports,arguments)},{dup:4}],20:[function(require,module,exports){arguments[4][5][0].apply(exports,arguments)},{dup:5}],21:[function(require,module,exports){arguments[4][6][0].apply(exports,arguments)},{dup:6}],22:[function(require,module,exports){arguments[4][7][0].apply(exports,arguments)},{dup:7,"robust-scale":18,"robust-subtract":19,"robust-sum":20,"two-product":21}],23:[function(require,module,exports){module.exports=robustPointInPolygon;var orient=require("robust-orientation");function robustPointInPolygon(vs,point){var x=point[0];var y=point[1];var n=vs.length;var inside=1;var lim=n;for(var i=0,j=n-1;i<lim;j=i++){var a=vs[i];var b=vs[j];var yi=a[1];var yj=b[1];if(yj<yi){if(yj<y&&y<yi){var s=orient(a,b,point);if(s===0){return 0}else{inside^=0<s|0}}else if(y===yi){var c=vs[(i+1)%n];var yk=c[1];if(yi<yk){var s=orient(a,b,point);if(s===0){return 0}else{inside^=0<s|0}}}}else if(yi<yj){if(yi<y&&y<yj){var s=orient(a,b,point);if(s===0){return 0}else{inside^=s<0|0}}else if(y===yi){var c=vs[(i+1)%n];var yk=c[1];if(yk<yi){var s=orient(a,b,point);if(s===0){return 0}else{inside^=s<0|0}}}}else if(y===yi){var x0=Math.min(a[0],b[0]);var x1=Math.max(a[0],b[0]);if(i===0){while(j>0){var k=(j+n-1)%n;var p=vs[k];if(p[1]!==y){break}var px=p[0];x0=Math.min(x0,px);x1=Math.max(x1,px);j=k}if(j===0){if(x0<=x&&x<=x1){return 0}return 1}lim=j+1}var y0=vs[(j+n-1)%n][1];while(i+1<lim){var p=vs[i+1];if(p[1]!==y){break}var px=p[0];x0=Math.min(x0,px);x1=Math.max(x1,px);i+=1}if(x0<=x&&x<=x1){return 0}var y1=vs[(i+1)%n][1];if(x<x0&&y0<y!==y1<y){inside^=1}}}return 2*inside-1}},{"robust-orientation":22}],24:[function(require,module,exports){(function inject(clean,precision,undef){var isArray=function(a){return Object.prototype.toString.call(a)==="[object Array]"};var defined=function(a){return a!==undef};function Vec2(x,y){if(!(this instanceof Vec2)){return new Vec2(x,y)}if(isArray(x)){y=x[1];x=x[0]}else if("object"===typeof x&&x){y=x.y;x=x.x}this.x=Vec2.clean(x||0);this.y=Vec2.clean(y||0)}Vec2.prototype={change:function(fn){if(typeof fn==="function"){if(this.observers){this.observers.push(fn)}else{this.observers=[fn]}}else if(this.observers&&this.observers.length){for(var i=this.observers.length-1;i>=0;i--){this.observers[i](this,fn)}}return this},ignore:function(fn){if(this.observers){if(!fn){this.observers=[]}else{var o=this.observers,l=o.length;while(l--){o[l]===fn&&o.splice(l,1)}}}return this},set:function(x,y,notify){if("number"!=typeof x){notify=y;y=x.y;x=x.x}if(this.x===x&&this.y===y){return this}var orig=null;if(notify!==false&&this.observers&&this.observers.length){orig=this.clone()}this.x=Vec2.clean(x);this.y=Vec2.clean(y);if(notify!==false){return this.change(orig)}},zero:function(){return this.set(0,0)},clone:function(){return new this.constructor(this.x,this.y)},negate:function(returnNew){if(returnNew){return new this.constructor(-this.x,-this.y)}else{return this.set(-this.x,-this.y)}},add:function(x,y,returnNew){if(typeof x!="number"){returnNew=y;if(isArray(x)){y=x[1];x=x[0]}else{y=x.y;x=x.x}}x+=this.x;y+=this.y;if(!returnNew){return this.set(x,y)}else{return new this.constructor(x,y)}},subtract:function(x,y,returnNew){if(typeof x!="number"){returnNew=y;if(isArray(x)){y=x[1];x=x[0]}else{y=x.y;x=x.x}}x=this.x-x;y=this.y-y;if(!returnNew){return this.set(x,y)}else{return new this.constructor(x,y)}},multiply:function(x,y,returnNew){if(typeof x!="number"){returnNew=y;if(isArray(x)){y=x[1];x=x[0]}else{y=x.y;x=x.x}}else if(typeof y!="number"){returnNew=y;y=x}x*=this.x;y*=this.y;if(!returnNew){return this.set(x,y)}else{return new this.constructor(x,y)}},rotate:function(r,inverse,returnNew){var x=this.x,y=this.y,cos=Math.cos(r),sin=Math.sin(r),rx,ry;inverse=inverse?-1:1;rx=cos*x-inverse*sin*y;ry=inverse*sin*x+cos*y;if(returnNew){return new this.constructor(rx,ry)}else{return this.set(rx,ry)}},length:function(){var x=this.x,y=this.y;return Math.sqrt(x*x+y*y)},lengthSquared:function(){var x=this.x,y=this.y;return x*x+y*y},distance:function(vec2){var x=this.x-vec2.x;var y=this.y-vec2.y;return Math.sqrt(x*x+y*y)},nearest:function(others){var shortestDistance=Number.MAX_VALUE,nearest=null,currentDistance;for(var i=others.length-1;i>=0;i--){currentDistance=this.distance(others[i]);if(currentDistance<=shortestDistance){shortestDistance=currentDistance;nearest=others[i]}}return nearest},normalize:function(returnNew){var length=this.length();var invertedLength=length<Number.MIN_VALUE?0:1/length;if(!returnNew){return this.set(this.x*invertedLength,this.y*invertedLength)}else{return new this.constructor(this.x*invertedLength,this.y*invertedLength)}},equal:function(v,w){if(typeof v!="number"){if(isArray(v)){w=v[1];v=v[0]}else{w=v.y;v=v.x}}return Vec2.clean(v)===this.x&&Vec2.clean(w)===this.y},abs:function(returnNew){var x=Math.abs(this.x),y=Math.abs(this.y);if(returnNew){return new this.constructor(x,y)}else{return this.set(x,y)}},min:function(v,returnNew){var tx=this.x,ty=this.y,vx=v.x,vy=v.y,x=tx<vx?tx:vx,y=ty<vy?ty:vy;if(returnNew){return new this.constructor(x,y)}else{return this.set(x,y)}},max:function(v,returnNew){var tx=this.x,ty=this.y,vx=v.x,vy=v.y,x=tx>vx?tx:vx,y=ty>vy?ty:vy;if(returnNew){return new this.constructor(x,y)}else{return this.set(x,y)}},clamp:function(low,high,returnNew){var ret=this.min(high,true).max(low);if(returnNew){return ret}else{return this.set(ret.x,ret.y)}},lerp:function(vec,amount,returnNew){return this.add(vec.subtract(this,true).multiply(amount),returnNew)},skew:function(returnNew){if(!returnNew){return this.set(-this.y,this.x)}else{return new this.constructor(-this.y,this.x)}},dot:function(b){return Vec2.clean(this.x*b.x+b.y*this.y)},perpDot:function(b){return Vec2.clean(this.x*b.y-this.y*b.x)},angleTo:function(vec){return Math.atan2(this.perpDot(vec),this.dot(vec))},divide:function(x,y,returnNew){if(typeof x!="number"){returnNew=y;if(isArray(x)){y=x[1];x=x[0]}else{y=x.y;x=x.x}}else if(typeof y!="number"){returnNew=y;y=x}if(x===0||y===0){throw new Error("division by zero")}if(isNaN(x)||isNaN(y)){throw new Error("NaN detected")}if(returnNew){return new this.constructor(this.x/x,this.y/y)}return this.set(this.x/x,this.y/y)},isPointOnLine:function(start,end){return(start.y-this.y)*(start.x-end.x)===(start.y-end.y)*(start.x-this.x)},toArray:function(){return[this.x,this.y]},fromArray:function(array){return this.set(array[0],array[1])},toJSON:function(){return{x:this.x,y:this.y}},toString:function(){return"("+this.x+", "+this.y+")"},constructor:Vec2};Vec2.fromArray=function(array,ctor){return new(ctor||Vec2)(array[0],array[1])};Vec2.precision=precision||8;var p=Math.pow(10,Vec2.precision);Vec2.clean=clean||function(val){if(isNaN(val)){throw new Error("NaN detected")}if(!isFinite(val)){throw new Error("Infinity detected")}if(Math.round(val)===val){return val}return Math.round(val*p)/p};Vec2.inject=inject;if(!clean){Vec2.fast=inject(function(k){return k});if(typeof module!=="undefined"&&typeof module.exports=="object"){module.exports=Vec2}else{window.Vec2=window.Vec2||Vec2}}return Vec2})()},{}],"sdf-polygon-2d":[function(require,module,exports){var polygon=require("polygon");var vec2=require("vec2");var classifyPoint=require("robust-point-in-polygon");module.exports=createSDF;var min=Math.min;var max=Math.max;var abs=Math.abs;function createSDF(polygons){var polypoints=Array(polygons.length);var polys=polygons.map(function(points,i){if(points.toArray){polypoints[i]=points.toArray();return points}else{polypoints[i]=points;return polygon(points)}});polys.sort(function(a,b){return b.area()-a.area()});var l=polys.length;var holes=Array(l);var classifiers=Array(l);holes[0]=false;for(var ci=1;ci<l;ci++){var pi=ci-1;var contained;while(pi>-1){contained=polys[pi].containsPolygon(polys[ci]);if(contained){break}pi--}holes[ci]=contained?!holes[pi]:false}var scratch=vec2();var s=[0,0];return function evaluate(x,y){if(Array.isArray(x)){y=x[1];x=x[0]}else if(typeof x.x!=="undefined"){y=x.y;x=x.x}scratch.x=x;scratch.y=y;s[0]=x;s[1]=y;var d=Infinity;var closest=null;for(var i=0;i<l;i++){var cd=polys[i].closestPointTo(scratch).distance(scratch);if(cd<d){closest=i}d=min(cd,d)}var inside=classifyPoint(polygons[closest],s)<0;return holes[closest]!==inside?-d:d}}},{polygon:16,"robust-point-in-polygon":23,vec2:24}]},{},[]);require=function e(t,n,r){function s(o,u){if(!n[o]){if(!t[o]){var a=typeof require=="function"&&require;if(!u&&a)return a(o,!0);if(i)return i(o,!0);var f=new Error("Cannot find module '"+o+"'");throw f.code="MODULE_NOT_FOUND",f}var l=n[o]={exports:{}};t[o][0].call(l.exports,function(e){var n=t[o][1][e];return s(n?n:e)},l,l.exports,e,t,n,r)}return n[o].exports}var i=typeof require=="function"&&require;for(var o=0;o<r.length;o++)s(r[o]);return s}({"2d-polygon-area":[function(require,module,exports){module.exports=area;var e0=[0,0];var e1=[0,0];function area(a){var area=0;var first=a[0];var l=a.length;for(var i=2;i<l;i++){var p=a[i-1];var c=a[i];e0[0]=first[0]-c[0];e0[1]=first[1]-c[1];e1[0]=first[0]-p[0];e1[1]=first[1]-p[1];area+=e0[0]*e1[1]-e0[1]*e1[0]}return area/2}},{}]},{},[]);require=function e(t,n,r){function s(o,u){if(!n[o]){if(!t[o]){var a=typeof require=="function"&&require;if(!u&&a)return a(o,!0);if(i)return i(o,!0);var f=new Error("Cannot find module '"+o+"'");throw f.code="MODULE_NOT_FOUND",f}var l=n[o]={exports:{}};t[o][0].call(l.exports,function(e){var n=t[o][1][e];return s(n?n:e)},l,l.exports,e,t,n,r)}return n[o].exports}var i=typeof require=="function"&&require;for(var o=0;o<r.length;o++)s(r[o]);return s}({segseg:[function(require,module,exports){function segseg(x1,y1,x2,y2,x3,y3,x4,y4){if(arguments.length===4){var p1=x1;var p2=y1;var p3=x2;var p4=y2;if(p1.length&&p1.length===2){x1=p1[0];y1=p1[1];x2=p2[0];y2=p2[1];x3=p3[0];y3=p3[1];x4=p4[0];y4=p4[1]}else{x1=p1.x;y1=p1.y;x2=p2.x;y2=p2.y;x3=p3.x;y3=p3.y;x4=p4.x;y4=p4.y}}var a1,a2,b1,b2,c1,c2;var r1,r2,r3,r4;var denom,offset;var x,y;a1=y2-y1;b1=x1-x2;c1=x2*y1-x1*y2;r3=a1*x3+b1*y3+c1;r4=a1*x4+b1*y4+c1;if(r3!==0&&r4!==0&&(r3>=0&&r4>=0||r3<0&&r4<0)){return}a2=y4-y3;b2=x3-x4;c2=x4*y3-x3*y4;r1=a2*x1+b2*y1+c2;r2=a2*x2+b2*y2+c2;if(r1!==0&&r2!==0&&(r1>=0&&r2>=0||r1<0&&r2<0)){return}denom=a1*b2-a2*b1;if(denom===0){return true}offset=denom<0?-denom/2:denom/2;x=b1*c2-b2*c1;y=a2*c1-a1*c2;return[(x<0?x:x)/denom,(y<0?y:y)/denom]}if(typeof module!=="undefined"&&module.exports){module.exports=segseg}if(typeof window!=="undefined"){window.segseg=window.segseg||segseg}},{}]},{},[]);require=function e(t,n,r){function s(o,u){if(!n[o]){if(!t[o]){var a=typeof require=="function"&&require;if(!u&&a)return a(o,!0);if(i)return i(o,!0);var f=new Error("Cannot find module '"+o+"'");throw f.code="MODULE_NOT_FOUND",f}var l=n[o]={exports:{}};t[o][0].call(l.exports,function(e){var n=t[o][1][e];return s(n?n:e)},l,l.exports,e,t,n,r)}return n[o].exports}var i=typeof require=="function"&&require;for(var o=0;o<r.length;o++)s(r[o]);return s}({signum:[function(require,module,exports){"use strict";module.exports=function signum(x){if(x<0){return-1}if(x>0){return 1}return 0}},{}]},{},[]);var fc=require("fc");var center=require("ctx-translate-center");var poly=require("ctx-render-polyline");var points=require("ctx-render-points");var bounds2=require("2d-bounds");var gridlines=require("ctx-render-grid-lines");var isect=require("robust-segment-intersect");var createSDF=require("sdf-polygon-2d");var area=require("2d-polygon-area");var segseg=require("segseg");var sign=require("signum");var TAU=Math.PI*2;var min=Math.min;var max=Math.max;var abs=Math.abs;var polyline=[[-10,-100],[-100,-100],[-100,-10],[-100,100],[0,0],[100,0]];window.dump=function(){console.log(JSON.stringify(polyline,null,"  "))};function pointinbox(point,minx,miny,maxx,maxy){var x=point[0];var y=point[1];return x>=minx&&x<=maxx&&y>=miny&&y<=maxy}function line(ctx,x1,y1,x2,y2,color){ctx.beginPath();ctx.moveTo(x1,y1);ctx.lineTo(x2,y2);ctx.strokeStyle=color||"grey";ctx.stroke()}function midpoint(c,n){return[(c[0]+n[0])/2,(c[1]+n[1])/2]}function closest(p,c,target){var pd=Math.abs(p-target);var cd=Math.abs(c-target);return pd<cd?1:0}var EPS=1e-6;function near(a,b){return Math.abs(a-b)<EPS}function vecNear(a,b){return near(a[0],b[0])&&near(a[1],b[1])}function gridfill(ctx,r,minx,miny,maxx,maxy,results){var lx=min(minx,maxx);var ly=min(miny,maxy);var ux=max(minx,maxx);var uy=max(miny,maxy);var offset=1;var offset2=offset*2;var inside="hsla(114, 19%, 25%, 1)";var border="hsla(228, 19%, 25%, 1)";var outside="hsla(0, 19%, 25%, .7)";var sdf=createSDF([polyline]);var block=[0,0];var r2=r/2|0;var contour=[];var map={};for(var x=lx;x<ux;x+=r){for(var y=ly;y<uy;y+=r){var oy=min(r-offset2,uy-y);var ox=min(r-offset2,ux-x);var dist=sdf(x+r2,y+r2);var res=[false,false,false,false];var tests=[[x,y],[x+r,y],[x+r,y+r],[x,y+r]];var potentialCrossings=[[0,1],[1,2],[2,3],[3,0]];var distances=tests.map(function(a){return sdf(a[0],a[1])});var crossings=potentialCrossings.map(function(t){if(sign(distances[t[0]]-r)!==sign(distances[t[1]]-r)){return true}else{return false}});crossings.map(function(c,i){if(c){var edge=[[tests[potentialCrossings[i][0]][0],tests[potentialCrossings[i][0]][1],distances[potentialCrossings[i][0]]],[tests[potentialCrossings[i][1]][0],tests[potentialCrossings[i][1]][1],distances[potentialCrossings[i][1]]]];var ssss=100,d=c,updateIndex;var lastDistance=Infinity;var mid;var midpointDistance;while(ssss--){mid=midpoint(edge[0],edge[1]);midpointDistance=sdf(mid[0],mid[1]);if(Math.abs(midpointDistance-r)<.1||midpointDistance>lastDistance){found=true;ctx.beginPath();ctx.arc(mid[0],mid[1],5,0,Math.PI*2,false);ctx.strokeStyle="green";ctx.stroke();contour.push([mid,x,y,midpointDistance]);break}updateIndex=closest(edge[0][2],edge[1][2],r);edge[updateIndex][0]=mid[0];edge[updateIndex][1]=mid[1];edge[updateIndex][2]=midpointDistance}if(ssss<=0){contour.push([mid,x,y,midpointDistance]);ctx.beginPath();ctx.arc(mid[0],mid[1],5,0,Math.PI*2,false);ctx.fillStyle="orange";ctx.fill()}}})}}var gridpoints={};var points={};contour.forEach(function(point){var gridkey=point[1]+","+point[2];if(!gridpoints[gridkey]){gridpoints[gridkey]=[]}var local=gridpoints[gridkey];var found=false;for(var i=0;i<local.length;i++){var lp=local[i][0];if(vecNear(lp,point[0])){return}}gridpoints[gridkey].push(point);var p=point[0];var key=p[0]+","+p[1];if(!points[key]){points[key]=1}});console.log(contour.length,Object.keys(points).length);Object.keys(gridpoints).map(function(key){var pair=gridpoints[key];if(pair.length<2){return}ctx.beginPath();ctx.moveTo(pair[0][0][0],pair[0][0][1]);pair.forEach(function(p,i){ctx.lineTo(p[0][0],p[0][1])});ctx.strokeStyle="red";ctx.stroke()})}var r=20;var b=[0,0,0,0];var ctx=fc(function(){ctx.clear();center(ctx);bounds2(polyline,b);b[0]=Math.floor(b[0]/r)*r-r*2|0;b[1]=Math.floor(b[1]/r)*r-r*2|0;b[2]=Math.ceil(b[2]/r)*r+r*2|0;b[3]=Math.ceil(b[3]/r)*r+r*2|0;var gridspacing=r;ctx.beginPath();gridlines(ctx,gridspacing,b[0],b[1],b[2],b[3]);ctx.strokeStyle="rgba(222, 228, 244, .1)";ctx.stroke();ctx.strokeStyle="grey";var pad=3;ctx.strokeRect(b[0]-pad,b[1]-pad,Math.ceil(b[2]-b[0])+pad*2,Math.ceil(b[3]-b[1])+pad*2);var results=[];gridfill(ctx,gridspacing,b[0],b[1],b[2],b[3],results);ctx.beginPath();poly(ctx,polyline);ctx.closePath();ctx.strokeStyle="hsl(17, 80%, 56%)";ctx.stroke();ctx.beginPath();points(ctx,3,polyline);ctx.fillStyle="hsl(49, 60%, 56%)";ctx.fill();if(mouse.dragging||mouse.near){ctx.beginPath();var p=mouse.dragging===false?mouse.near:mouse.down;var sr=10;ctx.moveTo(p[0]+sr,p[1]);ctx.arc(p[0],p[1],sr,0,TAU,false);ctx.strokeStyle="hsl(49, 60%, 56%)";ctx.stroke()}results.forEach(function(seg){if(seg.length<2){ctx.fillStyle="red";ctx.fillRect(seg[0][2]+r/4,seg[0][3]+r/4,r/2,r/2);return}ctx.strokeStyle="green";line(ctx,seg[0][0],seg[0][1],seg[1][0],seg[1][1],"red")})});var mouse={down:false,dragging:false,near:false,pos:[0,0]};function nearPolyline(mouse,polyline){var m=mouse.pos;for(var i=0;i<polyline.length;i++){var p=polyline[i];var dx=p[0]-m[0];var dy=p[1]-m[1];var d=Math.sqrt(dx*dx+dy*dy);if(d<min(10,r)){return p}}return false}document.addEventListener("mousemove",function(ev){mouse.pos[0]=ev.clientX-ctx.canvas.width/2|0;mouse.pos[1]=ev.clientY-ctx.canvas.height/2|0;if(mouse.down!==false){if(!mouse.dragging){mouse.dragging=true}else{var p=mouse.down;p[0]=mouse.pos[0];p[1]=mouse.pos[1]}}else{mouse.near=nearPolyline(mouse,polyline)}ctx.dirty()});document.addEventListener("mouseup",function(ev){mouse.down=false;mouse.dragging=false;ctx.dirty()});document.addEventListener("mousedown",function(ev){mouse.down=nearPolyline(mouse,polyline)});

package.json

{
  "name": "requirebin-sketch",
  "version": "1.0.0",
  "dependencies": {
    "fc": "1.4.3",
    "ctx-translate-center": "1.0.0",
    "ctx-render-polyline": "1.0.1",
    "ctx-render-points": "1.0.0",
    "2d-bounds": "1.0.0",
    "ctx-render-grid-lines": "1.0.0",
    "robust-segment-intersect": "1.0.1",
    "sdf-polygon-2d": "2.0.0",
    "2d-polygon-area": "1.0.0",
    "segseg": "0.2.1",
    "signum": "1.0.0"
  }
}

page-body.html

<!-- contents of this file will be placed inside the <body> -->

page-head.html

<!-- contents of this file will be placed inside the <head> -->

requirebin.md

made with requirebin