made with requirebin
Last active
August 29, 2015 14:18
-
-
Save mikolalysenko/75877f65c11bcd66da3a to your computer and use it in GitHub Desktop.
requirebin sketch
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| //Hacky experiment with Ken Clarkson-style L1 shortest path finding | |
| // This sketch just visualizes the graph/data structures which are built by the algorithm. | |
| // The green node is the source node and the red is the sink | |
| // Magenta nodes/edges are nodes in the graph which is searched | |
| // The total number of magenta nodes/edges is at most O(n log(n)), n = number of corners | |
| // Worst case time to search the graph using A* is O(n log^2(n)), but in practice it might | |
| // be way faster. | |
| // | |
| // Reference: | |
| // "Rectilinear shortest paths through polygonal obstacles". K.L. Clarkson, S. Kapoor, P.M. Vaidya. | |
| // http://netlib.lucent.com/who/clarkson/l1mp/p.ps.gz | |
| // | |
| //Interactions: | |
| // Left click to modify the grid | |
| // Right click to set the source/sink node | |
| // | |
| var mouseChange = require('mouse-change') | |
| var ndarray = require('ndarray') | |
| var getContour = require('contour-2d') | |
| var orient = require('robust-orientation')[3] | |
| var uniq = require('uniq') | |
| var makeBoxes = require('bitmap-to-boxes') | |
| var rbush = require('rbush') | |
| var bsearch = require('binary-search-bounds') | |
| var GRID_SHAPE = [32,32] | |
| var canvas = document.createElement('canvas') | |
| canvas.width = canvas.height = 512 | |
| document.body.appendChild(canvas) | |
| var context = canvas.getContext('2d') | |
| var grid = ndarray(new Uint32Array(GRID_SHAPE[0]*GRID_SHAPE[1]), GRID_SHAPE) | |
| canvas.addEventListener('contextmenu', function(ev) { | |
| ev.preventDefault() | |
| }) | |
| var lastButton = 0 | |
| , fillValue = 0 | |
| , root = [0,0] | |
| , sink = [GRID_SHAPE[0]-1, GRID_SHAPE[1]-1] | |
| , lastRightClick = 0 | |
| mouseChange(canvas, function(button, x, y) { | |
| if(button) { | |
| var width = canvas.width | |
| var height = canvas.height | |
| var tileX = Math.floor(width/GRID_SHAPE[0]) | |
| var tileY = Math.floor(height/GRID_SHAPE[1]) | |
| var i = Math.floor(x / tileX) | |
| var j = Math.floor(y / tileY) | |
| if(i >= 0 && i < GRID_SHAPE[0] && | |
| j >= 0 && j < GRID_SHAPE[1]) { | |
| if(!(lastButton&1)) { | |
| fillValue = !grid.get(i,j) | |
| } | |
| if(button & 1) { | |
| grid.set(i,j, fillValue) | |
| } | |
| if(button & 2) { | |
| if(lastRightClick === 0) { | |
| root[0] = i | |
| root[1] = j | |
| } else { | |
| sink[0] = i | |
| sink[1] = j | |
| } | |
| lastRightClick ^= 1 | |
| } | |
| } | |
| } | |
| lastButton = button | |
| }) | |
| function render() { | |
| requestAnimationFrame(render) | |
| var width = canvas.width | |
| var height = canvas.height | |
| var tileX = Math.floor(width/GRID_SHAPE[0]) | |
| var tileY = Math.floor(height/GRID_SHAPE[1]) | |
| function drawTile(x, y) { | |
| context.fillRect(x*tileX, y*tileY, tileX, tileY) | |
| } | |
| context.fillStyle = '#000' | |
| context.fillRect(0, 0, width, height) | |
| for(var i=0; i<GRID_SHAPE[0]; ++i) { | |
| for(var j=0; j<GRID_SHAPE[1]; ++j) { | |
| var cell = grid.get(i,j) | |
| if(cell === 1) { | |
| context.fillStyle = '#fff' | |
| drawTile(i,j) | |
| } | |
| } | |
| } | |
| function drawVertex(v) { | |
| context.beginPath() | |
| context.arc(v[0]*tileX, v[1]*tileY, 0.25*Math.min(tileX,tileY), 0, 2.0*Math.PI) | |
| context.fill() | |
| } | |
| function drawLine(a, b) { | |
| context.beginPath() | |
| context.moveTo(a[0]*tileX, a[1]*tileY) | |
| context.lineTo(b[0]*tileX, b[1]*tileY) | |
| context.stroke() | |
| } | |
| function drawBox(box) { | |
| drawLine([box[0], box[1]], [box[2], box[1]]) | |
| drawLine([box[0], box[3]], [box[2], box[3]]) | |
| drawLine([box[0], box[1]], [box[0], box[3]]) | |
| drawLine([box[2], box[1]], [box[2], box[3]]) | |
| } | |
| var boxes = makeBoxes(grid.transpose(1,0), true).map(function(b) { return [b[0][0],b[0][1],b[1][0],b[1][1]] }) | |
| context.strokeStyle = 'rgb(0,128,128)' | |
| boxes.forEach(drawBox) | |
| var loops = getContour(grid.transpose(1,0)) | |
| var corners = [] | |
| var segments = [] | |
| context.strokeStyle = '#00f' | |
| loops.forEach(function(polygon) { | |
| for(var i=0; i<polygon.length; ++i) { | |
| var a = polygon[(i+polygon.length-1)%polygon.length] | |
| var b = polygon[i] | |
| var c = polygon[(i+1)%polygon.length] | |
| drawLine(a, b) | |
| segments.push([a,b]) | |
| if(orient(a, b, c) > 0) { | |
| var offset = [0,0] | |
| for(var j=0; j<2; ++j) { | |
| if(b[j] - a[j]) { | |
| offset[j] = b[j] - a[j] | |
| } else { | |
| offset[j] = b[j] - c[j] | |
| } | |
| offset[j] = b[j]+Math.min(Math.round(offset[j]/Math.abs(offset[j]))|0, 0) | |
| } | |
| corners.push([b, offset]) | |
| } | |
| } | |
| }) | |
| //Remove duplicate corner pairs | |
| function comparePair(a, b) { | |
| var d = a[0] - b[0] | |
| if(d) { return d } | |
| return a[1] - b[1] | |
| } | |
| function comparePoint(p,q) { | |
| return comparePair(p[0], q[0]) | |
| } | |
| corners.sort(comparePoint) | |
| var ptr = 0 | |
| for(var i=0; i<corners.length; ++i) { | |
| if(i+1 < corners.length) { | |
| if(comparePoint(corners[i], corners[i+1]) === 0) { | |
| i += 1 | |
| continue | |
| } | |
| } | |
| corners[ptr++] = corners[i] | |
| } | |
| corners.length = ptr | |
| //Extract tiles | |
| var cornerVerts = corners.map(function(c) { return c[0] }) | |
| var cornerTiles = uniq(corners.map(function(c) { return c[1] }), comparePair, false) | |
| context.fillStyle = 'rgba(128, 128, 0, 0.5)' | |
| cornerTiles.forEach(function(tile) { | |
| drawTile(tile[0], tile[1]) | |
| }) | |
| //Draw all the corner points | |
| context.fillStyle = '#ff0' | |
| cornerVerts.forEach(drawVertex) | |
| //Build rbush from boxes | |
| var rtree = rbush(9) | |
| rtree.load(boxes) | |
| function drawRay(v, x) { | |
| var ray = [Math.min(v[0], x), v[1], Math.max(v[0],x), v[1]] | |
| drawLine([ray[0]+0.5, ray[1]+0.5], [ray[2]+0.5, ray[3]+0.5]) | |
| } | |
| function stabTile(v) { | |
| return rtree.search([v[0]+0.5,v[1]+0.5,v[0]+0.5,v[1]+0.5]).length > 0 | |
| } | |
| function stabRay(v, x) { | |
| return rtree.search([Math.min(v[0], x)+0.5, v[1]+0.5, Math.max(v[0],x)+0.5, v[1]+0.5]).length > 0 | |
| } | |
| function stabBox(a, b) { | |
| return rtree.search([ | |
| Math.min(a[0], b[0])+0.5, | |
| Math.min(a[1], b[1])+0.5, | |
| Math.max(a[0], b[0])+0.5, | |
| Math.max(a[1], b[1])+0.5 ]).length > 0 | |
| } | |
| function makePartition(x, corners) { | |
| var left = [] | |
| var right = [] | |
| var on = [] | |
| for(var i=0; i<corners.length; ++i) { | |
| var c = corners[i] | |
| if(!stabRay(c, x)) { | |
| on.push(c) | |
| } | |
| if(c[0] < x) { | |
| left.push(c) | |
| } else if(c[0] > x) { | |
| right.push(c) | |
| } | |
| } | |
| //Sort on events by x | |
| on.sort(function(a, b) { | |
| var d = a[1] - b[1] | |
| if(d) { return d } | |
| return a[0] - b[0] | |
| }) | |
| //Construct vertices and horizontal edges | |
| var verts = [] | |
| var edges = [] | |
| for(var i=0; i<on.length; ) { | |
| var l = x | |
| var r = x | |
| var v = on[i] | |
| var y = v[1] | |
| while(i < on.length && on[i][1] === y && on[i][0] < x) { | |
| l = on[i++][0] | |
| } | |
| while(i < on.length && on[i][1] === y && on[i][0] === x) { | |
| ++i | |
| } | |
| if(i < on.length && on[i][1] === y) { | |
| r = on[i++][0] | |
| while(i < on.length && on[i][1] === y) { | |
| ++i | |
| } | |
| } | |
| verts.push([x, y]) | |
| var e = [] | |
| if(l < x) { | |
| e.push([l, y]) | |
| } | |
| if(r > x) { | |
| e.push([r, y]) | |
| } | |
| edges.push(e) | |
| } | |
| for(var i=0; i+1<verts.length; ++i) { | |
| if(stabBox(verts[i], verts[i+1])) { | |
| continue | |
| } | |
| edges[i].push(verts[i+1]) | |
| edges[i+1].push(verts[i]) | |
| } | |
| return { | |
| x: x, | |
| left: left, | |
| right: right, | |
| verts: verts, | |
| edges: edges | |
| } | |
| } | |
| function drawPartition(partition) { | |
| var x = partition.x | |
| context.strokeStyle = '#f0f' | |
| context.fillStyle = '#f0f' | |
| partition.verts.forEach(function(v, i) { | |
| drawVertex([v[0]+0.5, v[1]+0.5]) | |
| var e = partition.edges[i] | |
| for(var i=0; i<e.length; ++i) { | |
| drawLine([v[0]+0.5, v[1]+0.5], [e[i][0]+0.5, e[i][1]+0.5]) | |
| } | |
| }) | |
| } | |
| function glueVertex(tree, e, v) { | |
| if(e[0] < tree.x) { | |
| glueVertex(tree.left, e, v) | |
| } else if(e[0] > tree.x) { | |
| glueVertex(tree.right, e, v) | |
| } else { | |
| var idx = bsearch.eq(tree.verts, e, comparePair) | |
| tree.edges[idx].push(v) | |
| } | |
| } | |
| function makeClarksonTree(corners) { | |
| if(corners.length === 0) { | |
| return null | |
| } | |
| var x = corners[corners.length>>>1][0] | |
| var partition = makePartition(x, corners) | |
| drawPartition(partition) | |
| var leftTree = makeClarksonTree(partition.left) | |
| var rightTree = makeClarksonTree(partition.right) | |
| //Glue left/right tree edges to vertex | |
| for(var i=0; i<partition.edges.length; ++i) { | |
| var v = partition.verts[i] | |
| var e = partition.edges[i] | |
| for(var j=0; j<e.length; ++j) { | |
| if(e[j][0] < v[0] && leftTree) { | |
| glueVertex(leftTree, e[j], v) | |
| } else if(e[j][0] > v[0] && rightTree) { | |
| glueVertex(rightTree, e[j], v) | |
| } | |
| } | |
| } | |
| return { | |
| x: x, | |
| verts: partition.verts, | |
| edges: partition.edges, | |
| left: leftTree, | |
| right: rightTree | |
| } | |
| } | |
| var tree = makeClarksonTree(cornerTiles) | |
| function addEdge(a, b) { | |
| if(!stabBox(a, b)) { | |
| drawLine([a[0]+0.5, a[1]+0.5], [b[0]+0.5, a[1]+0.5]) | |
| drawLine([b[0]+0.5, a[1]+0.5], [b[0]+0.5, b[1]+0.5]) | |
| } | |
| } | |
| function getConnectingVerts(node, vertex) { | |
| if(!node) { | |
| return | |
| } | |
| var idx = bsearch.le(node.verts, vertex, function(a, b) { | |
| return a[1] - vertex[1] | |
| }) | |
| if(idx < 0) { | |
| addEdge(node.verts[0], vertex) | |
| } else if(node.verts[idx][1] === vertex[1]) { | |
| addEdge(node.verts[idx], vertex) | |
| } else { | |
| addEdge(node.verts[idx], vertex) | |
| if(idx < node.verts.length - 1) { | |
| addEdge(node.verts[idx+1], vertex) | |
| } | |
| } | |
| if(vertex[0] < node.x) { | |
| getConnectingVerts(node.left, vertex) | |
| } else if(vertex[0] > node.x) { | |
| getConnectingVerts(node.right, vertex) | |
| } | |
| } | |
| //Render the root | |
| context.fillStyle = '#0f0' | |
| context.strokeStyle = '#0f0' | |
| drawVertex([root[0]+0.5, root[1]+0.5]) | |
| getConnectingVerts(tree, root) | |
| addEdge(root, sink) | |
| //Render the sink | |
| context.fillStyle = '#f00' | |
| context.strokeStyle = '#f00' | |
| drawVertex([sink[0]+0.5, sink[1]+0.5]) | |
| getConnectingVerts(tree, sink) | |
| } | |
| render() |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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";function mouseButtons(ev){if(typeof ev==="object"){if("buttons"in ev){return ev.buttons}else if("which"in ev){var b=ev.which;if(b===2){return 4}else if(b===3){return 2}else if(b>0){return 1<<b-1}}else if("button"in ev){var b=ev.button;if(b===1){return 4}else if(b===2){return 2}else if(b>=0){return 1<<b}}}return 0}exports.buttons=mouseButtons;function mouseElement(ev){return ev.target||ev.srcElement||window}exports.element=mouseElement;function mouseRelativeX(ev){if(typeof ev==="object"){if("offsetX"in ev){return ev.offsetX}var target=mouseElement(ev);if("clientX"in ev){return ev.clientX-target.clientLeft}if("pageX"in ev){return ev.pageX-target.offsetLeft}}return 0}exports.x=mouseRelativeX;function mouseRelativeY(ev){if(typeof ev==="object"){if("offsetY"in ev){return ev.offsetY}var target=mouseElement(ev);if("clientY"in ev){return ev.clientY-target.clientTop}if("pageX"in ev){return ev.pageY-target.offsetTop}}return 0}exports.y=mouseRelativeY},{}],"mouse-change":[function(require,module,exports){"use strict";module.exports=mouseListen;var mouse=require("mouse-event");function mouseListen(element,callback){if(!callback){callback=element;element=window}var buttonState=0;var x=0;var y=0;var mods={shift:false,alt:false,control:false,meta:false};function updateMods(ev){var changed=false;if("altKey"in ev){changed=changed||ev.altKey!==mods.alt;mods.alt=!!ev.altKey}if("shiftKey"in ev){changed=changed||ev.shiftKey!==mods.shift;mods.shift=!!ev.shiftKey}if("ctrlKey"in ev){changed=changed||ev.ctrlKey!==mods.control;mods.control=!!ev.ctrlKey}if("metaKey"in ev){changed=changed||ev.metaKey!==mods.meta;mods.meta=!!ev.metaKey}return changed}function handleEvent(nextButtons,ev){var nextX=mouse.x(ev);var nextY=mouse.y(ev);if("buttons"in ev){nextButtons=ev.buttons|0}if(nextButtons!==buttonState||nextX!==x||nextY!==y||updateMods(ev)){buttonState=nextButtons|0;x=nextX||0;y=nextY||0;callback(buttonState,x,y,mods)}}function clearState(ev){handleEvent(0,ev)}function handleBlur(){if(buttonState||x||y||mods.shift||mods.alt||mods.meta||mods.control){x=y=0;buttonState=0;mods.shift=mods.alt=mods.control=mods.meta=false;callback(0,0,0,mods)}}function handleMods(ev){if(updateMods(ev)){callback(buttonState,x,y,mods)}}element.addEventListener("mousemove",function(ev){if(mouse.buttons(ev)===0){handleEvent(0,ev)}else{handleEvent(buttonState,ev)}});element.addEventListener("mousedown",function(ev){handleEvent(buttonState|mouse.buttons(ev),ev)});element.addEventListener("mouseup",function(ev){handleEvent(buttonState&~mouse.buttons(ev),ev)});element.addEventListener("mouseleave",clearState);element.addEventListener("mouseenter",clearState);element.addEventListener("mouseout",clearState);element.addEventListener("mouseover",clearState);element.addEventListener("blur",handleBlur);element.addEventListener("keyup",handleMods);element.addEventListener("keydown",handleMods);element.addEventListener("keypress",handleMods);if(element!==window){window.addEventListener("blur",handleBlur);window.addEventListener("keyup",handleMods);window.addEventListener("keydown",handleMods);window.addEventListener("keypress",handleMods)}}},{"mouse-event":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}({1:[function(require,module,exports){var base64=require("base64-js");var ieee754=require("ieee754");var isArray=require("is-array");exports.Buffer=Buffer;exports.SlowBuffer=SlowBuffer;exports.INSPECT_MAX_BYTES=50;Buffer.poolSize=8192;var kMaxLength=1073741823;var rootParent={};Buffer.TYPED_ARRAY_SUPPORT=function(){try{var buf=new ArrayBuffer(0);var arr=new Uint8Array(buf);arr.foo=function(){return 42};return 42===arr.foo()&&typeof arr.subarray==="function"&&new Uint8Array(1).subarray(1,1).byteLength===0}catch(e){return false}}();function Buffer(subject,encoding,noZero){if(!(this instanceof Buffer))return new Buffer(subject,encoding,noZero);var type=typeof subject;var length;if(type==="number")length=subject>0?subject>>>0:0;else if(type==="string"){length=Buffer.byteLength(subject,encoding)}else if(type==="object"&&subject!==null){if(subject.type==="Buffer"&&isArray(subject.data))subject=subject.data;length=+subject.length>0?Math.floor(+subject.length):0}else throw new TypeError("must start with number, buffer, array or string");if(length>kMaxLength)throw new RangeError("Attempt to allocate Buffer larger than maximum "+"size: 0x"+kMaxLength.toString(16)+" bytes");var buf;if(Buffer.TYPED_ARRAY_SUPPORT){buf=Buffer._augment(new Uint8Array(length))}else{buf=this;buf.length=length;buf._isBuffer=true}var i;if(Buffer.TYPED_ARRAY_SUPPORT&&typeof subject.byteLength==="number"){buf._set(subject)}else if(isArrayish(subject)){if(Buffer.isBuffer(subject)){for(i=0;i<length;i++)buf[i]=subject.readUInt8(i)}else{for(i=0;i<length;i++)buf[i]=(subject[i]%256+256)%256}}else if(type==="string"){buf.write(subject,0,encoding)}else if(type==="number"&&!Buffer.TYPED_ARRAY_SUPPORT&&!noZero){for(i=0;i<length;i++){buf[i]=0}}if(length>0&&length<=Buffer.poolSize)buf.parent=rootParent;return buf}function SlowBuffer(subject,encoding,noZero){if(!(this instanceof SlowBuffer))return new SlowBuffer(subject,encoding,noZero);var buf=new Buffer(subject,encoding,noZero);delete buf.parent;return buf}Buffer.isBuffer=function(b){return!!(b!=null&&b._isBuffer)};Buffer.compare=function(a,b){if(!Buffer.isBuffer(a)||!Buffer.isBuffer(b))throw new TypeError("Arguments must be Buffers");var x=a.length;var y=b.length;for(var i=0,len=Math.min(x,y);i<len&&a[i]===b[i];i++){}if(i!==len){x=a[i];y=b[i]}if(x<y)return-1;if(y<x)return 1;return 0};Buffer.isEncoding=function(encoding){switch(String(encoding).toLowerCase()){case"hex":case"utf8":case"utf-8":case"ascii":case"binary":case"base64":case"raw":case"ucs2":case"ucs-2":case"utf16le":case"utf-16le":return true;default:return false}};Buffer.concat=function(list,totalLength){if(!isArray(list))throw new TypeError("Usage: Buffer.concat(list[, length])");if(list.length===0){return new Buffer(0)}else if(list.length===1){return list[0]}var i;if(totalLength===undefined){totalLength=0;for(i=0;i<list.length;i++){totalLength+=list[i].length}}var buf=new Buffer(totalLength);var pos=0;for(i=0;i<list.length;i++){var item=list[i];item.copy(buf,pos);pos+=item.length}return buf};Buffer.byteLength=function(str,encoding){var ret;str=str+"";switch(encoding||"utf8"){case"ascii":case"binary":case"raw":ret=str.length;break;case"ucs2":case"ucs-2":case"utf16le":case"utf-16le":ret=str.length*2;break;case"hex":ret=str.length>>>1;break;case"utf8":case"utf-8":ret=utf8ToBytes(str).length;break;case"base64":ret=base64ToBytes(str).length;break;default:ret=str.length}return ret};Buffer.prototype.length=undefined;Buffer.prototype.parent=undefined;Buffer.prototype.toString=function(encoding,start,end){var loweredCase=false;start=start>>>0;end=end===undefined||end===Infinity?this.length:end>>>0;if(!encoding)encoding="utf8";if(start<0)start=0;if(end>this.length)end=this.length;if(end<=start)return"";while(true){switch(encoding){case"hex":return hexSlice(this,start,end);case"utf8":case"utf-8":return utf8Slice(this,start,end);case"ascii":return asciiSlice(this,start,end);case"binary":return binarySlice(this,start,end);case"base64":return base64Slice(this,start,end);case"ucs2":case"ucs-2":case"utf16le":case"utf-16le":return utf16leSlice(this,start,end);default:if(loweredCase)throw new TypeError("Unknown encoding: "+encoding);encoding=(encoding+"").toLowerCase();loweredCase=true}}};Buffer.prototype.equals=function(b){if(!Buffer.isBuffer(b))throw new TypeError("Argument must be a Buffer");return Buffer.compare(this,b)===0};Buffer.prototype.inspect=function(){var str="";var max=exports.INSPECT_MAX_BYTES;if(this.length>0){str=this.toString("hex",0,max).match(/.{2}/g).join(" ");if(this.length>max)str+=" ... "}return"<Buffer "+str+">"};Buffer.prototype.compare=function(b){if(!Buffer.isBuffer(b))throw new TypeError("Argument must be a Buffer");return Buffer.compare(this,b)};Buffer.prototype.get=function(offset){console.log(".get() is deprecated. Access using array indexes instead.");return this.readUInt8(offset)};Buffer.prototype.set=function(v,offset){console.log(".set() is deprecated. Access using array indexes instead.");return this.writeUInt8(v,offset)};function hexWrite(buf,string,offset,length){offset=Number(offset)||0;var remaining=buf.length-offset;if(!length){length=remaining}else{length=Number(length);if(length>remaining){length=remaining}}var strLen=string.length;if(strLen%2!==0)throw new Error("Invalid hex string");if(length>strLen/2){length=strLen/2}for(var i=0;i<length;i++){var byte=parseInt(string.substr(i*2,2),16);if(isNaN(byte))throw new Error("Invalid hex string");buf[offset+i]=byte}return i}function utf8Write(buf,string,offset,length){var charsWritten=blitBuffer(utf8ToBytes(string,buf.length-offset),buf,offset,length);return charsWritten}function asciiWrite(buf,string,offset,length){var charsWritten=blitBuffer(asciiToBytes(string),buf,offset,length);return charsWritten}function binaryWrite(buf,string,offset,length){return asciiWrite(buf,string,offset,length)}function base64Write(buf,string,offset,length){var charsWritten=blitBuffer(base64ToBytes(string),buf,offset,length);return charsWritten}function utf16leWrite(buf,string,offset,length){var charsWritten=blitBuffer(utf16leToBytes(string,buf.length-offset),buf,offset,length,2);return charsWritten}Buffer.prototype.write=function(string,offset,length,encoding){if(isFinite(offset)){if(!isFinite(length)){encoding=length;length=undefined}}else{var swap=encoding;encoding=offset;offset=length;length=swap}offset=Number(offset)||0;if(length<0||offset<0||offset>this.length)throw new RangeError("attempt to write outside buffer bounds");var remaining=this.length-offset;if(!length){length=remaining}else{length=Number(length);if(length>remaining){length=remaining}}encoding=String(encoding||"utf8").toLowerCase();var ret;switch(encoding){case"hex":ret=hexWrite(this,string,offset,length);break;case"utf8":case"utf-8":ret=utf8Write(this,string,offset,length);break;case"ascii":ret=asciiWrite(this,string,offset,length);break;case"binary":ret=binaryWrite(this,string,offset,length);break;case"base64":ret=base64Write(this,string,offset,length);break;case"ucs2":case"ucs-2":case"utf16le":case"utf-16le":ret=utf16leWrite(this,string,offset,length);break;default:throw new TypeError("Unknown encoding: "+encoding)}return ret};Buffer.prototype.toJSON=function(){return{type:"Buffer",data:Array.prototype.slice.call(this._arr||this,0)}};function base64Slice(buf,start,end){if(start===0&&end===buf.length){return base64.fromByteArray(buf)}else{return base64.fromByteArray(buf.slice(start,end))}}function utf8Slice(buf,start,end){var res="";var tmp="";end=Math.min(buf.length,end);for(var i=start;i<end;i++){if(buf[i]<=127){res+=decodeUtf8Char(tmp)+String.fromCharCode(buf[i]);tmp=""}else{tmp+="%"+buf[i].toString(16)}}return res+decodeUtf8Char(tmp)}function asciiSlice(buf,start,end){var ret="";end=Math.min(buf.length,end);for(var i=start;i<end;i++){ret+=String.fromCharCode(buf[i]&127)}return ret}function binarySlice(buf,start,end){var ret="";end=Math.min(buf.length,end);for(var i=start;i<end;i++){ret+=String.fromCharCode(buf[i])}return ret}function hexSlice(buf,start,end){var len=buf.length;if(!start||start<0)start=0;if(!end||end<0||end>len)end=len;var out="";for(var i=start;i<end;i++){out+=toHex(buf[i])}return out}function utf16leSlice(buf,start,end){var bytes=buf.slice(start,end);var res="";for(var i=0;i<bytes.length;i+=2){res+=String.fromCharCode(bytes[i]+bytes[i+1]*256)}return res}Buffer.prototype.slice=function(start,end){var len=this.length;start=~~start;end=end===undefined?len:~~end;if(start<0){start+=len;if(start<0)start=0}else if(start>len){start=len}if(end<0){end+=len;if(end<0)end=0}else if(end>len){end=len}if(end<start)end=start;var newBuf;if(Buffer.TYPED_ARRAY_SUPPORT){newBuf=Buffer._augment(this.subarray(start,end))}else{var sliceLen=end-start;newBuf=new Buffer(sliceLen,undefined,true);for(var i=0;i<sliceLen;i++){newBuf[i]=this[i+start]}}if(newBuf.length)newBuf.parent=this.parent||this;return newBuf};function checkOffset(offset,ext,length){if(offset%1!==0||offset<0)throw new RangeError("offset is not uint");if(offset+ext>length)throw new RangeError("Trying to access beyond buffer length")}Buffer.prototype.readUIntLE=function(offset,byteLength,noAssert){offset=offset>>>0;byteLength=byteLength>>>0;if(!noAssert)checkOffset(offset,byteLength,this.length);var val=this[offset];var mul=1;var i=0;while(++i<byteLength&&(mul*=256))val+=this[offset+i]*mul;return val};Buffer.prototype.readUIntBE=function(offset,byteLength,noAssert){offset=offset>>>0;byteLength=byteLength>>>0;if(!noAssert)checkOffset(offset,byteLength,this.length);var val=this[offset+--byteLength];var mul=1;while(byteLength>0&&(mul*=256))val+=this[offset+--byteLength]*mul;return val};Buffer.prototype.readUInt8=function(offset,noAssert){if(!noAssert)checkOffset(offset,1,this.length);return this[offset]};Buffer.prototype.readUInt16LE=function(offset,noAssert){if(!noAssert)checkOffset(offset,2,this.length);return this[offset]|this[offset+1]<<8};Buffer.prototype.readUInt16BE=function(offset,noAssert){if(!noAssert)checkOffset(offset,2,this.length);return this[offset]<<8|this[offset+1]};Buffer.prototype.readUInt32LE=function(offset,noAssert){if(!noAssert)checkOffset(offset,4,this.length);return(this[offset]|this[offset+1]<<8|this[offset+2]<<16)+this[offset+3]*16777216};Buffer.prototype.readUInt32BE=function(offset,noAssert){if(!noAssert)checkOffset(offset,4,this.length);return this[offset]*16777216+(this[offset+1]<<16|this[offset+2]<<8|this[offset+3])};Buffer.prototype.readIntLE=function(offset,byteLength,noAssert){offset=offset>>>0;byteLength=byteLength>>>0;if(!noAssert)checkOffset(offset,byteLength,this.length);var val=this[offset];var mul=1;var i=0;while(++i<byteLength&&(mul*=256))val+=this[offset+i]*mul;mul*=128;if(val>=mul)val-=Math.pow(2,8*byteLength);return val};Buffer.prototype.readIntBE=function(offset,byteLength,noAssert){offset=offset>>>0;byteLength=byteLength>>>0;if(!noAssert)checkOffset(offset,byteLength,this.length);var i=byteLength;var mul=1;var val=this[offset+--i];while(i>0&&(mul*=256))val+=this[offset+--i]*mul;mul*=128;if(val>=mul)val-=Math.pow(2,8*byteLength);return val};Buffer.prototype.readInt8=function(offset,noAssert){if(!noAssert)checkOffset(offset,1,this.length);if(!(this[offset]&128))return this[offset];return(255-this[offset]+1)*-1};Buffer.prototype.readInt16LE=function(offset,noAssert){if(!noAssert)checkOffset(offset,2,this.length);var val=this[offset]|this[offset+1]<<8;return val&32768?val|4294901760:val};Buffer.prototype.readInt16BE=function(offset,noAssert){if(!noAssert)checkOffset(offset,2,this.length);var val=this[offset+1]|this[offset]<<8;return val&32768?val|4294901760:val};Buffer.prototype.readInt32LE=function(offset,noAssert){if(!noAssert)checkOffset(offset,4,this.length);return this[offset]|this[offset+1]<<8|this[offset+2]<<16|this[offset+3]<<24};Buffer.prototype.readInt32BE=function(offset,noAssert){if(!noAssert)checkOffset(offset,4,this.length);return this[offset]<<24|this[offset+1]<<16|this[offset+2]<<8|this[offset+3]};Buffer.prototype.readFloatLE=function(offset,noAssert){if(!noAssert)checkOffset(offset,4,this.length);return ieee754.read(this,offset,true,23,4)};Buffer.prototype.readFloatBE=function(offset,noAssert){if(!noAssert)checkOffset(offset,4,this.length);return ieee754.read(this,offset,false,23,4)};Buffer.prototype.readDoubleLE=function(offset,noAssert){if(!noAssert)checkOffset(offset,8,this.length);return ieee754.read(this,offset,true,52,8)};Buffer.prototype.readDoubleBE=function(offset,noAssert){if(!noAssert)checkOffset(offset,8,this.length);return ieee754.read(this,offset,false,52,8)};function checkInt(buf,value,offset,ext,max,min){if(!Buffer.isBuffer(buf))throw new TypeError("buffer must be a Buffer instance");if(value>max||value<min)throw new RangeError("value is out of bounds");if(offset+ext>buf.length)throw new RangeError("index out of range")}Buffer.prototype.writeUIntLE=function(value,offset,byteLength,noAssert){value=+value;offset=offset>>>0;byteLength=byteLength>>>0;if(!noAssert)checkInt(this,value,offset,byteLength,Math.pow(2,8*byteLength),0);var mul=1;var i=0;this[offset]=value&255;while(++i<byteLength&&(mul*=256))this[offset+i]=value/mul>>>0&255;return offset+byteLength};Buffer.prototype.writeUIntBE=function(value,offset,byteLength,noAssert){value=+value;offset=offset>>>0;byteLength=byteLength>>>0;if(!noAssert)checkInt(this,value,offset,byteLength,Math.pow(2,8*byteLength),0);var i=byteLength-1;var mul=1;this[offset+i]=value&255;while(--i>=0&&(mul*=256))this[offset+i]=value/mul>>>0&255;return offset+byteLength};Buffer.prototype.writeUInt8=function(value,offset,noAssert){value=+value;offset=offset>>>0;if(!noAssert)checkInt(this,value,offset,1,255,0);if(!Buffer.TYPED_ARRAY_SUPPORT)value=Math.floor(value);this[offset]=value;return offset+1};function objectWriteUInt16(buf,value,offset,littleEndian){if(value<0)value=65535+value+1;for(var i=0,j=Math.min(buf.length-offset,2);i<j;i++){buf[offset+i]=(value&255<<8*(littleEndian?i:1-i))>>>(littleEndian?i:1-i)*8}}Buffer.prototype.writeUInt16LE=function(value,offset,noAssert){value=+value;offset=offset>>>0;if(!noAssert)checkInt(this,value,offset,2,65535,0);if(Buffer.TYPED_ARRAY_SUPPORT){this[offset]=value;this[offset+1]=value>>>8}else objectWriteUInt16(this,value,offset,true);return offset+2};Buffer.prototype.writeUInt16BE=function(value,offset,noAssert){value=+value;offset=offset>>>0;if(!noAssert)checkInt(this,value,offset,2,65535,0);if(Buffer.TYPED_ARRAY_SUPPORT){this[offset]=value>>>8;this[offset+1]=value}else objectWriteUInt16(this,value,offset,false);return offset+2};function objectWriteUInt32(buf,value,offset,littleEndian){if(value<0)value=4294967295+value+1;for(var i=0,j=Math.min(buf.length-offset,4);i<j;i++){buf[offset+i]=value>>>(littleEndian?i:3-i)*8&255}}Buffer.prototype.writeUInt32LE=function(value,offset,noAssert){value=+value;offset=offset>>>0;if(!noAssert)checkInt(this,value,offset,4,4294967295,0);if(Buffer.TYPED_ARRAY_SUPPORT){this[offset+3]=value>>>24;this[offset+2]=value>>>16;this[offset+1]=value>>>8;this[offset]=value}else objectWriteUInt32(this,value,offset,true);return offset+4};Buffer.prototype.writeUInt32BE=function(value,offset,noAssert){value=+value;offset=offset>>>0;if(!noAssert)checkInt(this,value,offset,4,4294967295,0);if(Buffer.TYPED_ARRAY_SUPPORT){this[offset]=value>>>24;this[offset+1]=value>>>16;this[offset+2]=value>>>8;this[offset+3]=value}else objectWriteUInt32(this,value,offset,false);return offset+4};Buffer.prototype.writeIntLE=function(value,offset,byteLength,noAssert){value=+value;offset=offset>>>0;if(!noAssert){checkInt(this,value,offset,byteLength,Math.pow(2,8*byteLength-1)-1,-Math.pow(2,8*byteLength-1))}var i=0;var mul=1;var sub=value<0?1:0;this[offset]=value&255;while(++i<byteLength&&(mul*=256))this[offset+i]=(value/mul>>0)-sub&255;return offset+byteLength};Buffer.prototype.writeIntBE=function(value,offset,byteLength,noAssert){value=+value;offset=offset>>>0;if(!noAssert){checkInt(this,value,offset,byteLength,Math.pow(2,8*byteLength-1)-1,-Math.pow(2,8*byteLength-1))}var i=byteLength-1;var mul=1;var sub=value<0?1:0;this[offset+i]=value&255;while(--i>=0&&(mul*=256))this[offset+i]=(value/mul>>0)-sub&255;return offset+byteLength};Buffer.prototype.writeInt8=function(value,offset,noAssert){value=+value;offset=offset>>>0;if(!noAssert)checkInt(this,value,offset,1,127,-128);if(!Buffer.TYPED_ARRAY_SUPPORT)value=Math.floor(value);if(value<0)value=255+value+1;this[offset]=value;return offset+1};Buffer.prototype.writeInt16LE=function(value,offset,noAssert){value=+value;offset=offset>>>0;if(!noAssert)checkInt(this,value,offset,2,32767,-32768);if(Buffer.TYPED_ARRAY_SUPPORT){this[offset]=value;this[offset+1]=value>>>8}else objectWriteUInt16(this,value,offset,true);return offset+2};Buffer.prototype.writeInt16BE=function(value,offset,noAssert){value=+value;offset=offset>>>0;if(!noAssert)checkInt(this,value,offset,2,32767,-32768);if(Buffer.TYPED_ARRAY_SUPPORT){this[offset]=value>>>8;this[offset+1]=value}else objectWriteUInt16(this,value,offset,false);return offset+2};Buffer.prototype.writeInt32LE=function(value,offset,noAssert){value=+value;offset=offset>>>0;if(!noAssert)checkInt(this,value,offset,4,2147483647,-2147483648);if(Buffer.TYPED_ARRAY_SUPPORT){this[offset]=value;this[offset+1]=value>>>8;this[offset+2]=value>>>16;this[offset+3]=value>>>24}else objectWriteUInt32(this,value,offset,true);return offset+4};Buffer.prototype.writeInt32BE=function(value,offset,noAssert){value=+value;offset=offset>>>0;if(!noAssert)checkInt(this,value,offset,4,2147483647,-2147483648);if(value<0)value=4294967295+value+1;if(Buffer.TYPED_ARRAY_SUPPORT){this[offset]=value>>>24;this[offset+1]=value>>>16;this[offset+2]=value>>>8;this[offset+3]=value}else objectWriteUInt32(this,value,offset,false);return offset+4};function checkIEEE754(buf,value,offset,ext,max,min){if(value>max||value<min)throw new RangeError("value is out of bounds");if(offset+ext>buf.length)throw new RangeError("index out of range");if(offset<0)throw new RangeError("index out of range")}function writeFloat(buf,value,offset,littleEndian,noAssert){if(!noAssert)checkIEEE754(buf,value,offset,4,3.4028234663852886e38,-3.4028234663852886e38);ieee754.write(buf,value,offset,littleEndian,23,4);return offset+4}Buffer.prototype.writeFloatLE=function(value,offset,noAssert){return writeFloat(this,value,offset,true,noAssert)};Buffer.prototype.writeFloatBE=function(value,offset,noAssert){return writeFloat(this,value,offset,false,noAssert)};function writeDouble(buf,value,offset,littleEndian,noAssert){if(!noAssert)checkIEEE754(buf,value,offset,8,1.7976931348623157e308,-1.7976931348623157e308);ieee754.write(buf,value,offset,littleEndian,52,8);return offset+8}Buffer.prototype.writeDoubleLE=function(value,offset,noAssert){return writeDouble(this,value,offset,true,noAssert)};Buffer.prototype.writeDoubleBE=function(value,offset,noAssert){return writeDouble(this,value,offset,false,noAssert)};Buffer.prototype.copy=function(target,target_start,start,end){var source=this;if(!start)start=0;if(!end&&end!==0)end=this.length;if(target_start>=target.length)target_start=target.length;if(!target_start)target_start=0;if(end>0&&end<start)end=start;if(end===start)return 0;if(target.length===0||source.length===0)return 0;if(target_start<0)throw new RangeError("targetStart out of bounds");if(start<0||start>=source.length)throw new RangeError("sourceStart out of bounds");if(end<0)throw new RangeError("sourceEnd out of bounds");if(end>this.length)end=this.length;if(target.length-target_start<end-start)end=target.length-target_start+start;var len=end-start;if(len<1e3||!Buffer.TYPED_ARRAY_SUPPORT){for(var i=0;i<len;i++){target[i+target_start]=this[i+start]}}else{target._set(this.subarray(start,start+len),target_start)}return len};Buffer.prototype.fill=function(value,start,end){if(!value)value=0;if(!start)start=0;if(!end)end=this.length;if(end<start)throw new RangeError("end < start");if(end===start)return;if(this.length===0)return;if(start<0||start>=this.length)throw new RangeError("start out of bounds");if(end<0||end>this.length)throw new RangeError("end out of bounds");var i;if(typeof value==="number"){for(i=start;i<end;i++){this[i]=value}}else{var bytes=utf8ToBytes(value.toString());var len=bytes.length;for(i=start;i<end;i++){this[i]=bytes[i%len]}}return this};Buffer.prototype.toArrayBuffer=function(){if(typeof Uint8Array!=="undefined"){if(Buffer.TYPED_ARRAY_SUPPORT){return new Buffer(this).buffer}else{var buf=new Uint8Array(this.length);for(var i=0,len=buf.length;i<len;i+=1){buf[i]=this[i]}return buf.buffer}}else{throw new TypeError("Buffer.toArrayBuffer not supported in this browser")}};var BP=Buffer.prototype;Buffer._augment=function(arr){arr.constructor=Buffer;arr._isBuffer=true;arr._get=arr.get;arr._set=arr.set;arr.get=BP.get;arr.set=BP.set;arr.write=BP.write;arr.toString=BP.toString;arr.toLocaleString=BP.toString;arr.toJSON=BP.toJSON;arr.equals=BP.equals;arr.compare=BP.compare;arr.copy=BP.copy;arr.slice=BP.slice;arr.readUIntLE=BP.readUIntLE;arr.readUIntBE=BP.readUIntBE;arr.readUInt8=BP.readUInt8;arr.readUInt16LE=BP.readUInt16LE;arr.readUInt16BE=BP.readUInt16BE;arr.readUInt32LE=BP.readUInt32LE;arr.readUInt32BE=BP.readUInt32BE;arr.readIntLE=BP.readIntLE;arr.readIntBE=BP.readIntBE;arr.readInt8=BP.readInt8;arr.readInt16LE=BP.readInt16LE;arr.readInt16BE=BP.readInt16BE;arr.readInt32LE=BP.readInt32LE;arr.readInt32BE=BP.readInt32BE;arr.readFloatLE=BP.readFloatLE;arr.readFloatBE=BP.readFloatBE;arr.readDoubleLE=BP.readDoubleLE;arr.readDoubleBE=BP.readDoubleBE;arr.writeUInt8=BP.writeUInt8;arr.writeUIntLE=BP.writeUIntLE;arr.writeUIntBE=BP.writeUIntBE;arr.writeUInt16LE=BP.writeUInt16LE;arr.writeUInt16BE=BP.writeUInt16BE;arr.writeUInt32LE=BP.writeUInt32LE;arr.writeUInt32BE=BP.writeUInt32BE;arr.writeIntLE=BP.writeIntLE;arr.writeIntBE=BP.writeIntBE;arr.writeInt8=BP.writeInt8;arr.writeInt16LE=BP.writeInt16LE;arr.writeInt16BE=BP.writeInt16BE;arr.writeInt32LE=BP.writeInt32LE;arr.writeInt32BE=BP.writeInt32BE;arr.writeFloatLE=BP.writeFloatLE;arr.writeFloatBE=BP.writeFloatBE;arr.writeDoubleLE=BP.writeDoubleLE;arr.writeDoubleBE=BP.writeDoubleBE;arr.fill=BP.fill;arr.inspect=BP.inspect;arr.toArrayBuffer=BP.toArrayBuffer;return arr};var INVALID_BASE64_RE=/[^+\/0-9A-z\-]/g;function base64clean(str){str=stringtrim(str).replace(INVALID_BASE64_RE,"");if(str.length<2)return"";while(str.length%4!==0){str=str+"="}return str}function stringtrim(str){if(str.trim)return str.trim();return str.replace(/^\s+|\s+$/g,"")}function isArrayish(subject){return isArray(subject)||Buffer.isBuffer(subject)||subject&&typeof subject==="object"&&typeof subject.length==="number"}function toHex(n){if(n<16)return"0"+n.toString(16);return n.toString(16)}function utf8ToBytes(string,units){var codePoint,length=string.length;var leadSurrogate=null;units=units||Infinity;var bytes=[];var i=0;for(;i<length;i++){codePoint=string.charCodeAt(i);if(codePoint>55295&&codePoint<57344){if(leadSurrogate){if(codePoint<56320){if((units-=3)>-1)bytes.push(239,191,189);leadSurrogate=codePoint;continue}else{codePoint=leadSurrogate-55296<<10|codePoint-56320|65536;leadSurrogate=null}}else{if(codePoint>56319){if((units-=3)>-1)bytes.push(239,191,189);continue}else if(i+1===length){if((units-=3)>-1)bytes.push(239,191,189);continue}else{leadSurrogate=codePoint;continue}}}else if(leadSurrogate){if((units-=3)>-1)bytes.push(239,191,189);leadSurrogate=null}if(codePoint<128){if((units-=1)<0)break;bytes.push(codePoint)}else if(codePoint<2048){if((units-=2)<0)break;bytes.push(codePoint>>6|192,codePoint&63|128)}else if(codePoint<65536){if((units-=3)<0)break;bytes.push(codePoint>>12|224,codePoint>>6&63|128,codePoint&63|128)}else if(codePoint<2097152){if((units-=4)<0)break;bytes.push(codePoint>>18|240,codePoint>>12&63|128,codePoint>>6&63|128,codePoint&63|128)}else{throw new Error("Invalid code point")}}return bytes}function asciiToBytes(str){var byteArray=[];for(var i=0;i<str.length;i++){byteArray.push(str.charCodeAt(i)&255)}return byteArray}function utf16leToBytes(str,units){var c,hi,lo;var byteArray=[];for(var i=0;i<str.length;i++){if((units-=2)<0)break;c=str.charCodeAt(i);hi=c>>8;lo=c%256;byteArray.push(lo);byteArray.push(hi)}return byteArray}function base64ToBytes(str){return base64.toByteArray(base64clean(str))}function blitBuffer(src,dst,offset,length,unitSize){if(unitSize)length-=length%unitSize;for(var i=0;i<length;i++){if(i+offset>=dst.length||i>=src.length)break;dst[i+offset]=src[i]}return i}function decodeUtf8Char(str){try{return decodeURIComponent(str)}catch(err){return String.fromCharCode(65533)}}},{"base64-js":2,ieee754:3,"is-array":4}],2:[function(require,module,exports){var lookup="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";(function(exports){"use strict";var Arr=typeof Uint8Array!=="undefined"?Uint8Array:Array;var PLUS="+".charCodeAt(0);var SLASH="/".charCodeAt(0);var NUMBER="0".charCodeAt(0);var LOWER="a".charCodeAt(0);var UPPER="A".charCodeAt(0);var PLUS_URL_SAFE="-".charCodeAt(0);var SLASH_URL_SAFE="_".charCodeAt(0);function decode(elt){var code=elt.charCodeAt(0);if(code===PLUS||code===PLUS_URL_SAFE)return 62;if(code===SLASH||code===SLASH_URL_SAFE)return 63;if(code<NUMBER)return-1;if(code<NUMBER+10)return code-NUMBER+26+26;if(code<UPPER+26)return code-UPPER;if(code<LOWER+26)return code-LOWER+26}function b64ToByteArray(b64){var i,j,l,tmp,placeHolders,arr;if(b64.length%4>0){throw new Error("Invalid string. Length must be a multiple of 4")}var len=b64.length;placeHolders="="===b64.charAt(len-2)?2:"="===b64.charAt(len-1)?1:0;arr=new Arr(b64.length*3/4-placeHolders);l=placeHolders>0?b64.length-4:b64.length;var L=0;function push(v){arr[L++]=v}for(i=0,j=0;i<l;i+=4,j+=3){tmp=decode(b64.charAt(i))<<18|decode(b64.charAt(i+1))<<12|decode(b64.charAt(i+2))<<6|decode(b64.charAt(i+3));push((tmp&16711680)>>16);push((tmp&65280)>>8);push(tmp&255)}if(placeHolders===2){tmp=decode(b64.charAt(i))<<2|decode(b64.charAt(i+1))>>4;push(tmp&255)}else if(placeHolders===1){tmp=decode(b64.charAt(i))<<10|decode(b64.charAt(i+1))<<4|decode(b64.charAt(i+2))>>2;push(tmp>>8&255);push(tmp&255)}return arr}function uint8ToBase64(uint8){var i,extraBytes=uint8.length%3,output="",temp,length;function encode(num){return lookup.charAt(num)}function tripletToBase64(num){return encode(num>>18&63)+encode(num>>12&63)+encode(num>>6&63)+encode(num&63)}for(i=0,length=uint8.length-extraBytes;i<length;i+=3){temp=(uint8[i]<<16)+(uint8[i+1]<<8)+uint8[i+2];output+=tripletToBase64(temp)}switch(extraBytes){case 1:temp=uint8[uint8.length-1];output+=encode(temp>>2);output+=encode(temp<<4&63);output+="==";break;case 2:temp=(uint8[uint8.length-2]<<8)+uint8[uint8.length-1];output+=encode(temp>>10);output+=encode(temp>>4&63);output+=encode(temp<<2&63);output+="=";break}return output}exports.toByteArray=b64ToByteArray;exports.fromByteArray=uint8ToBase64})(typeof exports==="undefined"?this.base64js={}:exports)},{}],3:[function(require,module,exports){exports.read=function(buffer,offset,isLE,mLen,nBytes){var e,m,eLen=nBytes*8-mLen-1,eMax=(1<<eLen)-1,eBias=eMax>>1,nBits=-7,i=isLE?nBytes-1:0,d=isLE?-1:1,s=buffer[offset+i];i+=d;e=s&(1<<-nBits)-1;s>>=-nBits;nBits+=eLen;for(;nBits>0;e=e*256+buffer[offset+i],i+=d,nBits-=8);m=e&(1<<-nBits)-1;e>>=-nBits;nBits+=mLen;for(;nBits>0;m=m*256+buffer[offset+i],i+=d,nBits-=8);if(e===0){e=1-eBias}else if(e===eMax){return m?NaN:(s?-1:1)*Infinity}else{m=m+Math.pow(2,mLen);e=e-eBias}return(s?-1:1)*m*Math.pow(2,e-mLen)};exports.write=function(buffer,value,offset,isLE,mLen,nBytes){var e,m,c,eLen=nBytes*8-mLen-1,eMax=(1<<eLen)-1,eBias=eMax>>1,rt=mLen===23?Math.pow(2,-24)-Math.pow(2,-77):0,i=isLE?0:nBytes-1,d=isLE?1:-1,s=value<0||value===0&&1/value<0?1:0;value=Math.abs(value);if(isNaN(value)||value===Infinity){m=isNaN(value)?1:0;e=eMax}else{e=Math.floor(Math.log(value)/Math.LN2);if(value*(c=Math.pow(2,-e))<1){e--;c*=2}if(e+eBias>=1){value+=rt/c}else{value+=rt*Math.pow(2,1-eBias)}if(value*c>=2){e++;c/=2}if(e+eBias>=eMax){m=0;e=eMax}else if(e+eBias>=1){m=(value*c-1)*Math.pow(2,mLen); | |
| e=e+eBias}else{m=value*Math.pow(2,eBias-1)*Math.pow(2,mLen);e=0}}for(;mLen>=8;buffer[offset+i]=m&255,i+=d,m/=256,mLen-=8);e=e<<mLen|m;eLen+=mLen;for(;eLen>0;buffer[offset+i]=e&255,i+=d,e/=256,eLen-=8);buffer[offset+i-d]|=s*128}},{}],4:[function(require,module,exports){var isArray=Array.isArray;var str=Object.prototype.toString;module.exports=isArray||function(val){return!!val&&"[object Array]"==str.call(val)}},{}],5:[function(require,module,exports){"use strict";function iota(n){var result=new Array(n);for(var i=0;i<n;++i){result[i]=i}return result}module.exports=iota},{}],ndarray:[function(require,module,exports){(function(Buffer){var iota=require("iota-array");var hasTypedArrays=typeof Float64Array!=="undefined";var hasBuffer=typeof Buffer!=="undefined";function compare1st(a,b){return a[0]-b[0]}function order(){var stride=this.stride;var terms=new Array(stride.length);var i;for(i=0;i<terms.length;++i){terms[i]=[Math.abs(stride[i]),i]}terms.sort(compare1st);var result=new Array(terms.length);for(i=0;i<result.length;++i){result[i]=terms[i][1]}return result}function compileConstructor(dtype,dimension){var className=["View",dimension,"d",dtype].join("");if(dimension<0){className="View_Nil"+dtype}var useGetters=dtype==="generic";if(dimension===-1){var code="function "+className+"(a){this.data=a;};var proto="+className+".prototype;proto.dtype='"+dtype+"';proto.index=function(){return -1};proto.size=0;proto.dimension=-1;proto.shape=proto.stride=proto.order=[];proto.lo=proto.hi=proto.transpose=proto.step=function(){return new "+className+"(this.data);};proto.get=proto.set=function(){};proto.pick=function(){return null};return function construct_"+className+"(a){return new "+className+"(a);}";var procedure=new Function(code);return procedure()}else if(dimension===0){var code="function "+className+"(a,d) {this.data = a;this.offset = d};var proto="+className+".prototype;proto.dtype='"+dtype+"';proto.index=function(){return this.offset};proto.dimension=0;proto.size=1;proto.shape=proto.stride=proto.order=[];proto.lo=proto.hi=proto.transpose=proto.step=function "+className+"_copy() {return new "+className+"(this.data,this.offset)};proto.pick=function "+className+"_pick(){return TrivialArray(this.data);};proto.valueOf=proto.get=function "+className+"_get(){return "+(useGetters?"this.data.get(this.offset)":"this.data[this.offset]")+"};proto.set=function "+className+"_set(v){return "+(useGetters?"this.data.set(this.offset,v)":"this.data[this.offset]=v")+"};return function construct_"+className+"(a,b,c,d){return new "+className+"(a,d)}";var procedure=new Function("TrivialArray",code);return procedure(CACHED_CONSTRUCTORS[dtype][0])}var code=["'use strict'"];var indices=iota(dimension);var args=indices.map(function(i){return"i"+i});var index_str="this.offset+"+indices.map(function(i){return"this.stride["+i+"]*i"+i}).join("+");var shapeArg=indices.map(function(i){return"b"+i}).join(",");var strideArg=indices.map(function(i){return"c"+i}).join(",");code.push("function "+className+"(a,"+shapeArg+","+strideArg+",d){this.data=a","this.shape=["+shapeArg+"]","this.stride=["+strideArg+"]","this.offset=d|0}","var proto="+className+".prototype","proto.dtype='"+dtype+"'","proto.dimension="+dimension);code.push("Object.defineProperty(proto,'size',{get:function "+className+"_size(){return "+indices.map(function(i){return"this.shape["+i+"]"}).join("*"),"}})");if(dimension===1){code.push("proto.order=[0]")}else{code.push("Object.defineProperty(proto,'order',{get:");if(dimension<4){code.push("function "+className+"_order(){");if(dimension===2){code.push("return (Math.abs(this.stride[0])>Math.abs(this.stride[1]))?[1,0]:[0,1]}})")}else if(dimension===3){code.push("var s0=Math.abs(this.stride[0]),s1=Math.abs(this.stride[1]),s2=Math.abs(this.stride[2]);if(s0>s1){if(s1>s2){return [2,1,0];}else if(s0>s2){return [1,2,0];}else{return [1,0,2];}}else if(s0>s2){return [2,0,1];}else if(s2>s1){return [0,1,2];}else{return [0,2,1];}}})")}}else{code.push("ORDER})")}}code.push("proto.set=function "+className+"_set("+args.join(",")+",v){");if(useGetters){code.push("return this.data.set("+index_str+",v)}")}else{code.push("return this.data["+index_str+"]=v}")}code.push("proto.get=function "+className+"_get("+args.join(",")+"){");if(useGetters){code.push("return this.data.get("+index_str+")}")}else{code.push("return this.data["+index_str+"]}")}code.push("proto.index=function "+className+"_index(",args.join(),"){return "+index_str+"}");code.push("proto.hi=function "+className+"_hi("+args.join(",")+"){return new "+className+"(this.data,"+indices.map(function(i){return["(typeof i",i,"!=='number'||i",i,"<0)?this.shape[",i,"]:i",i,"|0"].join("")}).join(",")+","+indices.map(function(i){return"this.stride["+i+"]"}).join(",")+",this.offset)}");var a_vars=indices.map(function(i){return"a"+i+"=this.shape["+i+"]"});var c_vars=indices.map(function(i){return"c"+i+"=this.stride["+i+"]"});code.push("proto.lo=function "+className+"_lo("+args.join(",")+"){var b=this.offset,d=0,"+a_vars.join(",")+","+c_vars.join(","));for(var i=0;i<dimension;++i){code.push("if(typeof i"+i+"==='number'&&i"+i+">=0){d=i"+i+"|0;b+=c"+i+"*d;a"+i+"-=d}")}code.push("return new "+className+"(this.data,"+indices.map(function(i){return"a"+i}).join(",")+","+indices.map(function(i){return"c"+i}).join(",")+",b)}");code.push("proto.step=function "+className+"_step("+args.join(",")+"){var "+indices.map(function(i){return"a"+i+"=this.shape["+i+"]"}).join(",")+","+indices.map(function(i){return"b"+i+"=this.stride["+i+"]"}).join(",")+",c=this.offset,d=0,ceil=Math.ceil");for(var i=0;i<dimension;++i){code.push("if(typeof i"+i+"==='number'){d=i"+i+"|0;if(d<0){c+=b"+i+"*(a"+i+"-1);a"+i+"=ceil(-a"+i+"/d)}else{a"+i+"=ceil(a"+i+"/d)}b"+i+"*=d}")}code.push("return new "+className+"(this.data,"+indices.map(function(i){return"a"+i}).join(",")+","+indices.map(function(i){return"b"+i}).join(",")+",c)}");var tShape=new Array(dimension);var tStride=new Array(dimension);for(var i=0;i<dimension;++i){tShape[i]="a[i"+i+"]";tStride[i]="b[i"+i+"]"}code.push("proto.transpose=function "+className+"_transpose("+args+"){"+args.map(function(n,idx){return n+"=("+n+"===undefined?"+idx+":"+n+"|0)"}).join(";"),"var a=this.shape,b=this.stride;return new "+className+"(this.data,"+tShape.join(",")+","+tStride.join(",")+",this.offset)}");code.push("proto.pick=function "+className+"_pick("+args+"){var a=[],b=[],c=this.offset");for(var i=0;i<dimension;++i){code.push("if(typeof i"+i+"==='number'&&i"+i+">=0){c=(c+this.stride["+i+"]*i"+i+")|0}else{a.push(this.shape["+i+"]);b.push(this.stride["+i+"])}")}code.push("var ctor=CTOR_LIST[a.length+1];return ctor(this.data,a,b,c)}");code.push("return function construct_"+className+"(data,shape,stride,offset){return new "+className+"(data,"+indices.map(function(i){return"shape["+i+"]"}).join(",")+","+indices.map(function(i){return"stride["+i+"]"}).join(",")+",offset)}");var procedure=new Function("CTOR_LIST","ORDER",code.join("\n"));return procedure(CACHED_CONSTRUCTORS[dtype],order)}function arrayDType(data){if(hasBuffer){if(Buffer.isBuffer(data)){return"buffer"}}if(hasTypedArrays){switch(Object.prototype.toString.call(data)){case"[object Float64Array]":return"float64";case"[object Float32Array]":return"float32";case"[object Int8Array]":return"int8";case"[object Int16Array]":return"int16";case"[object Int32Array]":return"int32";case"[object Uint8Array]":return"uint8";case"[object Uint16Array]":return"uint16";case"[object Uint32Array]":return"uint32";case"[object Uint8ClampedArray]":return"uint8_clamped"}}if(Array.isArray(data)){return"array"}return"generic"}var CACHED_CONSTRUCTORS={float32:[],float64:[],int8:[],int16:[],int32:[],uint8:[],uint16:[],uint32:[],array:[],uint8_clamped:[],buffer:[],generic:[]};(function(){for(var id in CACHED_CONSTRUCTORS){CACHED_CONSTRUCTORS[id].push(compileConstructor(id,-1))}});function wrappedNDArrayCtor(data,shape,stride,offset){if(data===undefined){var ctor=CACHED_CONSTRUCTORS.array[0];return ctor([])}else if(typeof data==="number"){data=[data]}if(shape===undefined){shape=[data.length]}var d=shape.length;if(stride===undefined){stride=new Array(d);for(var i=d-1,sz=1;i>=0;--i){stride[i]=sz;sz*=shape[i]}}if(offset===undefined){offset=0;for(var i=0;i<d;++i){if(stride[i]<0){offset-=(shape[i]-1)*stride[i]}}}var dtype=arrayDType(data);var ctor_list=CACHED_CONSTRUCTORS[dtype];while(ctor_list.length<=d+1){ctor_list.push(compileConstructor(dtype,ctor_list.length-1))}var ctor=ctor_list[d+1];return ctor(data,shape,stride,offset)}module.exports=wrappedNDArrayCtor}).call(this,require("buffer").Buffer)},{buffer:1,"iota-array":5}]},{},[]);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}({"contour-2d":[function(require,module,exports){"use strict";module.exports=getContours;function Segment(start,end,direction,height){this.start=start;this.end=end;this.direction=direction;this.height=height;this.visited=false;this.next=null;this.prev=null}function Vertex(x,y,segment,orientation){this.x=x;this.y=y;this.segment=segment;this.orientation=orientation}function getParallelCountours(array,direction){var n=array.shape[0];var m=array.shape[1];var contours=[];var a=false;var b=false;var c=false;var d=false;var x0=0;var i=0,j=0;for(j=0;j<m;++j){b=!!array.get(0,j);if(b===a){continue}if(a){contours.push(new Segment(x0,j,direction,0))}if(b){x0=j}a=b}if(a){contours.push(new Segment(x0,j,direction,0))}for(i=1;i<n;++i){a=false;b=false;x0=0;for(j=0;j<m;++j){c=!!array.get(i-1,j);d=!!array.get(i,j);if(c===a&&d===b){continue}if(a!==b){if(a){contours.push(new Segment(j,x0,direction,i))}else{contours.push(new Segment(x0,j,direction,i))}}if(c!==d){x0=j}a=c;b=d}if(a!==b){if(a){contours.push(new Segment(j,x0,direction,i))}else{contours.push(new Segment(x0,j,direction,i))}}}a=false;x0=0;for(j=0;j<m;++j){b=!!array.get(n-1,j);if(b===a){continue}if(a){contours.push(new Segment(j,x0,direction,n))}if(b){x0=j}a=b}if(a){contours.push(new Segment(j,x0,direction,n))}return contours}function getVertices(contours){var vertices=new Array(contours.length*2);for(var i=0;i<contours.length;++i){var h=contours[i];if(h.direction===0){vertices[2*i]=new Vertex(h.start,h.height,h,0);vertices[2*i+1]=new Vertex(h.end,h.height,h,1)}else{vertices[2*i]=new Vertex(h.height,h.start,h,0);vertices[2*i+1]=new Vertex(h.height,h.end,h,1)}}return vertices}function walk(v,clockwise){var result=[];while(!v.visited){v.visited=true;if(v.direction){result.push([v.height,v.end])}else{result.push([v.start,v.height])}if(clockwise){v=v.next}else{v=v.prev}}return result}function compareVertex(a,b){var d=a.x-b.x;if(d){return d}d=a.y-b.y;if(d){return d}return a.orientation-b.orientation}function getContours(array,clockwise){var clockwise=!!clockwise;var hcontours=getParallelCountours(array,0);var hvertices=getVertices(hcontours);hvertices.sort(compareVertex);var vcontours=getParallelCountours(array.transpose(1,0),1);var vvertices=getVertices(vcontours);vvertices.sort(compareVertex);var nv=hvertices.length;for(var i=0;i<nv;++i){var h=hvertices[i];var v=vvertices[i];if(h.orientation){h.segment.next=v.segment;v.segment.prev=h.segment}else{h.segment.prev=v.segment;v.segment.next=h.segment}}var loops=[];for(var i=0;i<hcontours.length;++i){var h=hcontours[i];if(!h.visited){loops.push(walk(h,clockwise))}}return loops}},{}]},{},[]);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]}},{}],"robust-orientation":[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}]},{},[]);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}({uniq:[function(require,module,exports){"use strict";function unique_pred(list,compare){var ptr=1,len=list.length,a=list[0],b=list[0];for(var i=1;i<len;++i){b=a;a=list[i];if(compare(a,b)){if(i===ptr){ptr++;continue}list[ptr++]=a}}list.length=ptr;return list}function unique_eq(list){var ptr=1,len=list.length,a=list[0],b=list[0];for(var i=1;i<len;++i,b=a){b=a;a=list[i];if(a!==b){if(i===ptr){ptr++;continue}list[ptr++]=a}}list.length=ptr;return list}function unique(list,compare,sorted){if(list.length===0){return list}if(compare){if(!sorted){list.sort(compare)}return unique_pred(list,compare)}if(!sorted){list.sort()}return unique_eq(list)}module.exports=unique},{}]},{},[]);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 base64=require("base64-js");var ieee754=require("ieee754");var isArray=require("is-array");exports.Buffer=Buffer;exports.SlowBuffer=SlowBuffer;exports.INSPECT_MAX_BYTES=50;Buffer.poolSize=8192;var kMaxLength=1073741823;var rootParent={};Buffer.TYPED_ARRAY_SUPPORT=function(){try{var buf=new ArrayBuffer(0);var arr=new Uint8Array(buf);arr.foo=function(){return 42};return 42===arr.foo()&&typeof arr.subarray==="function"&&new Uint8Array(1).subarray(1,1).byteLength===0}catch(e){return false}}();function Buffer(subject,encoding,noZero){if(!(this instanceof Buffer))return new Buffer(subject,encoding,noZero);var type=typeof subject;var length;if(type==="number")length=subject>0?subject>>>0:0;else if(type==="string"){length=Buffer.byteLength(subject,encoding)}else if(type==="object"&&subject!==null){if(subject.type==="Buffer"&&isArray(subject.data))subject=subject.data;length=+subject.length>0?Math.floor(+subject.length):0}else throw new TypeError("must start with number, buffer, array or string");if(length>kMaxLength)throw new RangeError("Attempt to allocate Buffer larger than maximum "+"size: 0x"+kMaxLength.toString(16)+" bytes");var buf;if(Buffer.TYPED_ARRAY_SUPPORT){buf=Buffer._augment(new Uint8Array(length))}else{buf=this;buf.length=length;buf._isBuffer=true}var i;if(Buffer.TYPED_ARRAY_SUPPORT&&typeof subject.byteLength==="number"){buf._set(subject)}else if(isArrayish(subject)){if(Buffer.isBuffer(subject)){for(i=0;i<length;i++)buf[i]=subject.readUInt8(i)}else{for(i=0;i<length;i++)buf[i]=(subject[i]%256+256)%256}}else if(type==="string"){buf.write(subject,0,encoding)}else if(type==="number"&&!Buffer.TYPED_ARRAY_SUPPORT&&!noZero){for(i=0;i<length;i++){buf[i]=0}}if(length>0&&length<=Buffer.poolSize)buf.parent=rootParent;return buf}function SlowBuffer(subject,encoding,noZero){if(!(this instanceof SlowBuffer))return new SlowBuffer(subject,encoding,noZero);var buf=new Buffer(subject,encoding,noZero);delete buf.parent;return buf}Buffer.isBuffer=function(b){return!!(b!=null&&b._isBuffer)};Buffer.compare=function(a,b){if(!Buffer.isBuffer(a)||!Buffer.isBuffer(b))throw new TypeError("Arguments must be Buffers");var x=a.length;var y=b.length;for(var i=0,len=Math.min(x,y);i<len&&a[i]===b[i];i++){}if(i!==len){x=a[i];y=b[i]}if(x<y)return-1;if(y<x)return 1;return 0};Buffer.isEncoding=function(encoding){switch(String(encoding).toLowerCase()){case"hex":case"utf8":case"utf-8":case"ascii":case"binary":case"base64":case"raw":case"ucs2":case"ucs-2":case"utf16le":case"utf-16le":return true;default:return false}};Buffer.concat=function(list,totalLength){if(!isArray(list))throw new TypeError("Usage: Buffer.concat(list[, length])");if(list.length===0){return new Buffer(0)}else if(list.length===1){return list[0]}var i;if(totalLength===undefined){totalLength=0;for(i=0;i<list.length;i++){totalLength+=list[i].length}}var buf=new Buffer(totalLength);var pos=0;for(i=0;i<list.length;i++){var item=list[i];item.copy(buf,pos);pos+=item.length}return buf};Buffer.byteLength=function(str,encoding){var ret;str=str+"";switch(encoding||"utf8"){case"ascii":case"binary":case"raw":ret=str.length;break;case"ucs2":case"ucs-2":case"utf16le":case"utf-16le":ret=str.length*2;break;case"hex":ret=str.length>>>1;break;case"utf8":case"utf-8":ret=utf8ToBytes(str).length;break;case"base64":ret=base64ToBytes(str).length;break;default:ret=str.length}return ret};Buffer.prototype.length=undefined;Buffer.prototype.parent=undefined;Buffer.prototype.toString=function(encoding,start,end){var loweredCase=false;start=start>>>0;end=end===undefined||end===Infinity?this.length:end>>>0;if(!encoding)encoding="utf8";if(start<0)start=0;if(end>this.length)end=this.length;if(end<=start)return"";while(true){switch(encoding){case"hex":return hexSlice(this,start,end);case"utf8":case"utf-8":return utf8Slice(this,start,end);case"ascii":return asciiSlice(this,start,end);case"binary":return binarySlice(this,start,end);case"base64":return base64Slice(this,start,end);case"ucs2":case"ucs-2":case"utf16le":case"utf-16le":return utf16leSlice(this,start,end);default:if(loweredCase)throw new TypeError("Unknown encoding: "+encoding);encoding=(encoding+"").toLowerCase();loweredCase=true}}};Buffer.prototype.equals=function(b){if(!Buffer.isBuffer(b))throw new TypeError("Argument must be a Buffer");return Buffer.compare(this,b)===0};Buffer.prototype.inspect=function(){var str="";var max=exports.INSPECT_MAX_BYTES;if(this.length>0){str=this.toString("hex",0,max).match(/.{2}/g).join(" ");if(this.length>max)str+=" ... "}return"<Buffer "+str+">"};Buffer.prototype.compare=function(b){if(!Buffer.isBuffer(b))throw new TypeError("Argument must be a Buffer");return Buffer.compare(this,b)};Buffer.prototype.get=function(offset){console.log(".get() is deprecated. Access using array indexes instead.");return this.readUInt8(offset)};Buffer.prototype.set=function(v,offset){console.log(".set() is deprecated. Access using array indexes instead.");return this.writeUInt8(v,offset)};function hexWrite(buf,string,offset,length){offset=Number(offset)||0;var remaining=buf.length-offset;if(!length){length=remaining}else{length=Number(length);if(length>remaining){length=remaining}}var strLen=string.length;if(strLen%2!==0)throw new Error("Invalid hex string");if(length>strLen/2){length=strLen/2}for(var i=0;i<length;i++){var byte=parseInt(string.substr(i*2,2),16);if(isNaN(byte))throw new Error("Invalid hex string");buf[offset+i]=byte}return i}function utf8Write(buf,string,offset,length){var charsWritten=blitBuffer(utf8ToBytes(string,buf.length-offset),buf,offset,length);return charsWritten}function asciiWrite(buf,string,offset,length){var charsWritten=blitBuffer(asciiToBytes(string),buf,offset,length);return charsWritten}function binaryWrite(buf,string,offset,length){return asciiWrite(buf,string,offset,length)}function base64Write(buf,string,offset,length){var charsWritten=blitBuffer(base64ToBytes(string),buf,offset,length);return charsWritten}function utf16leWrite(buf,string,offset,length){var charsWritten=blitBuffer(utf16leToBytes(string,buf.length-offset),buf,offset,length,2);return charsWritten}Buffer.prototype.write=function(string,offset,length,encoding){if(isFinite(offset)){if(!isFinite(length)){encoding=length;length=undefined}}else{var swap=encoding;encoding=offset;offset=length;length=swap}offset=Number(offset)||0;if(length<0||offset<0||offset>this.length)throw new RangeError("attempt to write outside buffer bounds");var remaining=this.length-offset;if(!length){length=remaining}else{length=Number(length);if(length>remaining){length=remaining}}encoding=String(encoding||"utf8").toLowerCase();var ret;switch(encoding){case"hex":ret=hexWrite(this,string,offset,length);break;case"utf8":case"utf-8":ret=utf8Write(this,string,offset,length);break;case"ascii":ret=asciiWrite(this,string,offset,length);break;case"binary":ret=binaryWrite(this,string,offset,length);break;case"base64":ret=base64Write(this,string,offset,length);break;case"ucs2":case"ucs-2":case"utf16le":case"utf-16le":ret=utf16leWrite(this,string,offset,length);break;default:throw new TypeError("Unknown encoding: "+encoding)}return ret};Buffer.prototype.toJSON=function(){return{type:"Buffer",data:Array.prototype.slice.call(this._arr||this,0)}};function base64Slice(buf,start,end){if(start===0&&end===buf.length){return base64.fromByteArray(buf)}else{return base64.fromByteArray(buf.slice(start,end))}}function utf8Slice(buf,start,end){var res="";var tmp="";end=Math.min(buf.length,end);for(var i=start;i<end;i++){if(buf[i]<=127){res+=decodeUtf8Char(tmp)+String.fromCharCode(buf[i]);tmp=""}else{tmp+="%"+buf[i].toString(16)}}return res+decodeUtf8Char(tmp)}function asciiSlice(buf,start,end){var ret="";end=Math.min(buf.length,end);for(var i=start;i<end;i++){ret+=String.fromCharCode(buf[i]&127)}return ret}function binarySlice(buf,start,end){var ret="";end=Math.min(buf.length,end);for(var i=start;i<end;i++){ret+=String.fromCharCode(buf[i])}return ret}function hexSlice(buf,start,end){var len=buf.length;if(!start||start<0)start=0;if(!end||end<0||end>len)end=len;var out="";for(var i=start;i<end;i++){out+=toHex(buf[i])}return out}function utf16leSlice(buf,start,end){var bytes=buf.slice(start,end);var res="";for(var i=0;i<bytes.length;i+=2){res+=String.fromCharCode(bytes[i]+bytes[i+1]*256)}return res}Buffer.prototype.slice=function(start,end){var len=this.length;start=~~start;end=end===undefined?len:~~end;if(start<0){start+=len;if(start<0)start=0}else if(start>len){start=len}if(end<0){end+=len;if(end<0)end=0}else if(end>len){end=len}if(end<start)end=start;var newBuf;if(Buffer.TYPED_ARRAY_SUPPORT){newBuf=Buffer._augment(this.subarray(start,end))}else{var sliceLen=end-start;newBuf=new Buffer(sliceLen,undefined,true);for(var i=0;i<sliceLen;i++){newBuf[i]=this[i+start]}}if(newBuf.length)newBuf.parent=this.parent||this;return newBuf};function checkOffset(offset,ext,length){if(offset%1!==0||offset<0)throw new RangeError("offset is not uint");if(offset+ext>length)throw new RangeError("Trying to access beyond buffer length")}Buffer.prototype.readUIntLE=function(offset,byteLength,noAssert){offset=offset>>>0;byteLength=byteLength>>>0;if(!noAssert)checkOffset(offset,byteLength,this.length);var val=this[offset];var mul=1;var i=0;while(++i<byteLength&&(mul*=256))val+=this[offset+i]*mul;return val};Buffer.prototype.readUIntBE=function(offset,byteLength,noAssert){offset=offset>>>0;byteLength=byteLength>>>0;if(!noAssert)checkOffset(offset,byteLength,this.length);var val=this[offset+--byteLength];var mul=1;while(byteLength>0&&(mul*=256))val+=this[offset+--byteLength]*mul;return val};Buffer.prototype.readUInt8=function(offset,noAssert){if(!noAssert)checkOffset(offset,1,this.length);return this[offset]};Buffer.prototype.readUInt16LE=function(offset,noAssert){if(!noAssert)checkOffset(offset,2,this.length);return this[offset]|this[offset+1]<<8};Buffer.prototype.readUInt16BE=function(offset,noAssert){if(!noAssert)checkOffset(offset,2,this.length);return this[offset]<<8|this[offset+1]};Buffer.prototype.readUInt32LE=function(offset,noAssert){ | |
| if(!noAssert)checkOffset(offset,4,this.length);return(this[offset]|this[offset+1]<<8|this[offset+2]<<16)+this[offset+3]*16777216};Buffer.prototype.readUInt32BE=function(offset,noAssert){if(!noAssert)checkOffset(offset,4,this.length);return this[offset]*16777216+(this[offset+1]<<16|this[offset+2]<<8|this[offset+3])};Buffer.prototype.readIntLE=function(offset,byteLength,noAssert){offset=offset>>>0;byteLength=byteLength>>>0;if(!noAssert)checkOffset(offset,byteLength,this.length);var val=this[offset];var mul=1;var i=0;while(++i<byteLength&&(mul*=256))val+=this[offset+i]*mul;mul*=128;if(val>=mul)val-=Math.pow(2,8*byteLength);return val};Buffer.prototype.readIntBE=function(offset,byteLength,noAssert){offset=offset>>>0;byteLength=byteLength>>>0;if(!noAssert)checkOffset(offset,byteLength,this.length);var i=byteLength;var mul=1;var val=this[offset+--i];while(i>0&&(mul*=256))val+=this[offset+--i]*mul;mul*=128;if(val>=mul)val-=Math.pow(2,8*byteLength);return val};Buffer.prototype.readInt8=function(offset,noAssert){if(!noAssert)checkOffset(offset,1,this.length);if(!(this[offset]&128))return this[offset];return(255-this[offset]+1)*-1};Buffer.prototype.readInt16LE=function(offset,noAssert){if(!noAssert)checkOffset(offset,2,this.length);var val=this[offset]|this[offset+1]<<8;return val&32768?val|4294901760:val};Buffer.prototype.readInt16BE=function(offset,noAssert){if(!noAssert)checkOffset(offset,2,this.length);var val=this[offset+1]|this[offset]<<8;return val&32768?val|4294901760:val};Buffer.prototype.readInt32LE=function(offset,noAssert){if(!noAssert)checkOffset(offset,4,this.length);return this[offset]|this[offset+1]<<8|this[offset+2]<<16|this[offset+3]<<24};Buffer.prototype.readInt32BE=function(offset,noAssert){if(!noAssert)checkOffset(offset,4,this.length);return this[offset]<<24|this[offset+1]<<16|this[offset+2]<<8|this[offset+3]};Buffer.prototype.readFloatLE=function(offset,noAssert){if(!noAssert)checkOffset(offset,4,this.length);return ieee754.read(this,offset,true,23,4)};Buffer.prototype.readFloatBE=function(offset,noAssert){if(!noAssert)checkOffset(offset,4,this.length);return ieee754.read(this,offset,false,23,4)};Buffer.prototype.readDoubleLE=function(offset,noAssert){if(!noAssert)checkOffset(offset,8,this.length);return ieee754.read(this,offset,true,52,8)};Buffer.prototype.readDoubleBE=function(offset,noAssert){if(!noAssert)checkOffset(offset,8,this.length);return ieee754.read(this,offset,false,52,8)};function checkInt(buf,value,offset,ext,max,min){if(!Buffer.isBuffer(buf))throw new TypeError("buffer must be a Buffer instance");if(value>max||value<min)throw new RangeError("value is out of bounds");if(offset+ext>buf.length)throw new RangeError("index out of range")}Buffer.prototype.writeUIntLE=function(value,offset,byteLength,noAssert){value=+value;offset=offset>>>0;byteLength=byteLength>>>0;if(!noAssert)checkInt(this,value,offset,byteLength,Math.pow(2,8*byteLength),0);var mul=1;var i=0;this[offset]=value&255;while(++i<byteLength&&(mul*=256))this[offset+i]=value/mul>>>0&255;return offset+byteLength};Buffer.prototype.writeUIntBE=function(value,offset,byteLength,noAssert){value=+value;offset=offset>>>0;byteLength=byteLength>>>0;if(!noAssert)checkInt(this,value,offset,byteLength,Math.pow(2,8*byteLength),0);var i=byteLength-1;var mul=1;this[offset+i]=value&255;while(--i>=0&&(mul*=256))this[offset+i]=value/mul>>>0&255;return offset+byteLength};Buffer.prototype.writeUInt8=function(value,offset,noAssert){value=+value;offset=offset>>>0;if(!noAssert)checkInt(this,value,offset,1,255,0);if(!Buffer.TYPED_ARRAY_SUPPORT)value=Math.floor(value);this[offset]=value;return offset+1};function objectWriteUInt16(buf,value,offset,littleEndian){if(value<0)value=65535+value+1;for(var i=0,j=Math.min(buf.length-offset,2);i<j;i++){buf[offset+i]=(value&255<<8*(littleEndian?i:1-i))>>>(littleEndian?i:1-i)*8}}Buffer.prototype.writeUInt16LE=function(value,offset,noAssert){value=+value;offset=offset>>>0;if(!noAssert)checkInt(this,value,offset,2,65535,0);if(Buffer.TYPED_ARRAY_SUPPORT){this[offset]=value;this[offset+1]=value>>>8}else objectWriteUInt16(this,value,offset,true);return offset+2};Buffer.prototype.writeUInt16BE=function(value,offset,noAssert){value=+value;offset=offset>>>0;if(!noAssert)checkInt(this,value,offset,2,65535,0);if(Buffer.TYPED_ARRAY_SUPPORT){this[offset]=value>>>8;this[offset+1]=value}else objectWriteUInt16(this,value,offset,false);return offset+2};function objectWriteUInt32(buf,value,offset,littleEndian){if(value<0)value=4294967295+value+1;for(var i=0,j=Math.min(buf.length-offset,4);i<j;i++){buf[offset+i]=value>>>(littleEndian?i:3-i)*8&255}}Buffer.prototype.writeUInt32LE=function(value,offset,noAssert){value=+value;offset=offset>>>0;if(!noAssert)checkInt(this,value,offset,4,4294967295,0);if(Buffer.TYPED_ARRAY_SUPPORT){this[offset+3]=value>>>24;this[offset+2]=value>>>16;this[offset+1]=value>>>8;this[offset]=value}else objectWriteUInt32(this,value,offset,true);return offset+4};Buffer.prototype.writeUInt32BE=function(value,offset,noAssert){value=+value;offset=offset>>>0;if(!noAssert)checkInt(this,value,offset,4,4294967295,0);if(Buffer.TYPED_ARRAY_SUPPORT){this[offset]=value>>>24;this[offset+1]=value>>>16;this[offset+2]=value>>>8;this[offset+3]=value}else objectWriteUInt32(this,value,offset,false);return offset+4};Buffer.prototype.writeIntLE=function(value,offset,byteLength,noAssert){value=+value;offset=offset>>>0;if(!noAssert){checkInt(this,value,offset,byteLength,Math.pow(2,8*byteLength-1)-1,-Math.pow(2,8*byteLength-1))}var i=0;var mul=1;var sub=value<0?1:0;this[offset]=value&255;while(++i<byteLength&&(mul*=256))this[offset+i]=(value/mul>>0)-sub&255;return offset+byteLength};Buffer.prototype.writeIntBE=function(value,offset,byteLength,noAssert){value=+value;offset=offset>>>0;if(!noAssert){checkInt(this,value,offset,byteLength,Math.pow(2,8*byteLength-1)-1,-Math.pow(2,8*byteLength-1))}var i=byteLength-1;var mul=1;var sub=value<0?1:0;this[offset+i]=value&255;while(--i>=0&&(mul*=256))this[offset+i]=(value/mul>>0)-sub&255;return offset+byteLength};Buffer.prototype.writeInt8=function(value,offset,noAssert){value=+value;offset=offset>>>0;if(!noAssert)checkInt(this,value,offset,1,127,-128);if(!Buffer.TYPED_ARRAY_SUPPORT)value=Math.floor(value);if(value<0)value=255+value+1;this[offset]=value;return offset+1};Buffer.prototype.writeInt16LE=function(value,offset,noAssert){value=+value;offset=offset>>>0;if(!noAssert)checkInt(this,value,offset,2,32767,-32768);if(Buffer.TYPED_ARRAY_SUPPORT){this[offset]=value;this[offset+1]=value>>>8}else objectWriteUInt16(this,value,offset,true);return offset+2};Buffer.prototype.writeInt16BE=function(value,offset,noAssert){value=+value;offset=offset>>>0;if(!noAssert)checkInt(this,value,offset,2,32767,-32768);if(Buffer.TYPED_ARRAY_SUPPORT){this[offset]=value>>>8;this[offset+1]=value}else objectWriteUInt16(this,value,offset,false);return offset+2};Buffer.prototype.writeInt32LE=function(value,offset,noAssert){value=+value;offset=offset>>>0;if(!noAssert)checkInt(this,value,offset,4,2147483647,-2147483648);if(Buffer.TYPED_ARRAY_SUPPORT){this[offset]=value;this[offset+1]=value>>>8;this[offset+2]=value>>>16;this[offset+3]=value>>>24}else objectWriteUInt32(this,value,offset,true);return offset+4};Buffer.prototype.writeInt32BE=function(value,offset,noAssert){value=+value;offset=offset>>>0;if(!noAssert)checkInt(this,value,offset,4,2147483647,-2147483648);if(value<0)value=4294967295+value+1;if(Buffer.TYPED_ARRAY_SUPPORT){this[offset]=value>>>24;this[offset+1]=value>>>16;this[offset+2]=value>>>8;this[offset+3]=value}else objectWriteUInt32(this,value,offset,false);return offset+4};function checkIEEE754(buf,value,offset,ext,max,min){if(value>max||value<min)throw new RangeError("value is out of bounds");if(offset+ext>buf.length)throw new RangeError("index out of range");if(offset<0)throw new RangeError("index out of range")}function writeFloat(buf,value,offset,littleEndian,noAssert){if(!noAssert)checkIEEE754(buf,value,offset,4,3.4028234663852886e38,-3.4028234663852886e38);ieee754.write(buf,value,offset,littleEndian,23,4);return offset+4}Buffer.prototype.writeFloatLE=function(value,offset,noAssert){return writeFloat(this,value,offset,true,noAssert)};Buffer.prototype.writeFloatBE=function(value,offset,noAssert){return writeFloat(this,value,offset,false,noAssert)};function writeDouble(buf,value,offset,littleEndian,noAssert){if(!noAssert)checkIEEE754(buf,value,offset,8,1.7976931348623157e308,-1.7976931348623157e308);ieee754.write(buf,value,offset,littleEndian,52,8);return offset+8}Buffer.prototype.writeDoubleLE=function(value,offset,noAssert){return writeDouble(this,value,offset,true,noAssert)};Buffer.prototype.writeDoubleBE=function(value,offset,noAssert){return writeDouble(this,value,offset,false,noAssert)};Buffer.prototype.copy=function(target,target_start,start,end){var source=this;if(!start)start=0;if(!end&&end!==0)end=this.length;if(target_start>=target.length)target_start=target.length;if(!target_start)target_start=0;if(end>0&&end<start)end=start;if(end===start)return 0;if(target.length===0||source.length===0)return 0;if(target_start<0)throw new RangeError("targetStart out of bounds");if(start<0||start>=source.length)throw new RangeError("sourceStart out of bounds");if(end<0)throw new RangeError("sourceEnd out of bounds");if(end>this.length)end=this.length;if(target.length-target_start<end-start)end=target.length-target_start+start;var len=end-start;if(len<1e3||!Buffer.TYPED_ARRAY_SUPPORT){for(var i=0;i<len;i++){target[i+target_start]=this[i+start]}}else{target._set(this.subarray(start,start+len),target_start)}return len};Buffer.prototype.fill=function(value,start,end){if(!value)value=0;if(!start)start=0;if(!end)end=this.length;if(end<start)throw new RangeError("end < start");if(end===start)return;if(this.length===0)return;if(start<0||start>=this.length)throw new RangeError("start out of bounds");if(end<0||end>this.length)throw new RangeError("end out of bounds");var i;if(typeof value==="number"){for(i=start;i<end;i++){this[i]=value}}else{var bytes=utf8ToBytes(value.toString());var len=bytes.length;for(i=start;i<end;i++){this[i]=bytes[i%len]}}return this};Buffer.prototype.toArrayBuffer=function(){if(typeof Uint8Array!=="undefined"){if(Buffer.TYPED_ARRAY_SUPPORT){return new Buffer(this).buffer}else{var buf=new Uint8Array(this.length);for(var i=0,len=buf.length;i<len;i+=1){buf[i]=this[i]}return buf.buffer}}else{throw new TypeError("Buffer.toArrayBuffer not supported in this browser")}};var BP=Buffer.prototype;Buffer._augment=function(arr){arr.constructor=Buffer;arr._isBuffer=true;arr._get=arr.get;arr._set=arr.set;arr.get=BP.get;arr.set=BP.set;arr.write=BP.write;arr.toString=BP.toString;arr.toLocaleString=BP.toString;arr.toJSON=BP.toJSON;arr.equals=BP.equals;arr.compare=BP.compare;arr.copy=BP.copy;arr.slice=BP.slice;arr.readUIntLE=BP.readUIntLE;arr.readUIntBE=BP.readUIntBE;arr.readUInt8=BP.readUInt8;arr.readUInt16LE=BP.readUInt16LE;arr.readUInt16BE=BP.readUInt16BE;arr.readUInt32LE=BP.readUInt32LE;arr.readUInt32BE=BP.readUInt32BE;arr.readIntLE=BP.readIntLE;arr.readIntBE=BP.readIntBE;arr.readInt8=BP.readInt8;arr.readInt16LE=BP.readInt16LE;arr.readInt16BE=BP.readInt16BE;arr.readInt32LE=BP.readInt32LE;arr.readInt32BE=BP.readInt32BE;arr.readFloatLE=BP.readFloatLE;arr.readFloatBE=BP.readFloatBE;arr.readDoubleLE=BP.readDoubleLE;arr.readDoubleBE=BP.readDoubleBE;arr.writeUInt8=BP.writeUInt8;arr.writeUIntLE=BP.writeUIntLE;arr.writeUIntBE=BP.writeUIntBE;arr.writeUInt16LE=BP.writeUInt16LE;arr.writeUInt16BE=BP.writeUInt16BE;arr.writeUInt32LE=BP.writeUInt32LE;arr.writeUInt32BE=BP.writeUInt32BE;arr.writeIntLE=BP.writeIntLE;arr.writeIntBE=BP.writeIntBE;arr.writeInt8=BP.writeInt8;arr.writeInt16LE=BP.writeInt16LE;arr.writeInt16BE=BP.writeInt16BE;arr.writeInt32LE=BP.writeInt32LE;arr.writeInt32BE=BP.writeInt32BE;arr.writeFloatLE=BP.writeFloatLE;arr.writeFloatBE=BP.writeFloatBE;arr.writeDoubleLE=BP.writeDoubleLE;arr.writeDoubleBE=BP.writeDoubleBE;arr.fill=BP.fill;arr.inspect=BP.inspect;arr.toArrayBuffer=BP.toArrayBuffer;return arr};var INVALID_BASE64_RE=/[^+\/0-9A-z\-]/g;function base64clean(str){str=stringtrim(str).replace(INVALID_BASE64_RE,"");if(str.length<2)return"";while(str.length%4!==0){str=str+"="}return str}function stringtrim(str){if(str.trim)return str.trim();return str.replace(/^\s+|\s+$/g,"")}function isArrayish(subject){return isArray(subject)||Buffer.isBuffer(subject)||subject&&typeof subject==="object"&&typeof subject.length==="number"}function toHex(n){if(n<16)return"0"+n.toString(16);return n.toString(16)}function utf8ToBytes(string,units){var codePoint,length=string.length;var leadSurrogate=null;units=units||Infinity;var bytes=[];var i=0;for(;i<length;i++){codePoint=string.charCodeAt(i);if(codePoint>55295&&codePoint<57344){if(leadSurrogate){if(codePoint<56320){if((units-=3)>-1)bytes.push(239,191,189);leadSurrogate=codePoint;continue}else{codePoint=leadSurrogate-55296<<10|codePoint-56320|65536;leadSurrogate=null}}else{if(codePoint>56319){if((units-=3)>-1)bytes.push(239,191,189);continue}else if(i+1===length){if((units-=3)>-1)bytes.push(239,191,189);continue}else{leadSurrogate=codePoint;continue}}}else if(leadSurrogate){if((units-=3)>-1)bytes.push(239,191,189);leadSurrogate=null}if(codePoint<128){if((units-=1)<0)break;bytes.push(codePoint)}else if(codePoint<2048){if((units-=2)<0)break;bytes.push(codePoint>>6|192,codePoint&63|128)}else if(codePoint<65536){if((units-=3)<0)break;bytes.push(codePoint>>12|224,codePoint>>6&63|128,codePoint&63|128)}else if(codePoint<2097152){if((units-=4)<0)break;bytes.push(codePoint>>18|240,codePoint>>12&63|128,codePoint>>6&63|128,codePoint&63|128)}else{throw new Error("Invalid code point")}}return bytes}function asciiToBytes(str){var byteArray=[];for(var i=0;i<str.length;i++){byteArray.push(str.charCodeAt(i)&255)}return byteArray}function utf16leToBytes(str,units){var c,hi,lo;var byteArray=[];for(var i=0;i<str.length;i++){if((units-=2)<0)break;c=str.charCodeAt(i);hi=c>>8;lo=c%256;byteArray.push(lo);byteArray.push(hi)}return byteArray}function base64ToBytes(str){return base64.toByteArray(base64clean(str))}function blitBuffer(src,dst,offset,length,unitSize){if(unitSize)length-=length%unitSize;for(var i=0;i<length;i++){if(i+offset>=dst.length||i>=src.length)break;dst[i+offset]=src[i]}return i}function decodeUtf8Char(str){try{return decodeURIComponent(str)}catch(err){return String.fromCharCode(65533)}}},{"base64-js":2,ieee754:3,"is-array":4}],2:[function(require,module,exports){var lookup="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";(function(exports){"use strict";var Arr=typeof Uint8Array!=="undefined"?Uint8Array:Array;var PLUS="+".charCodeAt(0);var SLASH="/".charCodeAt(0);var NUMBER="0".charCodeAt(0);var LOWER="a".charCodeAt(0);var UPPER="A".charCodeAt(0);var PLUS_URL_SAFE="-".charCodeAt(0);var SLASH_URL_SAFE="_".charCodeAt(0);function decode(elt){var code=elt.charCodeAt(0);if(code===PLUS||code===PLUS_URL_SAFE)return 62;if(code===SLASH||code===SLASH_URL_SAFE)return 63;if(code<NUMBER)return-1;if(code<NUMBER+10)return code-NUMBER+26+26;if(code<UPPER+26)return code-UPPER;if(code<LOWER+26)return code-LOWER+26}function b64ToByteArray(b64){var i,j,l,tmp,placeHolders,arr;if(b64.length%4>0){throw new Error("Invalid string. Length must be a multiple of 4")}var len=b64.length;placeHolders="="===b64.charAt(len-2)?2:"="===b64.charAt(len-1)?1:0;arr=new Arr(b64.length*3/4-placeHolders);l=placeHolders>0?b64.length-4:b64.length;var L=0;function push(v){arr[L++]=v}for(i=0,j=0;i<l;i+=4,j+=3){tmp=decode(b64.charAt(i))<<18|decode(b64.charAt(i+1))<<12|decode(b64.charAt(i+2))<<6|decode(b64.charAt(i+3));push((tmp&16711680)>>16);push((tmp&65280)>>8);push(tmp&255)}if(placeHolders===2){tmp=decode(b64.charAt(i))<<2|decode(b64.charAt(i+1))>>4;push(tmp&255)}else if(placeHolders===1){tmp=decode(b64.charAt(i))<<10|decode(b64.charAt(i+1))<<4|decode(b64.charAt(i+2))>>2;push(tmp>>8&255);push(tmp&255)}return arr}function uint8ToBase64(uint8){var i,extraBytes=uint8.length%3,output="",temp,length;function encode(num){return lookup.charAt(num)}function tripletToBase64(num){return encode(num>>18&63)+encode(num>>12&63)+encode(num>>6&63)+encode(num&63)}for(i=0,length=uint8.length-extraBytes;i<length;i+=3){temp=(uint8[i]<<16)+(uint8[i+1]<<8)+uint8[i+2];output+=tripletToBase64(temp)}switch(extraBytes){case 1:temp=uint8[uint8.length-1];output+=encode(temp>>2);output+=encode(temp<<4&63);output+="==";break;case 2:temp=(uint8[uint8.length-2]<<8)+uint8[uint8.length-1];output+=encode(temp>>10);output+=encode(temp>>4&63);output+=encode(temp<<2&63);output+="=";break}return output}exports.toByteArray=b64ToByteArray;exports.fromByteArray=uint8ToBase64})(typeof exports==="undefined"?this.base64js={}:exports)},{}],3:[function(require,module,exports){exports.read=function(buffer,offset,isLE,mLen,nBytes){var e,m,eLen=nBytes*8-mLen-1,eMax=(1<<eLen)-1,eBias=eMax>>1,nBits=-7,i=isLE?nBytes-1:0,d=isLE?-1:1,s=buffer[offset+i];i+=d;e=s&(1<<-nBits)-1;s>>=-nBits;nBits+=eLen;for(;nBits>0;e=e*256+buffer[offset+i],i+=d,nBits-=8);m=e&(1<<-nBits)-1;e>>=-nBits;nBits+=mLen;for(;nBits>0;m=m*256+buffer[offset+i],i+=d,nBits-=8);if(e===0){e=1-eBias}else if(e===eMax){return m?NaN:(s?-1:1)*Infinity}else{m=m+Math.pow(2,mLen);e=e-eBias}return(s?-1:1)*m*Math.pow(2,e-mLen)};exports.write=function(buffer,value,offset,isLE,mLen,nBytes){var e,m,c,eLen=nBytes*8-mLen-1,eMax=(1<<eLen)-1,eBias=eMax>>1,rt=mLen===23?Math.pow(2,-24)-Math.pow(2,-77):0,i=isLE?0:nBytes-1,d=isLE?1:-1,s=value<0||value===0&&1/value<0?1:0;value=Math.abs(value);if(isNaN(value)||value===Infinity){m=isNaN(value)?1:0;e=eMax}else{e=Math.floor(Math.log(value)/Math.LN2);if(value*(c=Math.pow(2,-e))<1){e--;c*=2}if(e+eBias>=1){value+=rt/c}else{value+=rt*Math.pow(2,1-eBias)}if(value*c>=2){e++;c/=2}if(e+eBias>=eMax){m=0;e=eMax}else if(e+eBias>=1){m=(value*c-1)*Math.pow(2,mLen);e=e+eBias}else{m=value*Math.pow(2,eBias-1)*Math.pow(2,mLen);e=0}}for(;mLen>=8;buffer[offset+i]=m&255,i+=d,m/=256,mLen-=8);e=e<<mLen|m;eLen+=mLen;for(;eLen>0;buffer[offset+i]=e&255,i+=d,e/=256,eLen-=8);buffer[offset+i-d]|=s*128}},{}],4:[function(require,module,exports){var isArray=Array.isArray;var str=Object.prototype.toString;module.exports=isArray||function(val){return!!val&&"[object Array]"==str.call(val)}},{}],5:[function(require,module,exports){"use strict";module.exports=getContours;function Segment(start,end,direction,height){this.start=start;this.end=end;this.direction=direction;this.height=height;this.visited=false;this.next=null;this.prev=null}function Vertex(x,y,segment,orientation){this.x=x;this.y=y;this.segment=segment;this.orientation=orientation}function getParallelCountours(array,direction){var n=array.shape[0];var m=array.shape[1];var contours=[];var a=false;var b=false;var c=false;var d=false;var x0=0;var i=0,j=0;for(j=0;j<m;++j){b=!!array.get(0,j);if(b===a){continue}if(a){contours.push(new Segment(x0,j,direction,0))}if(b){x0=j}a=b}if(a){contours.push(new Segment(x0,j,direction,0))}for(i=1;i<n;++i){a=false;b=false;x0=0;for(j=0;j<m;++j){c=!!array.get(i-1,j);d=!!array.get(i,j);if(c===a&&d===b){continue}if(a!==b){if(a){contours.push(new Segment(j,x0,direction,i))}else{contours.push(new Segment(x0,j,direction,i))}}if(c!==d){x0=j}a=c;b=d}if(a!==b){if(a){contours.push(new Segment(j,x0,direction,i))}else{contours.push(new Segment(x0,j,direction,i))}}}a=false;x0=0;for(j=0;j<m;++j){b=!!array.get(n-1,j);if(b===a){continue}if(a){contours.push(new Segment(j,x0,direction,n))}if(b){x0=j}a=b}if(a){contours.push(new Segment(j,x0,direction,n))}return contours}function getVertices(contours){var vertices=new Array(contours.length*2);for(var i=0;i<contours.length;++i){var h=contours[i];if(h.direction===0){vertices[2*i]=new Vertex(h.start,h.height,h,0);vertices[2*i+1]=new Vertex(h.end,h.height,h,1)}else{vertices[2*i]=new Vertex(h.height,h.start,h,0);vertices[2*i+1]=new Vertex(h.height,h.end,h,1)}}return vertices}function walk(v,clockwise){var result=[];while(!v.visited){v.visited=true;if(v.direction){result.push([v.height,v.end])}else{result.push([v.start,v.height])}if(clockwise){v=v.next}else{v=v.prev}}return result}function compareVertex(a,b){var d=a.x-b.x;if(d){return d}d=a.y-b.y;if(d){return d}return a.orientation-b.orientation}function getContours(array,clockwise){var clockwise=!!clockwise;var hcontours=getParallelCountours(array,0);var hvertices=getVertices(hcontours);hvertices.sort(compareVertex);var vcontours=getParallelCountours(array.transpose(1,0),1);var vvertices=getVertices(vcontours);vvertices.sort(compareVertex);var nv=hvertices.length;for(var i=0;i<nv;++i){var h=hvertices[i];var v=vvertices[i];if(h.orientation){h.segment.next=v.segment;v.segment.prev=h.segment}else{h.segment.prev=v.segment;v.segment.next=h.segment}}var loops=[];for(var i=0;i<hcontours.length;++i){var h=hcontours[i];if(!h.visited){loops.push(walk(h,clockwise))}}return loops}},{}],6:[function(require,module,exports){"use strict";var pool=require("typedarray-pool");var uniq=require("uniq");var iota=require("iota-array");function generateMesher(order,skip,merge,append,num_options,options,useGetter){var code=[];var d=order.length;var i,j,k;var append_args=new Array(2*d+1+num_options);for(i=0;i<d;++i){append_args[i]="i"+i}for(i=0;i<d;++i){append_args[i+d]="j"+i}append_args[2*d]="oval";var opt_args=new Array(num_options);for(i=0;i<num_options;++i){opt_args[i]="opt"+i;append_args[2*d+1+i]="opt"+i}code.push("var data=array.data,offset=array.offset,shape=array.shape,stride=array.stride");for(var i=0;i<d;++i){code.push(["var stride",i,"=stride[",order[i],"]|0,shape",i,"=shape[",order[i],"]|0"].join(""));if(i>0){code.push(["var astep",i,"=(stride",i,"-stride",i-1,"*shape",i-1,")|0"].join(""))}else{code.push(["var astep",i,"=stride",i,"|0"].join(""))}if(i>0){code.push(["var vstep",i,"=(vstep",i-1,"*shape",i-1,")|0"].join(""))}else{code.push(["var vstep",i,"=1"].join(""))}code.push(["var i",i,"=0,j",i,"=0,k",i,"=0,ustep",i,"=vstep",i,"|0,bstep",i,"=astep",i,"|0"].join(""))}code.push("var a_ptr=offset>>>0,b_ptr=0,u_ptr=0,v_ptr=0,i=0,d=0,val=0,oval=0");code.push("var count="+iota(d).map(function(i){return"shape"+i}).join("*"));code.push("var visited=mallocUint8(count)");code.push("for(;i<count;++i){visited[i]=0}");for(i=d-1;i>=0;--i){code.push(["for(i",i,"=0;i",i,"<shape",i,";++i",i,"){"].join(""))}code.push("if(!visited[v_ptr]){");if(useGetter){code.push("val=data.get(a_ptr)")}else{code.push("val=data[a_ptr]")}if(skip){code.push("if(!skip(val)){")}else{code.push("if(val!==0){")}code.push("oval = val");for(i=0;i<d;++i){code.push("u_ptr=v_ptr+vstep"+i);code.push("b_ptr=a_ptr+stride"+i);code.push(["j",i,"_loop: for(j",i,"=1+i",i,";j",i,"<shape",i,";++j",i,"){"].join(""));for(j=i-1;j>=0;--j){code.push(["for(k",j,"=i",j,";k",j,"<j",j,";++k",j,"){"].join(""))}code.push("if(visited[u_ptr]) { break j"+i+"_loop; }");if(useGetter){code.push("val=data.get(b_ptr)")}else{code.push("val=data[b_ptr]")}if(skip&&merge){code.push("if(skip(val) || !merge(oval,val)){ break j"+i+"_loop; }")}else if(skip){code.push("if(skip(val) || val !== oval){ break j"+i+"_loop; }")}else if(merge){code.push("if(val === 0 || !merge(oval,val)){ break j"+i+"_loop; }")}else{code.push("if(val === 0 || val !== oval){ break j"+i+"_loop; }")}code.push("++u_ptr");code.push("b_ptr+=stride0");code.push("}");for(j=1;j<=i;++j){code.push("u_ptr+=ustep"+j);code.push("b_ptr+=bstep"+j);code.push("}")}if(i<d-1){code.push("d=j"+i+"-i"+i);code.push(["ustep",i+1,"=(vstep",i+1,"-vstep",i,"*d)|0"].join(""));code.push(["bstep",i+1,"=(stride",i+1,"-stride",i,"*d)|0"].join(""))}}code.push("u_ptr=v_ptr");for(i=d-1;i>=0;--i){code.push(["for(k",i,"=i",i,";k",i,"<j",i,";++k",i,"){"].join(""))}code.push("visited[u_ptr++]=1");code.push("}");for(i=1;i<d;++i){code.push("u_ptr+=ustep"+i);code.push("}")}code.push("append("+append_args.join(",")+")");code.push("}");code.push("}");code.push("++v_ptr");for(var i=0;i<d;++i){code.push("a_ptr+=astep"+i);code.push("}")}code.push("freeUint8(visited)");if(options.debug){console.log("GENERATING MESHER:");console.log(code.join("\n"))}var args=["append","mallocUint8","freeUint8"];if(merge){args.unshift("merge")}if(skip){args.unshift("skip")}var local_args=["array"].concat(opt_args);var funcName=["greedyMesher",d,"d_ord",order.join("s"),skip?"skip":"",merge?"merge":""].join("");var gen_body=["'use strict';function ",funcName,"(",local_args.join(","),"){",code.join("\n"),"};return ",funcName].join("");args.push(gen_body);var proc=Function.apply(undefined,args);if(skip&&merge){return proc(skip,merge,append,pool.mallocUint8,pool.freeUint8)}else if(skip){return proc(skip,append,pool.mallocUint8,pool.freeUint8)}else if(merge){return proc(merge,append,pool.mallocUint8,pool.freeUint8)}else{return proc(append,pool.mallocUint8,pool.freeUint8)}}function compileMesher(options){options=options||{};if(!options.order){throw new Error("greedy-mesher: Missing order field")}if(!options.append){throw new Error("greedy-mesher: Missing append field")}return generateMesher(options.order,options.skip,options.merge,options.append,options.extraArgs|0,options,!!options.useGetter)}module.exports=compileMesher},{"iota-array":7,"typedarray-pool":10,uniq:11}],7:[function(require,module,exports){"use strict";function iota(n){var result=new Array(n);for(var i=0;i<n;++i){result[i]=i}return result}module.exports=iota},{}],8:[function(require,module,exports){"use strict";"use restrict";var INT_BITS=32;exports.INT_BITS=INT_BITS;exports.INT_MAX=2147483647;exports.INT_MIN=-1<<INT_BITS-1;exports.sign=function(v){return(v>0)-(v<0)};exports.abs=function(v){var mask=v>>INT_BITS-1;return(v^mask)-mask};exports.min=function(x,y){return y^(x^y)&-(x<y)};exports.max=function(x,y){return x^(x^y)&-(x<y)};exports.isPow2=function(v){return!(v&v-1)&&!!v};exports.log2=function(v){var r,shift;r=(v>65535)<<4;v>>>=r;shift=(v>255)<<3;v>>>=shift;r|=shift;shift=(v>15)<<2;v>>>=shift;r|=shift;shift=(v>3)<<1;v>>>=shift;r|=shift;return r|v>>1};exports.log10=function(v){return v>=1e9?9:v>=1e8?8:v>=1e7?7:v>=1e6?6:v>=1e5?5:v>=1e4?4:v>=1e3?3:v>=100?2:v>=10?1:0};exports.popCount=function(v){v=v-(v>>>1&1431655765);v=(v&858993459)+(v>>>2&858993459);return(v+(v>>>4)&252645135)*16843009>>>24};function countTrailingZeros(v){var c=32;v&=-v;if(v)c--;if(v&65535)c-=16;if(v&16711935)c-=8;if(v&252645135)c-=4;if(v&858993459)c-=2;if(v&1431655765)c-=1;return c}exports.countTrailingZeros=countTrailingZeros;exports.nextPow2=function(v){v+=v===0;--v;v|=v>>>1;v|=v>>>2;v|=v>>>4;v|=v>>>8;v|=v>>>16;return v+1};exports.prevPow2=function(v){v|=v>>>1;v|=v>>>2;v|=v>>>4;v|=v>>>8;v|=v>>>16;return v-(v>>>1)};exports.parity=function(v){v^=v>>>16;v^=v>>>8;v^=v>>>4;v&=15;return 27030>>>v&1};var REVERSE_TABLE=new Array(256);(function(tab){for(var i=0;i<256;++i){var v=i,r=i,s=7;for(v>>>=1;v;v>>>=1){r<<=1;r|=v&1;--s}tab[i]=r<<s&255}})(REVERSE_TABLE);exports.reverse=function(v){return REVERSE_TABLE[v&255]<<24|REVERSE_TABLE[v>>>8&255]<<16|REVERSE_TABLE[v>>>16&255]<<8|REVERSE_TABLE[v>>>24&255]};exports.interleave2=function(x,y){x&=65535;x=(x|x<<8)&16711935;x=(x|x<<4)&252645135;x=(x|x<<2)&858993459;x=(x|x<<1)&1431655765;y&=65535;y=(y|y<<8)&16711935;y=(y|y<<4)&252645135;y=(y|y<<2)&858993459;y=(y|y<<1)&1431655765;return x|y<<1};exports.deinterleave2=function(v,n){v=v>>>n&1431655765;v=(v|v>>>1)&858993459;v=(v|v>>>2)&252645135;v=(v|v>>>4)&16711935;v=(v|v>>>16)&65535;return v<<16>>16};exports.interleave3=function(x,y,z){x&=1023;x=(x|x<<16)&4278190335;x=(x|x<<8)&251719695;x=(x|x<<4)&3272356035;x=(x|x<<2)&1227133513;y&=1023;y=(y|y<<16)&4278190335;y=(y|y<<8)&251719695;y=(y|y<<4)&3272356035;y=(y|y<<2)&1227133513;x|=y<<1;z&=1023;z=(z|z<<16)&4278190335;z=(z|z<<8)&251719695;z=(z|z<<4)&3272356035;z=(z|z<<2)&1227133513;return x|z<<2};exports.deinterleave3=function(v,n){v=v>>>n&1227133513;v=(v|v>>>2)&3272356035;v=(v|v>>>4)&251719695;v=(v|v>>>8)&4278190335;v=(v|v>>>16)&1023;return v<<22>>22};exports.nextCombination=function(v){var t=v|v-1;return t+1|(~t&-~t)-1>>>countTrailingZeros(v)+1}},{}],9:[function(require,module,exports){"use strict";function dupe_array(count,value,i){var c=count[i]|0;if(c<=0){return[]}var result=new Array(c),j;if(i===count.length-1){for(j=0;j<c;++j){result[j]=value}}else{for(j=0;j<c;++j){result[j]=dupe_array(count,value,i+1)}}return result}function dupe_number(count,value){var result,i;result=new Array(count);for(i=0;i<count;++i){result[i]=value}return result}function dupe(count,value){if(typeof value==="undefined"){value=0}switch(typeof count){case"number":if(count>0){return dupe_number(count|0,value)}break;case"object":if(typeof count.length==="number"){return dupe_array(count,value,0)}break}return[]}module.exports=dupe},{}],10:[function(require,module,exports){(function(global,Buffer){"use strict";var bits=require("bit-twiddle");var dup=require("dup");if(!global.__TYPEDARRAY_POOL){global.__TYPEDARRAY_POOL={UINT8:dup([32,0]),UINT16:dup([32,0]),UINT32:dup([32,0]),INT8:dup([32,0]),INT16:dup([32,0]),INT32:dup([32,0]),FLOAT:dup([32,0]),DOUBLE:dup([32,0]),DATA:dup([32,0]),UINT8C:dup([32,0]),BUFFER:dup([32,0])}}var hasUint8C=typeof Uint8ClampedArray!=="undefined";var POOL=global.__TYPEDARRAY_POOL;if(!POOL.UINT8C){POOL.UINT8C=dup([32,0])}if(!POOL.BUFFER){POOL.BUFFER=dup([32,0])}var DATA=POOL.DATA,BUFFER=POOL.BUFFER;exports.free=function free(array){if(Buffer.isBuffer(array)){BUFFER[bits.log2(array.length)].push(array)}else{if(Object.prototype.toString.call(array)!=="[object ArrayBuffer]"){array=array.buffer}if(!array){return}var n=array.length||array.byteLength;var log_n=bits.log2(n)|0;DATA[log_n].push(array)}};function freeArrayBuffer(buffer){if(!buffer){return}var n=buffer.length||buffer.byteLength;var log_n=bits.log2(n);DATA[log_n].push(buffer)}function freeTypedArray(array){freeArrayBuffer(array.buffer)}exports.freeUint8=exports.freeUint16=exports.freeUint32=exports.freeInt8=exports.freeInt16=exports.freeInt32=exports.freeFloat32=exports.freeFloat=exports.freeFloat64=exports.freeDouble=exports.freeUint8Clamped=exports.freeDataView=freeTypedArray;exports.freeArrayBuffer=freeArrayBuffer;exports.freeBuffer=function freeBuffer(array){BUFFER[bits.log2(array.length)].push(array)};exports.malloc=function malloc(n,dtype){if(dtype===undefined||dtype==="arraybuffer"){return mallocArrayBuffer(n)}else{switch(dtype){case"uint8":return mallocUint8(n);case"uint16":return mallocUint16(n);case"uint32":return mallocUint32(n);case"int8":return mallocInt8(n);case"int16":return mallocInt16(n);case"int32":return mallocInt32(n);case"float":case"float32":return mallocFloat(n);case"double":case"float64":return mallocDouble(n);case"uint8_clamped":return mallocUint8Clamped(n);case"buffer":return mallocBuffer(n);case"data":case"dataview":return mallocDataView(n);default:return null}}return null};function mallocArrayBuffer(n){var n=bits.nextPow2(n);var log_n=bits.log2(n);var d=DATA[log_n];if(d.length>0){return d.pop()}return new ArrayBuffer(n)}exports.mallocArrayBuffer=mallocArrayBuffer;function mallocUint8(n){return new Uint8Array(mallocArrayBuffer(n),0,n)}exports.mallocUint8=mallocUint8;function mallocUint16(n){return new Uint16Array(mallocArrayBuffer(2*n),0,n)}exports.mallocUint16=mallocUint16;function mallocUint32(n){return new Uint32Array(mallocArrayBuffer(4*n),0,n)}exports.mallocUint32=mallocUint32;function mallocInt8(n){return new Int8Array(mallocArrayBuffer(n),0,n)}exports.mallocInt8=mallocInt8;function mallocInt16(n){return new Int16Array(mallocArrayBuffer(2*n),0,n)}exports.mallocInt16=mallocInt16;function mallocInt32(n){return new Int32Array(mallocArrayBuffer(4*n),0,n)}exports.mallocInt32=mallocInt32;function mallocFloat(n){return new Float32Array(mallocArrayBuffer(4*n),0,n)}exports.mallocFloat32=exports.mallocFloat=mallocFloat;function mallocDouble(n){return new Float64Array(mallocArrayBuffer(8*n),0,n)}exports.mallocFloat64=exports.mallocDouble=mallocDouble;function mallocUint8Clamped(n){if(hasUint8C){return new Uint8ClampedArray(mallocArrayBuffer(n),0,n)}else{return mallocUint8(n)}}exports.mallocUint8Clamped=mallocUint8Clamped;function mallocDataView(n){return new DataView(mallocArrayBuffer(n),0,n); | |
| }exports.mallocDataView=mallocDataView;function mallocBuffer(n){n=bits.nextPow2(n);var log_n=bits.log2(n);var cache=BUFFER[log_n];if(cache.length>0){return cache.pop()}return new Buffer(n)}exports.mallocBuffer=mallocBuffer;exports.clearCache=function clearCache(){for(var i=0;i<32;++i){POOL.UINT8[i].length=0;POOL.UINT16[i].length=0;POOL.UINT32[i].length=0;POOL.INT8[i].length=0;POOL.INT16[i].length=0;POOL.INT32[i].length=0;POOL.FLOAT[i].length=0;POOL.DOUBLE[i].length=0;POOL.UINT8C[i].length=0;DATA[i].length=0;BUFFER[i].length=0}}}).call(this,typeof global!=="undefined"?global:typeof self!=="undefined"?self:typeof window!=="undefined"?window:{},require("buffer").Buffer)},{"bit-twiddle":8,buffer:1,dup:9}],11:[function(require,module,exports){"use strict";function unique_pred(list,compare){var ptr=1,len=list.length,a=list[0],b=list[0];for(var i=1;i<len;++i){b=a;a=list[i];if(compare(a,b)){if(i===ptr){ptr++;continue}list[ptr++]=a}}list.length=ptr;return list}function unique_eq(list){var ptr=1,len=list.length,a=list[0],b=list[0];for(var i=1;i<len;++i,b=a){b=a;a=list[i];if(a!==b){if(i===ptr){ptr++;continue}list[ptr++]=a}}list.length=ptr;return list}function unique(list,compare,sorted){if(list.length===0){return list}if(compare){if(!sorted){list.sort(compare)}return unique_pred(list,compare)}if(!sorted){list.sort()}return unique_eq(list)}module.exports=unique},{}],12:[function(require,module,exports){"use strict";var bipartiteIndependentSet=require("bipartite-independent-set");var createIntervalTree=require("interval-tree-1d");var dup=require("dup");module.exports=decomposeRegion;function Vertex(point,path,index,concave){this.point=point;this.path=path;this.index=index;this.concave=concave;this.next=null;this.prev=null;this.visited=false}function Segment(start,end,direction){var a=start.point[direction^1];var b=end.point[direction^1];if(a<b){this[0]=a;this[1]=b}else{this[0]=b;this[1]=a}this.start=start;this.end=end;this.direction=direction;this.number=-1}function testSegment(a,b,tree,direction){var ax=a.point[direction^1];var bx=b.point[direction^1];return!!tree.queryPoint(a.point[direction],function(s){var x=s.start.point[direction^1];if(ax<x&&x<bx){return true}return false})}function getDiagonals(vertices,paths,direction,tree){var concave=[];for(var i=0;i<vertices.length;++i){if(vertices[i].concave){concave.push(vertices[i])}}concave.sort(function(a,b){var d=a.point[direction]-b.point[direction];if(d){return d}return a.point[direction^1]-b.point[direction^1]});var diagonals=[];for(var i=1;i<concave.length;++i){var a=concave[i-1];var b=concave[i];if(a.point[direction]===b.point[direction]){if(a.path===b.path){var n=paths[a.path].length;var d=(a.index-b.index+n)%n;if(d===1||d===n-1){continue}}if(!testSegment(a,b,tree,direction)){diagonals.push(new Segment(a,b,direction))}}}return diagonals}function findCrossings(hdiagonals,vdiagonals){var htree=createIntervalTree(hdiagonals);var crossings=[];for(var i=0;i<vdiagonals.length;++i){var v=vdiagonals[i];var x=v.start.point[0];htree.queryPoint(v.start.point[1],function(h){var x=h.start.point[0];if(v[0]<=x&&x<=v[1]){crossings.push([h,v])}})}return crossings}function findSplitters(hdiagonals,vdiagonals){var crossings=findCrossings(hdiagonals,vdiagonals);for(var i=0;i<hdiagonals.length;++i){hdiagonals[i].number=i}for(var i=0;i<vdiagonals.length;++i){vdiagonals[i].number=i}var edges=crossings.map(function(c){return[c[0].number,c[1].number]});var selected=bipartiteIndependentSet(hdiagonals.length,vdiagonals.length,edges);var result=new Array(selected[0].length+selected[1].length);var ptr=0;for(var i=0;i<selected[0].length;++i){result[ptr++]=hdiagonals[selected[0][i]]}for(var i=0;i<selected[1].length;++i){result[ptr++]=vdiagonals[selected[1][i]]}return result}function splitSegment(segment){var a=segment.start;var b=segment.end;var pa=a.prev;var na=a.next;var pb=b.prev;var nb=b.next;a.concave=false;b.concave=false;var ao=pa.point[segment.direction]===a.point[segment.direction];var bo=pb.point[segment.direction]===b.point[segment.direction];if(ao&&bo){a.prev=pb;pb.next=a;b.prev=pa;pa.next=b}else if(ao&&!bo){a.prev=b;b.next=a;pa.next=nb;nb.prev=pa}else if(!ao&&bo){a.next=b;b.prev=a;na.prev=pb;pb.next=na}else if(!ao&&!bo){a.next=nb;nb.prev=a;b.next=na;na.prev=b}}function findLoops(vertices){for(var i=0;i<vertices.length;++i){vertices[i].visited=false}var loops=[];for(var i=0;i<vertices.length;++i){var v=vertices[i];if(v.visited){continue}var loop=[];while(!v.visited){loop.push(v);v.visited=true;v=v.next}loops.push(loop)}return loops}function splitConcave(vertices){var leftsegments=[];var rightsegments=[];for(var i=0;i<vertices.length;++i){var v=vertices[i];if(v.next.point[1]===v.point[1]){if(v.next.point[0]<v.point[0]){leftsegments.push(new Segment(v,v.next,1))}else{rightsegments.push(new Segment(v,v.next,1))}}}var lefttree=createIntervalTree(leftsegments);var righttree=createIntervalTree(rightsegments);for(var i=0;i<vertices.length;++i){var v=vertices[i];if(!v.concave){continue}var y=v.point[1];var direction;if(v.prev.point[0]===v.point[0]){direction=v.prev.point[1]<y}else{direction=v.next.point[1]<y}direction=direction?1:-1;var closestSegment=null;var closestDistance=Infinity*direction;if(direction<0){righttree.queryPoint(v.point[0],function(h){var x=h.start.point[1];if(x<y&&x>closestDistance){closestDistance=x;closestSegment=h}})}else{lefttree.queryPoint(v.point[0],function(h){var x=h.start.point[1];if(x>y&&x<closestDistance){closestDistance=x;closestSegment=h}})}var splitA=new Vertex([v.point[0],closestDistance],0,0,false);var splitB=new Vertex([v.point[0],closestDistance],0,0,false);v.concave=false;splitA.prev=closestSegment.start;closestSegment.start.next=splitA;splitB.next=closestSegment.end;closestSegment.end.prev=splitB;var tree;if(direction<0){tree=righttree}else{tree=lefttree}tree.remove(closestSegment);tree.insert(new Segment(closestSegment.start,splitA,1));tree.insert(new Segment(splitB,closestSegment.end,1));vertices.push(splitA,splitB);if(v.prev.point[0]===v.point[0]){splitA.next=v;splitB.prev=v.prev}else{splitA.next=v.next;splitB.prev=v}splitA.next.prev=splitA;splitB.prev.next=splitB}}function findRegions(vertices){var n=vertices.length;for(var i=0;i<n;++i){vertices[i].visited=false}var rectangles=[];for(var i=0;i<n;++i){var v=vertices[i];if(v.visited){continue}var lo=[Infinity,Infinity];var hi=[-Infinity,-Infinity];while(!v.visited){for(var j=0;j<2;++j){lo[j]=Math.min(v.point[j],lo[j]);hi[j]=Math.max(v.point[j],hi[j])}v.visited=true;v=v.next}rectangles.push([lo,hi])}return rectangles}function decomposeRegion(paths,clockwise){if(!Array.isArray(paths)){throw new Error("rectangle-decomposition: Must specify list of loops")}clockwise=!!clockwise;var vertices=[];var ptr=0;var npaths=new Array(paths.length);for(var i=0;i<paths.length;++i){var path=paths[i];if(!Array.isArray(path)){throw new Error("rectangle-decomposition: Loop must be array type")}var n=path.length;var prev=path[n-3];var cur=path[n-2];var next=path[n-1];npaths[i]=[];for(var j=0;j<n;++j){prev=cur;cur=next;next=path[j];if(!Array.isArray(next)||next.length!==2){throw new Error("rectangle-decomposition: Must specify list of loops")}var concave=false;if(prev[0]===cur[0]){if(next[0]===cur[0]){continue}var dir0=prev[1]<cur[1];var dir1=cur[0]<next[0];concave=dir0===dir1}else{if(next[1]===cur[1]){continue}var dir0=prev[0]<cur[0];var dir1=cur[1]<next[1];concave=dir0!==dir1}if(clockwise){concave=!concave}var vtx=new Vertex(cur,i,(j+n-1)%n,concave);npaths[i].push(vtx);vertices.push(vtx)}}var hsegments=[];var vsegments=[];for(var i=0;i<npaths.length;++i){var p=npaths[i];for(var j=0;j<p.length;++j){var a=p[j];var b=p[(j+1)%p.length];if(a.point[0]===b.point[0]){hsegments.push(new Segment(a,b,0))}else{vsegments.push(new Segment(a,b,1))}if(clockwise){a.prev=b;b.next=a}else{a.next=b;b.prev=a}}}var htree=createIntervalTree(hsegments);var vtree=createIntervalTree(vsegments);var hdiagonals=getDiagonals(vertices,npaths,0,vtree);var vdiagonals=getDiagonals(vertices,npaths,1,htree);var splitters=findSplitters(hdiagonals,vdiagonals);for(var i=0;i<splitters.length;++i){splitSegment(splitters[i])}splitConcave(vertices);return findRegions(vertices)}},{"bipartite-independent-set":13,dup:19,"interval-tree-1d":20}],13:[function(require,module,exports){"use strict";var vertexCover=require("bipartite-vertex-cover");module.exports=bipartiteIndependentSet;function compareInt(a,b){return a-b}function complement(list,n){var k=list.length;var result=new Array(n-k);var a=0;var b=0;list.sort(compareInt);for(var i=0;i<n;++i){if(list[a]===i){a+=1}else{result[b++]=i}}return result}function bipartiteIndependentSet(n,m,edges){var cover=vertexCover(n,m,edges);return[complement(cover[0],n),complement(cover[1],m)]}},{"bipartite-vertex-cover":18}],14:[function(require,module,exports){"use strict";var pool=require("typedarray-pool");var INF=1<<28;module.exports=bipartiteMatching;function bipartiteMatching(n,m,edges){var adjN=new Array(n);var g1=pool.mallocInt32(n);var dist=pool.mallocInt32(n);for(var i=0;i<n;++i){g1[i]=-1;adjN[i]=[];dist[i]=INF}var adjM=new Array(m);var g2=pool.mallocInt32(m);for(var i=0;i<m;++i){g2[i]=-1;adjM[i]=[]}var E=edges.length;for(var i=0;i<E;++i){var e=edges[i];adjN[e[0]].push(e[1]);adjM[e[1]].push(e[0])}var dmax=INF;function dfs(v){if(v<0){return true}var adj=adjN[v];for(var i=0,l=adj.length;i<l;++i){var u=adj[i];var pu=g2[u];var dpu=dmax;if(pu>=0){dpu=dist[pu]}if(dpu===dist[v]+1){if(dfs(pu)){g1[v]=u;g2[u]=v;return true}}}dist[v]=INF;return false}var toVisit=pool.mallocInt32(n);var matching=0;while(true){var count=0;for(var i=0;i<n;++i){if(g1[i]<0){dist[i]=0;toVisit[count++]=i}else{dist[i]=INF}}var ptr=0;dmax=INF;while(ptr<count){var v=toVisit[ptr++];var dv=dist[v];if(dv<dmax){var adj=adjN[v];for(var j=0,l=adj.length;j<l;++j){var u=adj[j];var pu=g2[u];if(pu<0){if(dmax===INF){dmax=dv+1}}else if(dist[pu]===INF){dist[pu]=dv+1;toVisit[count++]=pu}}}}if(dmax===INF){break}for(var i=0;i<n;++i){if(g1[i]<0){if(dfs(i)){matching+=1}}}}var count=0;var result=new Array(matching);for(var i=0;i<n;++i){if(g1[i]<0){continue}result[count++]=[i,g1[i]]}pool.free(toVisit);pool.free(g2);pool.free(dist);pool.free(g1);return result}},{"typedarray-pool":17}],15:[function(require,module,exports){arguments[4][7][0].apply(exports,arguments)},{dup:7}],16:[function(require,module,exports){arguments[4][8][0].apply(exports,arguments)},{dup:8}],17:[function(require,module,exports){(function(global,Buffer){"use strict";var bits=require("bit-twiddle");var dup=require("dup");if(!global.__TYPEDARRAY_POOL){global.__TYPEDARRAY_POOL={UINT8:dup([32,0]),UINT16:dup([32,0]),UINT32:dup([32,0]),INT8:dup([32,0]),INT16:dup([32,0]),INT32:dup([32,0]),FLOAT:dup([32,0]),DOUBLE:dup([32,0]),DATA:dup([32,0]),UINT8C:dup([32,0]),BUFFER:dup([32,0])}}var hasUint8C=typeof Uint8ClampedArray!=="undefined";var POOL=global.__TYPEDARRAY_POOL;if(!POOL.UINT8C){POOL.UINT8C=dup([32,0])}if(!POOL.BUFFER){POOL.BUFFER=dup([32,0])}var DATA=POOL.DATA,BUFFER=POOL.BUFFER;exports.free=function free(array){if(Buffer.isBuffer(array)){BUFFER[bits.log2(array.length)].push(array)}else{if(Object.prototype.toString.call(array)!=="[object ArrayBuffer]"){array=array.buffer}if(!array){return}var n=array.length||array.byteLength;var log_n=bits.log2(n)|0;DATA[log_n].push(array)}};function freeArrayBuffer(buffer){if(!buffer){return}var n=buffer.length||buffer.byteLength;var log_n=bits.log2(n);DATA[log_n].push(buffer)}function freeTypedArray(array){freeArrayBuffer(array.buffer)}exports.freeUint8=exports.freeUint16=exports.freeUint32=exports.freeInt8=exports.freeInt16=exports.freeInt32=exports.freeFloat32=exports.freeFloat=exports.freeFloat64=exports.freeDouble=exports.freeUint8Clamped=exports.freeDataView=freeTypedArray;exports.freeArrayBuffer=freeArrayBuffer;exports.freeBuffer=function freeBuffer(array){BUFFER[bits.log2(array.length)].push(array)};exports.malloc=function malloc(n,dtype){if(dtype===undefined||dtype==="arraybuffer"){return mallocArrayBuffer(n)}else{switch(dtype){case"uint8":return mallocUint8(n);case"uint16":return mallocUint16(n);case"uint32":return mallocUint32(n);case"int8":return mallocInt8(n);case"int16":return mallocInt16(n);case"int32":return mallocInt32(n);case"float":case"float32":return mallocFloat(n);case"double":case"float64":return mallocDouble(n);case"uint8_clamped":return mallocUint8Clamped(n);case"buffer":return mallocBuffer(n);case"data":case"dataview":return mallocDataView(n);default:return null}}return null};function mallocArrayBuffer(n){var n=bits.nextPow2(n);var log_n=bits.log2(n);var d=DATA[log_n];if(d.length>0){return d.pop()}return new ArrayBuffer(n)}exports.mallocArrayBuffer=mallocArrayBuffer;function mallocUint8(n){return new Uint8Array(mallocArrayBuffer(n),0,n)}exports.mallocUint8=mallocUint8;function mallocUint16(n){return new Uint16Array(mallocArrayBuffer(2*n),0,n)}exports.mallocUint16=mallocUint16;function mallocUint32(n){return new Uint32Array(mallocArrayBuffer(4*n),0,n)}exports.mallocUint32=mallocUint32;function mallocInt8(n){return new Int8Array(mallocArrayBuffer(n),0,n)}exports.mallocInt8=mallocInt8;function mallocInt16(n){return new Int16Array(mallocArrayBuffer(2*n),0,n)}exports.mallocInt16=mallocInt16;function mallocInt32(n){return new Int32Array(mallocArrayBuffer(4*n),0,n)}exports.mallocInt32=mallocInt32;function mallocFloat(n){return new Float32Array(mallocArrayBuffer(4*n),0,n)}exports.mallocFloat32=exports.mallocFloat=mallocFloat;function mallocDouble(n){return new Float64Array(mallocArrayBuffer(8*n),0,n)}exports.mallocFloat64=exports.mallocDouble=mallocDouble;function mallocUint8Clamped(n){if(hasUint8C){return new Uint8ClampedArray(mallocArrayBuffer(n),0,n)}else{return mallocUint8(n)}}exports.mallocUint8Clamped=mallocUint8Clamped;function mallocDataView(n){return new DataView(mallocArrayBuffer(n),0,n)}exports.mallocDataView=mallocDataView;function mallocBuffer(n){n=bits.nextPow2(n);var log_n=bits.log2(n);var cache=BUFFER[log_n];if(cache.length>0){return cache.pop()}return new Buffer(n)}exports.mallocBuffer=mallocBuffer;exports.clearCache=function clearCache(){for(var i=0;i<32;++i){POOL.UINT8[i].length=0;POOL.UINT16[i].length=0;POOL.UINT32[i].length=0;POOL.INT8[i].length=0;POOL.INT16[i].length=0;POOL.INT32[i].length=0;POOL.FLOAT[i].length=0;POOL.DOUBLE[i].length=0;POOL.UINT8C[i].length=0;DATA[i].length=0;BUFFER[i].length=0}}}).call(this,typeof global!=="undefined"?global:typeof self!=="undefined"?self:typeof window!=="undefined"?window:{},require("buffer").Buffer)},{"bit-twiddle":16,buffer:1,dup:19}],18:[function(require,module,exports){"use strict";var pool=require("typedarray-pool");var iota=require("iota-array");var bipartiteMatching=require("bipartite-matching");module.exports=bipartiteVertexCover;function walk(list,v,adjL,matchL,coverL,matchR,coverR){if(coverL[v]||matchL[v]>=0){return}while(v>=0){coverL[v]=1;var adj=adjL[v];var next=-1;for(var i=0,l=adj.length;i<l;++i){var u=adj[i];if(coverR[u]){continue}next=u}if(next<0){break}coverR[next]=1;list.push(next);v=matchR[next]}}function bipartiteVertexCover(n,m,edges){var match=bipartiteMatching(n,m,edges);var adjL=new Array(n);var matchL=pool.mallocInt32(n);var matchCount=pool.mallocInt32(n);var coverL=pool.mallocInt32(n);for(var i=0;i<n;++i){adjL[i]=[];matchL[i]=-1;matchCount[i]=0;coverL[i]=0}var adjR=new Array(m);var matchR=pool.mallocInt32(m);var coverR=pool.mallocInt32(m);for(var i=0;i<m;++i){adjR[i]=[];matchR[i]=-1;coverR[i]=0}for(var i=0,l=match.length;i<l;++i){var s=match[i][0];var t=match[i][1];matchL[s]=t;matchR[t]=s}for(var i=0,l=edges.length;i<l;++i){var e=edges[i];var s=e[0];var t=e[1];if(matchL[s]===t){if(!matchCount[s]++){continue}}adjL[s].push(t);adjR[t].push(s)}var left=[];var right=[];for(var i=0;i<n;++i){walk(right,i,adjL,matchL,coverL,matchR,coverR)}for(var i=0;i<m;++i){walk(left,i,adjR,matchR,coverR,matchL,coverL)}for(var i=0;i<n;++i){if(!coverL[i]&&matchL[i]>=0){coverR[matchL[i]]=coverL[i]=1;left.push(i)}}pool.free(coverR);pool.free(matchR);pool.free(coverL);pool.free(matchCount);pool.free(matchL);return[left,right]}},{"bipartite-matching":14,"iota-array":15,"typedarray-pool":17}],19:[function(require,module,exports){arguments[4][9][0].apply(exports,arguments)},{dup:9}],20:[function(require,module,exports){"use strict";var bounds=require("binary-search-bounds");var NOT_FOUND=0;var SUCCESS=1;var EMPTY=2;module.exports=createWrapper;function IntervalTreeNode(mid,left,right,leftPoints,rightPoints){this.mid=mid;this.left=left;this.right=right;this.leftPoints=leftPoints;this.rightPoints=rightPoints;this.count=(left?left.count:0)+(right?right.count:0)+leftPoints.length}var proto=IntervalTreeNode.prototype;function copy(a,b){a.mid=b.mid;a.left=b.left;a.right=b.right;a.leftPoints=b.leftPoints;a.rightPoints=b.rightPoints;a.count=b.count}function rebuild(node,intervals){var ntree=createIntervalTree(intervals);node.mid=ntree.mid;node.left=ntree.left;node.right=ntree.right;node.leftPoints=ntree.leftPoints;node.rightPoints=ntree.rightPoints;node.count=ntree.count}function rebuildWithInterval(node,interval){var intervals=node.intervals([]);intervals.push(interval);rebuild(node,intervals)}function rebuildWithoutInterval(node,interval){var intervals=node.intervals([]);var idx=intervals.indexOf(interval);if(idx<0){return NOT_FOUND}intervals.splice(idx,1);rebuild(node,intervals);return SUCCESS}proto.intervals=function(result){result.push.apply(result,this.leftPoints);if(this.left){this.left.intervals(result)}if(this.right){this.right.intervals(result)}return result};proto.insert=function(interval){var weight=this.count-this.leftPoints.length;this.count+=1;if(interval[1]<this.mid){if(this.left){if(4*(this.left.count+1)>3*(weight+1)){rebuildWithInterval(this,interval)}else{this.left.insert(interval)}}else{this.left=createIntervalTree([interval])}}else if(interval[0]>this.mid){if(this.right){if(4*(this.right.count+1)>3*(weight+1)){rebuildWithInterval(this,interval)}else{this.right.insert(interval)}}else{this.right=createIntervalTree([interval])}}else{var l=bounds.ge(this.leftPoints,interval,compareBegin);var r=bounds.ge(this.rightPoints,interval,compareEnd);this.leftPoints.splice(l,0,interval);this.rightPoints.splice(r,0,interval)}};proto.remove=function(interval){var weight=this.count-this.leftPoints;if(interval[1]<this.mid){if(!this.left){return NOT_FOUND}var rw=this.right?this.right.count:0;if(4*rw>3*(weight-1)){return rebuildWithoutInterval(this,interval)}var r=this.left.remove(interval);if(r===EMPTY){this.left=null;this.count-=1;return SUCCESS}else if(r===SUCCESS){this.count-=1}return r}else if(interval[0]>this.mid){if(!this.right){return NOT_FOUND}var lw=this.left?this.left.count:0;if(4*lw>3*(weight-1)){return rebuildWithoutInterval(this,interval)}var r=this.right.remove(interval);if(r===EMPTY){this.right=null;this.count-=1;return SUCCESS}else if(r===SUCCESS){this.count-=1}return r}else{if(this.count===1){if(this.leftPoints[0]===interval){return EMPTY}else{return NOT_FOUND}}if(this.leftPoints.length===1&&this.leftPoints[0]===interval){if(this.left&&this.right){var p=this;var n=this.left;while(n.right){p=n;n=n.right}if(p===this){n.right=this.right}else{var l=this.left;var r=this.right;p.count-=n.count;p.right=n.left;n.left=l;n.right=r}copy(this,n);this.count=(this.left?this.left.count:0)+(this.right?this.right.count:0)+this.leftPoints.length}else if(this.left){copy(this,this.left)}else{copy(this,this.right)}return SUCCESS}for(var l=bounds.ge(this.leftPoints,interval,compareBegin);l<this.leftPoints.length;++l){if(this.leftPoints[l][0]!==interval[0]){break}if(this.leftPoints[l]===interval){this.count-=1;this.leftPoints.splice(l,1);for(var r=bounds.ge(this.rightPoints,interval,compareEnd);r<this.rightPoints.length;++r){if(this.rightPoints[r][1]!==interval[1]){break}else if(this.rightPoints[r]===interval){this.rightPoints.splice(r,1);return SUCCESS}}}}return NOT_FOUND}};function reportLeftRange(arr,hi,cb){for(var i=0;i<arr.length&&arr[i][0]<=hi;++i){var r=cb(arr[i]);if(r){return r}}}function reportRightRange(arr,lo,cb){for(var i=arr.length-1;i>=0&&arr[i][1]>=lo;--i){var r=cb(arr[i]);if(r){return r}}}function reportRange(arr,cb){for(var i=0;i<arr.length;++i){var r=cb(arr[i]);if(r){return r}}}proto.queryPoint=function(x,cb){if(x<this.mid){if(this.left){var r=this.left.queryPoint(x,cb);if(r){return r}}return reportLeftRange(this.leftPoints,x,cb)}else if(x>this.mid){if(this.right){var r=this.right.queryPoint(x,cb);if(r){return r}}return reportRightRange(this.rightPoints,x,cb)}else{return reportRange(this.leftPoints,cb)}};proto.queryInterval=function(lo,hi,cb){if(lo<this.mid&&this.left){var r=this.left.queryInterval(lo,hi,cb);if(r){return r}}if(hi>this.mid&&this.right){var r=this.right.queryInterval(lo,hi,cb);if(r){return r}}if(hi<this.mid){return reportLeftRange(this.leftPoints,hi,cb)}else if(lo>this.mid){return reportRightRange(this.rightPoints,lo,cb)}else{return reportRange(this.leftPoints,cb)}};function compareNumbers(a,b){return a-b}function compareBegin(a,b){var d=a[0]-b[0];if(d){return d}return a[1]-b[1]}function compareEnd(a,b){var d=a[1]-b[1];if(d){return d}return a[0]-b[0]}function createIntervalTree(intervals){if(intervals.length===0){return null}var pts=[];for(var i=0;i<intervals.length;++i){pts.push(intervals[i][0],intervals[i][1])}pts.sort(compareNumbers);var mid=pts[pts.length>>1];var leftIntervals=[];var rightIntervals=[];var centerIntervals=[];for(var i=0;i<intervals.length;++i){var s=intervals[i];if(s[1]<mid){leftIntervals.push(s)}else if(mid<s[0]){rightIntervals.push(s)}else{centerIntervals.push(s)}}var leftPoints=centerIntervals;var rightPoints=centerIntervals.slice();leftPoints.sort(compareBegin);rightPoints.sort(compareEnd);return new IntervalTreeNode(mid,createIntervalTree(leftIntervals),createIntervalTree(rightIntervals),leftPoints,rightPoints)}function IntervalTree(root){this.root=root}var tproto=IntervalTree.prototype;tproto.insert=function(interval){if(this.root){this.root.insert(interval)}else{this.root=new IntervalTreeNode(interval[0],null,null,[interval],[interval])}};tproto.remove=function(interval){if(this.root){var r=this.root.remove(interval);if(r===EMPTY){this.root=null}return r!==NOT_FOUND}return false};tproto.queryPoint=function(p,cb){if(this.root){return this.root.queryPoint(p,cb)}};tproto.queryInterval=function(lo,hi,cb){if(lo<=hi&&this.root){return this.root.queryInterval(lo,hi,cb)}};Object.defineProperty(tproto,"count",{get:function(){if(this.root){return this.root.count}return 0}});Object.defineProperty(tproto,"intervals",{get:function(){if(this.root){return this.root.intervals([])}return[]}});function createWrapper(intervals){if(!intervals||intervals.length===0){return new IntervalTree(null)}return new IntervalTree(createIntervalTree(intervals))}},{"binary-search-bounds":21}],21:[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)}},{}],"bitmap-to-boxes":[function(require,module,exports){"use strict";module.exports=getBoxes;var rectangleDecomposition=require("rectangle-decomposition");var contour=require("contour-2d");var greedy=require("greedy-mesher")({extraArgs:1,order:[1,0],merge:function(a,b){return!a===!b},append:function(lo_x,lo_y,hi_x,hi_y,val,result){result.push([[lo_x,lo_y],[hi_x,hi_y]])}});function getBoxes(image,useGreedy){if(useGreedy){var result=[];greedy(image,result);return result}return rectangleDecomposition(contour(image,true))}},{"contour-2d":5,"greedy-mesher":6,"rectangle-decomposition":12}]},{},[]);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}({rbush:[function(require,module,exports){(function(){"use strict";function rbush(maxEntries,format){if(!(this instanceof rbush))return new rbush(maxEntries,format);this._maxEntries=Math.max(4,maxEntries||9);this._minEntries=Math.max(2,Math.ceil(this._maxEntries*.4));if(format){this._initFormat(format)}this.clear()}rbush.prototype={all:function(){return this._all(this.data,[])},search:function(bbox){var node=this.data,result=[],toBBox=this.toBBox;if(!intersects(bbox,node.bbox))return result;var nodesToSearch=[],i,len,child,childBBox;while(node){for(i=0,len=node.children.length;i<len;i++){child=node.children[i];childBBox=node.leaf?toBBox(child):child.bbox;if(intersects(bbox,childBBox)){if(node.leaf)result.push(child);else if(contains(bbox,childBBox))this._all(child,result);else nodesToSearch.push(child)}}node=nodesToSearch.pop()}return result},load:function(data){if(!(data&&data.length))return this;if(data.length<this._minEntries){for(var i=0,len=data.length;i<len;i++){this.insert(data[i])}return this}var node=this._build(data.slice(),0,data.length-1,0);if(!this.data.children.length){this.data=node}else if(this.data.height===node.height){this._splitRoot(this.data,node)}else{if(this.data.height<node.height){var tmpNode=this.data;this.data=node;node=tmpNode}this._insert(node,this.data.height-node.height-1,true)}return this},insert:function(item){if(item)this._insert(item,this.data.height-1);return this},clear:function(){this.data={children:[],height:1,bbox:empty(),leaf:true};return this},remove:function(item){if(!item)return this;var node=this.data,bbox=this.toBBox(item),path=[],indexes=[],i,parent,index,goingUp;while(node||path.length){if(!node){node=path.pop();parent=path[path.length-1];i=indexes.pop();goingUp=true}if(node.leaf){index=node.children.indexOf(item);if(index!==-1){node.children.splice(index,1);path.push(node);this._condense(path);return this}}if(!goingUp&&!node.leaf&&contains(node.bbox,bbox)){path.push(node);indexes.push(i);i=0;parent=node;node=node.children[0]}else if(parent){i++;node=parent.children[i];goingUp=false}else node=null}return this},toBBox:function(item){return item},compareMinX:function(a,b){return a[0]-b[0]},compareMinY:function(a,b){return a[1]-b[1]},toJSON:function(){return this.data},fromJSON:function(data){this.data=data;return this},_all:function(node,result){var nodesToSearch=[];while(node){if(node.leaf)result.push.apply(result,node.children);else nodesToSearch.push.apply(nodesToSearch,node.children);node=nodesToSearch.pop()}return result},_build:function(items,left,right,height){var N=right-left+1,M=this._maxEntries,node;if(N<=M){node={children:items.slice(left,right+1),height:1,bbox:null,leaf:true};calcBBox(node,this.toBBox);return node}if(!height){height=Math.ceil(Math.log(N)/Math.log(M));M=Math.ceil(N/Math.pow(M,height-1))}node={children:[],height:height,bbox:null};var N2=Math.ceil(N/M),N1=N2*Math.ceil(Math.sqrt(M)),i,j,right2,right3;multiSelect(items,left,right,N1,this.compareMinX);for(i=left;i<=right;i+=N1){right2=Math.min(i+N1-1,right);multiSelect(items,i,right2,N2,this.compareMinY);for(j=i;j<=right2;j+=N2){right3=Math.min(j+N2-1,right2);node.children.push(this._build(items,j,right3,height-1))}}calcBBox(node,this.toBBox);return node},_chooseSubtree:function(bbox,node,level,path){var i,len,child,targetNode,area,enlargement,minArea,minEnlargement;while(true){path.push(node);if(node.leaf||path.length-1===level)break;minArea=minEnlargement=Infinity;for(i=0,len=node.children.length;i<len;i++){child=node.children[i];area=bboxArea(child.bbox);enlargement=enlargedArea(bbox,child.bbox)-area;if(enlargement<minEnlargement){minEnlargement=enlargement;minArea=area<minArea?area:minArea;targetNode=child}else if(enlargement===minEnlargement){if(area<minArea){minArea=area;targetNode=child}}}node=targetNode}return node},_insert:function(item,level,isNode){var toBBox=this.toBBox,bbox=isNode?item.bbox:toBBox(item),insertPath=[];var node=this._chooseSubtree(bbox,this.data,level,insertPath);node.children.push(item);extend(node.bbox,bbox);while(level>=0){if(insertPath[level].children.length>this._maxEntries){this._split(insertPath,level);level--}else break}this._adjustParentBBoxes(bbox,insertPath,level)},_split:function(insertPath,level){var node=insertPath[level],M=node.children.length,m=this._minEntries;this._chooseSplitAxis(node,m,M);var newNode={children:node.children.splice(this._chooseSplitIndex(node,m,M)),height:node.height};if(node.leaf)newNode.leaf=true;calcBBox(node,this.toBBox);calcBBox(newNode,this.toBBox);if(level)insertPath[level-1].children.push(newNode);else this._splitRoot(node,newNode)},_splitRoot:function(node,newNode){this.data={children:[node,newNode],height:node.height+1};calcBBox(this.data,this.toBBox)},_chooseSplitIndex:function(node,m,M){var i,bbox1,bbox2,overlap,area,minOverlap,minArea,index;minOverlap=minArea=Infinity;for(i=m;i<=M-m;i++){bbox1=distBBox(node,0,i,this.toBBox);bbox2=distBBox(node,i,M,this.toBBox);overlap=intersectionArea(bbox1,bbox2);area=bboxArea(bbox1)+bboxArea(bbox2);if(overlap<minOverlap){minOverlap=overlap;index=i;minArea=area<minArea?area:minArea}else if(overlap===minOverlap){if(area<minArea){minArea=area;index=i}}}return index},_chooseSplitAxis:function(node,m,M){var compareMinX=node.leaf?this.compareMinX:compareNodeMinX,compareMinY=node.leaf?this.compareMinY:compareNodeMinY,xMargin=this._allDistMargin(node,m,M,compareMinX),yMargin=this._allDistMargin(node,m,M,compareMinY);if(xMargin<yMargin)node.children.sort(compareMinX)},_allDistMargin:function(node,m,M,compare){node.children.sort(compare);var toBBox=this.toBBox,leftBBox=distBBox(node,0,m,toBBox),rightBBox=distBBox(node,M-m,M,toBBox),margin=bboxMargin(leftBBox)+bboxMargin(rightBBox),i,child;for(i=m;i<M-m;i++){child=node.children[i];extend(leftBBox,node.leaf?toBBox(child):child.bbox);margin+=bboxMargin(leftBBox)}for(i=M-m-1;i>=m;i--){child=node.children[i];extend(rightBBox,node.leaf?toBBox(child):child.bbox);margin+=bboxMargin(rightBBox)}return margin},_adjustParentBBoxes:function(bbox,path,level){for(var i=level;i>=0;i--){extend(path[i].bbox,bbox)}},_condense:function(path){for(var i=path.length-1,siblings;i>=0;i--){if(path[i].children.length===0){if(i>0){siblings=path[i-1].children;siblings.splice(siblings.indexOf(path[i]),1)}else this.clear()}else calcBBox(path[i],this.toBBox)}},_initFormat:function(format){var compareArr=["return a"," - b",";"];this.compareMinX=new Function("a","b",compareArr.join(format[0]));this.compareMinY=new Function("a","b",compareArr.join(format[1])); | |
| this.toBBox=new Function("a","return [a"+format.join(", a")+"];")}};function calcBBox(node,toBBox){node.bbox=distBBox(node,0,node.children.length,toBBox)}function distBBox(node,k,p,toBBox){var bbox=empty();for(var i=k,child;i<p;i++){child=node.children[i];extend(bbox,node.leaf?toBBox(child):child.bbox)}return bbox}function empty(){return[Infinity,Infinity,-Infinity,-Infinity]}function extend(a,b){a[0]=Math.min(a[0],b[0]);a[1]=Math.min(a[1],b[1]);a[2]=Math.max(a[2],b[2]);a[3]=Math.max(a[3],b[3]);return a}function compareNodeMinX(a,b){return a.bbox[0]-b.bbox[0]}function compareNodeMinY(a,b){return a.bbox[1]-b.bbox[1]}function bboxArea(a){return(a[2]-a[0])*(a[3]-a[1])}function bboxMargin(a){return a[2]-a[0]+(a[3]-a[1])}function enlargedArea(a,b){return(Math.max(b[2],a[2])-Math.min(b[0],a[0]))*(Math.max(b[3],a[3])-Math.min(b[1],a[1]))}function intersectionArea(a,b){var minX=Math.max(a[0],b[0]),minY=Math.max(a[1],b[1]),maxX=Math.min(a[2],b[2]),maxY=Math.min(a[3],b[3]);return Math.max(0,maxX-minX)*Math.max(0,maxY-minY)}function contains(a,b){return a[0]<=b[0]&&a[1]<=b[1]&&b[2]<=a[2]&&b[3]<=a[3]}function intersects(a,b){return b[0]<=a[2]&&b[1]<=a[3]&&b[2]>=a[0]&&b[3]>=a[1]}function multiSelect(arr,left,right,n,compare){var stack=[left,right],mid;while(stack.length){right=stack.pop();left=stack.pop();if(right-left<=n)continue;mid=left+Math.ceil((right-left)/n/2)*n;select(arr,left,right,mid,compare);stack.push(left,mid,mid,right)}}function select(arr,left,right,k,compare){var n,i,z,s,sd,newLeft,newRight,t,j;while(right>left){if(right-left>600){n=right-left+1;i=k-left+1;z=Math.log(n);s=.5*Math.exp(2*z/3);sd=.5*Math.sqrt(z*s*(n-s)/n)*(i-n/2<0?-1:1);newLeft=Math.max(left,Math.floor(k-i*s/n+sd));newRight=Math.min(right,Math.floor(k+(n-i)*s/n+sd));select(arr,newLeft,newRight,k,compare)}t=arr[k];i=left;j=right;swap(arr,left,k);if(compare(arr[right],t)>0)swap(arr,left,right);while(i<j){swap(arr,i,j);i++;j--;while(compare(arr[i],t)<0)i++;while(compare(arr[j],t)>0)j--}if(compare(arr[left],t)===0)swap(arr,left,j);else{j++;swap(arr,j,right)}if(j<=k)left=j+1;if(k<=j)right=j-1}}function swap(arr,i,j){var tmp=arr[i];arr[i]=arr[j];arr[j]=tmp}if(typeof define==="function"&&define.amd)define("rbush",function(){return rbush});else if(typeof module!=="undefined")module.exports=rbush;else if(typeof self!=="undefined")self.rbush=rbush;else window.rbush=rbush})()},{}]},{},[]);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}({"binary-search-bounds":[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)}},{}]},{},[]);var mouseChange=require("mouse-change");var ndarray=require("ndarray");var getContour=require("contour-2d");var orient=require("robust-orientation")[3];var uniq=require("uniq");var makeBoxes=require("bitmap-to-boxes");var rbush=require("rbush");var bsearch=require("binary-search-bounds");var GRID_SHAPE=[32,32];var canvas=document.createElement("canvas");canvas.width=canvas.height=512;document.body.appendChild(canvas);var context=canvas.getContext("2d");var grid=ndarray(new Uint32Array(GRID_SHAPE[0]*GRID_SHAPE[1]),GRID_SHAPE);canvas.addEventListener("contextmenu",function(ev){ev.preventDefault()});var lastButton=0,fillValue=0,root=[0,0],sink=[GRID_SHAPE[0]-1,GRID_SHAPE[1]-1],lastRightClick=0;mouseChange(canvas,function(button,x,y){if(button){var width=canvas.width;var height=canvas.height;var tileX=Math.floor(width/GRID_SHAPE[0]);var tileY=Math.floor(height/GRID_SHAPE[1]);var i=Math.floor(x/tileX);var j=Math.floor(y/tileY);if(i>=0&&i<GRID_SHAPE[0]&&j>=0&&j<GRID_SHAPE[1]){if(!(lastButton&1)){fillValue=!grid.get(i,j)}if(button&1){grid.set(i,j,fillValue)}if(button&2){if(lastRightClick===0){root[0]=i;root[1]=j}else{sink[0]=i;sink[1]=j}lastRightClick^=1}}}lastButton=button});function render(){requestAnimationFrame(render);var width=canvas.width;var height=canvas.height;var tileX=Math.floor(width/GRID_SHAPE[0]);var tileY=Math.floor(height/GRID_SHAPE[1]);function drawTile(x,y){context.fillRect(x*tileX,y*tileY,tileX,tileY)}context.fillStyle="#000";context.fillRect(0,0,width,height);for(var i=0;i<GRID_SHAPE[0];++i){for(var j=0;j<GRID_SHAPE[1];++j){var cell=grid.get(i,j);if(cell===1){context.fillStyle="#fff";drawTile(i,j)}}}function drawVertex(v){context.beginPath();context.arc(v[0]*tileX,v[1]*tileY,.25*Math.min(tileX,tileY),0,2*Math.PI);context.fill()}function drawLine(a,b){context.beginPath();context.moveTo(a[0]*tileX,a[1]*tileY);context.lineTo(b[0]*tileX,b[1]*tileY);context.stroke()}function drawBox(box){drawLine([box[0],box[1]],[box[2],box[1]]);drawLine([box[0],box[3]],[box[2],box[3]]);drawLine([box[0],box[1]],[box[0],box[3]]);drawLine([box[2],box[1]],[box[2],box[3]])}var boxes=makeBoxes(grid.transpose(1,0),true).map(function(b){return[b[0][0],b[0][1],b[1][0],b[1][1]]});context.strokeStyle="rgb(0,128,128)";boxes.forEach(drawBox);var loops=getContour(grid.transpose(1,0));var corners=[];var segments=[];context.strokeStyle="#00f";loops.forEach(function(polygon){for(var i=0;i<polygon.length;++i){var a=polygon[(i+polygon.length-1)%polygon.length];var b=polygon[i];var c=polygon[(i+1)%polygon.length];drawLine(a,b);segments.push([a,b]);if(orient(a,b,c)>0){var offset=[0,0];for(var j=0;j<2;++j){if(b[j]-a[j]){offset[j]=b[j]-a[j]}else{offset[j]=b[j]-c[j]}offset[j]=b[j]+Math.min(Math.round(offset[j]/Math.abs(offset[j]))|0,0)}corners.push([b,offset])}}});function comparePair(a,b){var d=a[0]-b[0];if(d){return d}return a[1]-b[1]}function comparePoint(p,q){return comparePair(p[0],q[0])}corners.sort(comparePoint);var ptr=0;for(var i=0;i<corners.length;++i){if(i+1<corners.length){if(comparePoint(corners[i],corners[i+1])===0){i+=1;continue}}corners[ptr++]=corners[i]}corners.length=ptr;var cornerVerts=corners.map(function(c){return c[0]});var cornerTiles=uniq(corners.map(function(c){return c[1]}),comparePair,false);context.fillStyle="rgba(128, 128, 0, 0.5)";cornerTiles.forEach(function(tile){drawTile(tile[0],tile[1])});context.fillStyle="#ff0";cornerVerts.forEach(drawVertex);var rtree=rbush(9);rtree.load(boxes);function drawRay(v,x){var ray=[Math.min(v[0],x),v[1],Math.max(v[0],x),v[1]];drawLine([ray[0]+.5,ray[1]+.5],[ray[2]+.5,ray[3]+.5])}function stabTile(v){return rtree.search([v[0]+.5,v[1]+.5,v[0]+.5,v[1]+.5]).length>0}function stabRay(v,x){return rtree.search([Math.min(v[0],x)+.5,v[1]+.5,Math.max(v[0],x)+.5,v[1]+.5]).length>0}function stabBox(a,b){return rtree.search([Math.min(a[0],b[0])+.5,Math.min(a[1],b[1])+.5,Math.max(a[0],b[0])+.5,Math.max(a[1],b[1])+.5]).length>0}function makePartition(x,corners){var left=[];var right=[];var on=[];for(var i=0;i<corners.length;++i){var c=corners[i];if(!stabRay(c,x)){on.push(c)}if(c[0]<x){left.push(c)}else if(c[0]>x){right.push(c)}}on.sort(function(a,b){var d=a[1]-b[1];if(d){return d}return a[0]-b[0]});var verts=[];var edges=[];for(var i=0;i<on.length;){var l=x;var r=x;var v=on[i];var y=v[1];while(i<on.length&&on[i][1]===y&&on[i][0]<x){l=on[i++][0]}while(i<on.length&&on[i][1]===y&&on[i][0]===x){++i}if(i<on.length&&on[i][1]===y){r=on[i++][0];while(i<on.length&&on[i][1]===y){++i}}verts.push([x,y]);var e=[];if(l<x){e.push([l,y])}if(r>x){e.push([r,y])}edges.push(e)}for(var i=0;i+1<verts.length;++i){if(stabBox(verts[i],verts[i+1])){continue}edges[i].push(verts[i+1]);edges[i+1].push(verts[i])}return{x:x,left:left,right:right,verts:verts,edges:edges}}function drawPartition(partition){var x=partition.x;context.strokeStyle="#f0f";context.fillStyle="#f0f";partition.verts.forEach(function(v,i){drawVertex([v[0]+.5,v[1]+.5]);var e=partition.edges[i];for(var i=0;i<e.length;++i){drawLine([v[0]+.5,v[1]+.5],[e[i][0]+.5,e[i][1]+.5])}})}function glueVertex(tree,e,v){if(e[0]<tree.x){glueVertex(tree.left,e,v)}else if(e[0]>tree.x){glueVertex(tree.right,e,v)}else{var idx=bsearch.eq(tree.verts,e,comparePair);tree.edges[idx].push(v)}}function makeClarksonTree(corners){if(corners.length===0){return null}var x=corners[corners.length>>>1][0];var partition=makePartition(x,corners);drawPartition(partition);var leftTree=makeClarksonTree(partition.left);var rightTree=makeClarksonTree(partition.right);for(var i=0;i<partition.edges.length;++i){var v=partition.verts[i];var e=partition.edges[i];for(var j=0;j<e.length;++j){if(e[j][0]<v[0]&&leftTree){glueVertex(leftTree,e[j],v)}else if(e[j][0]>v[0]&&rightTree){glueVertex(rightTree,e[j],v)}}}return{x:x,verts:partition.verts,edges:partition.edges,left:leftTree,right:rightTree}}var tree=makeClarksonTree(cornerTiles);function addEdge(a,b){if(!stabBox(a,b)){drawLine([a[0]+.5,a[1]+.5],[b[0]+.5,a[1]+.5]);drawLine([b[0]+.5,a[1]+.5],[b[0]+.5,b[1]+.5])}}function getConnectingVerts(node,vertex){if(!node){return}var idx=bsearch.le(node.verts,vertex,function(a,b){return a[1]-vertex[1]});if(idx<0){addEdge(node.verts[0],vertex)}else if(node.verts[idx][1]===vertex[1]){addEdge(node.verts[idx],vertex)}else{addEdge(node.verts[idx],vertex);if(idx<node.verts.length-1){addEdge(node.verts[idx+1],vertex)}}if(vertex[0]<node.x){getConnectingVerts(node.left,vertex)}else if(vertex[0]>node.x){getConnectingVerts(node.right,vertex)}}context.fillStyle="#0f0";context.strokeStyle="#0f0";drawVertex([root[0]+.5,root[1]+.5]);getConnectingVerts(tree,root);addEdge(root,sink);context.fillStyle="#f00";context.strokeStyle="#f00";drawVertex([sink[0]+.5,sink[1]+.5]);getConnectingVerts(tree,sink)}render(); |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| { | |
| "name": "requirebin-sketch", | |
| "version": "1.0.0", | |
| "dependencies": { | |
| "mouse-change": "1.1.1", | |
| "ndarray": "1.0.16", | |
| "contour-2d": "1.0.0", | |
| "robust-orientation": "1.1.3", | |
| "uniq": "1.0.1", | |
| "bitmap-to-boxes": "1.0.0", | |
| "rbush": "1.3.5", | |
| "binary-search-bounds": "1.0.0" | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment