Skip to content

Instantly share code, notes, and snippets.

@scriptspry

scriptspry/pslg-to-poly.js

Forked from anonymous/-
Created March 18, 2018 17:33
Show Gist options
  • Save scriptspry/e6c6d4e8d55e791eeb8749c0871d80f8 to your computer and use it in GitHub Desktop.
Save scriptspry/e6c6d4e8d55e791eeb8749c0871d80f8 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
pslg-to-poly.js
(function(e, a) { for(var i in a) e[i] = a[i]; }(window, /******/ (function(modules) { // webpackBootstrap
/******/ // The module cache
/******/ var installedModules = {};
/******/
/******/ // The require function
/******/ function __webpack_require__(moduleId) {
/******/
/******/ // Check if module is in cache
/******/ if(installedModules[moduleId]) {
/******/ return installedModules[moduleId].exports;
/******/ }
/******/ // Create a new module (and put it into the cache)
/******/ var module = installedModules[moduleId] = {
/******/ i: moduleId,
/******/ l: false,
/******/ exports: {}
/******/ };
/******/
/******/ // Execute the module function
/******/ modules[moduleId].call(module.exports, module, module.exports, __webpack_require__);
/******/
/******/ // Flag the module as loaded
/******/ module.l = true;
/******/
/******/ // Return the exports of the module
/******/ return module.exports;
/******/ }
/******/
/******/
/******/ // expose the modules object (__webpack_modules__)
/******/ __webpack_require__.m = modules;
/******/
/******/ // expose the module cache
/******/ __webpack_require__.c = installedModules;
/******/
/******/ // define getter function for harmony exports
/******/ __webpack_require__.d = function(exports, name, getter) {
/******/ if(!__webpack_require__.o(exports, name)) {
/******/ Object.defineProperty(exports, name, {
/******/ configurable: false,
/******/ enumerable: true,
/******/ get: getter
/******/ });
/******/ }
/******/ };
/******/
/******/ // getDefaultExport function for compatibility with non-harmony modules
/******/ __webpack_require__.n = function(module) {
/******/ var getter = module && module.__esModule ?
/******/ function getDefault() { return module['default']; } :
/******/ function getModuleExports() { return module; };
/******/ __webpack_require__.d(getter, 'a', getter);
/******/ return getter;
/******/ };
/******/
/******/ // Object.prototype.hasOwnProperty.call
/******/ __webpack_require__.o = function(object, property) { return Object.prototype.hasOwnProperty.call(object, property); };
/******/
/******/ // __webpack_public_path__
/******/ __webpack_require__.p = "";
/******/
/******/ // Load entry module and return exports
/******/ return __webpack_require__(__webpack_require__.s = 7);
/******/ })
/************************************************************************/
/******/ ([
/* 0 */
/***/ (function(module, exports, __webpack_require__) {
"use strict";
function compileSearch(funcName, predicate, reversed, extraArgs, 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[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"], earlyOut),
compileSearch("P", "c(x,y)" + predicate + "0", reversed, ["y", "c"], earlyOut),
"function dispatchBsearch", suffix, "(a,y,c,l,h){\
if(typeof(c)==='function'){\
return P(a,(l===void 0)?0:l|0,(h===void 0)?a.length-1:h|0,y,c)\
}else{\
return A(a,(c===void 0)?0:c|0,(l===void 0)?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)
}
/***/ }),
/* 1 */
/***/ (function(module, exports, __webpack_require__) {
"use strict";
module.exports = twoProduct
var SPLITTER = +(Math.pow(2, 27) + 1.0)
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 ]
}
/***/ }),
/* 2 */
/***/ (function(module, exports, __webpack_require__) {
"use strict";
module.exports = linearExpansionSum
//Easy case: Add two scalars
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.0
}
g.length = count
return g
}
/***/ }),
/* 3 */
/***/ (function(module, exports, __webpack_require__) {
"use strict";
var twoProduct = __webpack_require__(1)
var twoSum = __webpack_require__(12)
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 = [0.1, 0.1]
var t = [0.1, 0.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.0
}
g.length = count
return g
}
/***/ }),
/* 4 */
/***/ (function(module, exports, __webpack_require__) {
"use strict";
module.exports = robustSubtract
//Easy case: Add two scalars
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.0
}
g.length = count
return g
}
/***/ }),
/* 5 */
/***/ (function(module, exports) {
module.exports = compareCells
var min = Math.min
function compareInt(a, b) {
return a - b
}
function compareCells(a, b) {
var n = a.length
, t = a.length - b.length
if(t) {
return t
}
switch(n) {
case 0:
return 0
case 1:
return a[0] - b[0]
case 2:
return (a[0]+a[1]-b[0]-b[1]) ||
min(a[0],a[1]) - min(b[0],b[1])
case 3:
var l1 = a[0]+a[1]
, m1 = b[0]+b[1]
t = l1+a[2] - (m1+b[2])
if(t) {
return t
}
var l0 = min(a[0], a[1])
, m0 = min(b[0], b[1])
return min(l0, a[2]) - min(m0, b[2]) ||
min(l0+a[2], l1) - min(m0+b[2], m1)
case 4:
var aw=a[0], ax=a[1], ay=a[2], az=a[3]
, bw=b[0], bx=b[1], by=b[2], bz=b[3]
return (aw+ax+ay+az)-(bw+bx+by+bz) ||
min(aw,ax,ay,az)-min(bw,bx,by,bz,bw) ||
min(aw+ax,aw+ay,aw+az,ax+ay,ax+az,ay+az) -
min(bw+bx,bw+by,bw+bz,bx+by,bx+bz,by+bz) ||
min(aw+ax+ay,aw+ax+az,aw+ay+az,ax+ay+az) -
min(bw+bx+by,bw+bx+bz,bw+by+bz,bx+by+bz)
default:
var as = a.slice().sort(compareInt)
var bs = b.slice().sort(compareInt)
for(var i=0; i<n; ++i) {
t = as[i] - bs[i]
if(t) {
return t
}
}
return 0
}
}
/***/ }),
/* 6 */
/***/ (function(module, exports, __webpack_require__) {
"use strict";
module.exports = orientation
function orientation(s) {
var p = 1
for(var i=1; i<s.length; ++i) {
for(var j=0; j<i; ++j) {
if(s[i] < s[j]) {
p = -p
} else if(s[j] === s[i]) {
return 0
}
}
}
return p
}
/***/ }),
/* 7 */
/***/ (function(module, __webpack_exports__, __webpack_require__) {
"use strict";
Object.defineProperty(__webpack_exports__, "__esModule", { value: true });
const pslg2poly = __webpack_require__(8)
/* harmony export (immutable) */ __webpack_exports__["pslg2poly"] = pslg2poly;
/***/ }),
/* 8 */
/***/ (function(module, exports, __webpack_require__) {
"use strict";
var cdt2d = __webpack_require__(9)
var boundary = __webpack_require__(17)
module.exports = pslgToPolygon
function pslgToPolygon(points, edges) {
//Get cells
var cells = cdt2d(points, edges, {
delaunay: false,
exterior: false })
//Extract boundary
var bnd = boundary(cells)
//Construct adjacency list from boundary
var adj = new Array(points.length)
for(var i=0; i<points.length; ++i) {
adj[i] = []
}
for(var i=0; i<bnd.length; ++i) {
var e = bnd[i]
adj[e[0]].push(e[1])
}
//Extract boundary cycle
var loops = []
for(var i=0; i<points.length; ++i) {
if(adj[i].length === 0) {
continue
}
var v = i, loop = []
do {
loop.push(points[v])
v = adj[v].pop()
} while(v !== i)
loops.push(loop)
}
return loops
}
/***/ }),
/* 9 */
/***/ (function(module, exports, __webpack_require__) {
"use strict";
var monotoneTriangulate = __webpack_require__(10)
var makeIndex = __webpack_require__(13)
var delaunayFlip = __webpack_require__(14)
var filterTriangulation = __webpack_require__(16)
module.exports = cdt2d
function canonicalizeEdge(e) {
return [Math.min(e[0], e[1]), Math.max(e[0], e[1])]
}
function compareEdge(a, b) {
return a[0]-b[0] || a[1]-b[1]
}
function canonicalizeEdges(edges) {
return edges.map(canonicalizeEdge).sort(compareEdge)
}
function getDefault(options, property, dflt) {
if(property in options) {
return options[property]
}
return dflt
}
function cdt2d(points, edges, options) {
if(!Array.isArray(edges)) {
options = edges || {}
edges = []
} else {
options = options || {}
edges = edges || []
}
//Parse out options
var delaunay = !!getDefault(options, 'delaunay', true)
var interior = !!getDefault(options, 'interior', true)
var exterior = !!getDefault(options, 'exterior', true)
var infinity = !!getDefault(options, 'infinity', false)
//Handle trivial case
if((!interior && !exterior) || points.length === 0) {
return []
}
//Construct initial triangulation
var cells = monotoneTriangulate(points, edges)
//If delaunay refinement needed, then improve quality by edge flipping
if(delaunay || interior !== exterior || infinity) {
//Index all of the cells to support fast neighborhood queries
var triangulation = makeIndex(points.length, canonicalizeEdges(edges))
for(var i=0; i<cells.length; ++i) {
var f = cells[i]
triangulation.addTriangle(f[0], f[1], f[2])
}
//Run edge flipping
if(delaunay) {
delaunayFlip(points, triangulation)
}
//Filter points
if(!exterior) {
return filterTriangulation(triangulation, -1)
} else if(!interior) {
return filterTriangulation(triangulation, 1, infinity)
} else if(infinity) {
return filterTriangulation(triangulation, 0, infinity)
} else {
return triangulation.cells()
}
} else {
return cells
}
}
/***/ }),
/* 10 */
/***/ (function(module, exports, __webpack_require__) {
"use strict";
var bsearch = __webpack_require__(0)
var orient = __webpack_require__(11)[3]
var EVENT_POINT = 0
var EVENT_END = 1
var EVENT_START = 2
module.exports = monotoneTriangulate
//A partial convex hull fragment, made of two unimonotone polygons
function PartialHull(a, b, idx, lowerIds, upperIds) {
this.a = a
this.b = b
this.idx = idx
this.lowerIds = lowerIds
this.upperIds = upperIds
}
//An event in the sweep line procedure
function Event(a, b, type, idx) {
this.a = a
this.b = b
this.type = type
this.idx = idx
}
//This is used to compare events for the sweep line procedure
// Points are:
// 1. sorted lexicographically
// 2. sorted by type (point < end < start)
// 3. segments sorted by winding order
// 4. sorted by index
function compareEvent(a, b) {
var d =
(a.a[0] - b.a[0]) ||
(a.a[1] - b.a[1]) ||
(a.type - b.type)
if(d) { return d }
if(a.type !== EVENT_POINT) {
d = orient(a.a, a.b, b.b)
if(d) { return d }
}
return a.idx - b.idx
}
function testPoint(hull, p) {
return orient(hull.a, hull.b, p)
}
function addPoint(cells, hulls, points, p, idx) {
var lo = bsearch.lt(hulls, p, testPoint)
var hi = bsearch.gt(hulls, p, testPoint)
for(var i=lo; i<hi; ++i) {
var hull = hulls[i]
//Insert p into lower hull
var lowerIds = hull.lowerIds
var m = lowerIds.length
while(m > 1 && orient(
points[lowerIds[m-2]],
points[lowerIds[m-1]],
p) > 0) {
cells.push(
[lowerIds[m-1],
lowerIds[m-2],
idx])
m -= 1
}
lowerIds.length = m
lowerIds.push(idx)
//Insert p into upper hull
var upperIds = hull.upperIds
var m = upperIds.length
while(m > 1 && orient(
points[upperIds[m-2]],
points[upperIds[m-1]],
p) < 0) {
cells.push(
[upperIds[m-2],
upperIds[m-1],
idx])
m -= 1
}
upperIds.length = m
upperIds.push(idx)
}
}
function findSplit(hull, edge) {
var d
if(hull.a[0] < edge.a[0]) {
d = orient(hull.a, hull.b, edge.a)
} else {
d = orient(edge.b, edge.a, hull.a)
}
if(d) { return d }
if(edge.b[0] < hull.b[0]) {
d = orient(hull.a, hull.b, edge.b)
} else {
d = orient(edge.b, edge.a, hull.b)
}
return d || hull.idx - edge.idx
}
function splitHulls(hulls, points, event) {
var splitIdx = bsearch.le(hulls, event, findSplit)
var hull = hulls[splitIdx]
var upperIds = hull.upperIds
var x = upperIds[upperIds.length-1]
hull.upperIds = [x]
hulls.splice(splitIdx+1, 0,
new PartialHull(event.a, event.b, event.idx, [x], upperIds))
}
function mergeHulls(hulls, points, event) {
//Swap pointers for merge search
var tmp = event.a
event.a = event.b
event.b = tmp
var mergeIdx = bsearch.eq(hulls, event, findSplit)
var upper = hulls[mergeIdx]
var lower = hulls[mergeIdx-1]
lower.upperIds = upper.upperIds
hulls.splice(mergeIdx, 1)
}
function monotoneTriangulate(points, edges) {
var numPoints = points.length
var numEdges = edges.length
var events = []
//Create point events
for(var i=0; i<numPoints; ++i) {
events.push(new Event(
points[i],
null,
EVENT_POINT,
i))
}
//Create edge events
for(var i=0; i<numEdges; ++i) {
var e = edges[i]
var a = points[e[0]]
var b = points[e[1]]
if(a[0] < b[0]) {
events.push(
new Event(a, b, EVENT_START, i),
new Event(b, a, EVENT_END, i))
} else if(a[0] > b[0]) {
events.push(
new Event(b, a, EVENT_START, i),
new Event(a, b, EVENT_END, i))
}
}
//Sort events
events.sort(compareEvent)
//Initialize hull
var minX = events[0].a[0] - (1 + Math.abs(events[0].a[0])) * Math.pow(2, -52)
var hull = [ new PartialHull([minX, 1], [minX, 0], -1, [], [], [], []) ]
//Process events in order
var cells = []
for(var i=0, numEvents=events.length; i<numEvents; ++i) {
var event = events[i]
var type = event.type
if(type === EVENT_POINT) {
addPoint(cells, hull, points, event.a, event.idx)
} else if(type === EVENT_START) {
splitHulls(hull, points, event)
} else {
mergeHulls(hull, points, event)
}
}
//Return triangulation
return cells
}
/***/ }),
/* 11 */
/***/ (function(module, exports, __webpack_require__) {
"use strict";
var twoProduct = __webpack_require__(1)
var robustSum = __webpack_require__(2)
var robustScale = __webpack_require__(3)
var robustSubtract = __webpack_require__(4)
var NUM_EXPAND = 5
var EPSILON = 1.1102230246251565e-16
var ERRBOUND3 = (3.0 + 16.0 * EPSILON) * EPSILON
var ERRBOUND4 = (7.0 + 56.0 * 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()
/***/ }),
/* 12 */
/***/ (function(module, exports, __webpack_require__) {
"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]
}
/***/ }),
/* 13 */
/***/ (function(module, exports, __webpack_require__) {
"use strict";
var bsearch = __webpack_require__(0)
module.exports = createTriangulation
function Triangulation(stars, edges) {
this.stars = stars
this.edges = edges
}
var proto = Triangulation.prototype
function removePair(list, j, k) {
for(var i=1, n=list.length; i<n; i+=2) {
if(list[i-1] === j && list[i] === k) {
list[i-1] = list[n-2]
list[i] = list[n-1]
list.length = n - 2
return
}
}
}
proto.isConstraint = (function() {
var e = [0,0]
function compareLex(a, b) {
return a[0] - b[0] || a[1] - b[1]
}
return function(i, j) {
e[0] = Math.min(i,j)
e[1] = Math.max(i,j)
return bsearch.eq(this.edges, e, compareLex) >= 0
}
})()
proto.removeTriangle = function(i, j, k) {
var stars = this.stars
removePair(stars[i], j, k)
removePair(stars[j], k, i)
removePair(stars[k], i, j)
}
proto.addTriangle = function(i, j, k) {
var stars = this.stars
stars[i].push(j, k)
stars[j].push(k, i)
stars[k].push(i, j)
}
proto.opposite = function(j, i) {
var list = this.stars[i]
for(var k=1, n=list.length; k<n; k+=2) {
if(list[k] === j) {
return list[k-1]
}
}
return -1
}
proto.flip = function(i, j) {
var a = this.opposite(i, j)
var b = this.opposite(j, i)
this.removeTriangle(i, j, a)
this.removeTriangle(j, i, b)
this.addTriangle(i, b, a)
this.addTriangle(j, a, b)
}
proto.edges = function() {
var stars = this.stars
var result = []
for(var i=0, n=stars.length; i<n; ++i) {
var list = stars[i]
for(var j=0, m=list.length; j<m; j+=2) {
result.push([list[j], list[j+1]])
}
}
return result
}
proto.cells = function() {
var stars = this.stars
var result = []
for(var i=0, n=stars.length; i<n; ++i) {
var list = stars[i]
for(var j=0, m=list.length; j<m; j+=2) {
var s = list[j]
var t = list[j+1]
if(i < Math.min(s, t)) {
result.push([i, s, t])
}
}
}
return result
}
function createTriangulation(numVerts, edges) {
var stars = new Array(numVerts)
for(var i=0; i<numVerts; ++i) {
stars[i] = []
}
return new Triangulation(stars, edges)
}
/***/ }),
/* 14 */
/***/ (function(module, exports, __webpack_require__) {
"use strict";
var inCircle = __webpack_require__(15)[4]
var bsearch = __webpack_require__(0)
module.exports = delaunayRefine
function testFlip(points, triangulation, stack, a, b, x) {
var y = triangulation.opposite(a, b)
//Test boundary edge
if(y < 0) {
return
}
//Swap edge if order flipped
if(b < a) {
var tmp = a
a = b
b = tmp
tmp = x
x = y
y = tmp
}
//Test if edge is constrained
if(triangulation.isConstraint(a, b)) {
return
}
//Test if edge is delaunay
if(inCircle(points[a], points[b], points[x], points[y]) < 0) {
stack.push(a, b)
}
}
//Assume edges are sorted lexicographically
function delaunayRefine(points, triangulation) {
var stack = []
var numPoints = points.length
var stars = triangulation.stars
for(var a=0; a<numPoints; ++a) {
var star = stars[a]
for(var j=1; j<star.length; j+=2) {
var b = star[j]
//If order is not consistent, then skip edge
if(b < a) {
continue
}
//Check if edge is constrained
if(triangulation.isConstraint(a, b)) {
continue
}
//Find opposite edge
var x = star[j-1], y = -1
for(var k=1; k<star.length; k+=2) {
if(star[k-1] === b) {
y = star[k]
break
}
}
//If this is a boundary edge, don't flip it
if(y < 0) {
continue
}
//If edge is in circle, flip it
if(inCircle(points[a], points[b], points[x], points[y]) < 0) {
stack.push(a, b)
}
}
}
while(stack.length > 0) {
var b = stack.pop()
var a = stack.pop()
//Find opposite pairs
var x = -1, y = -1
var star = stars[a]
for(var i=1; i<star.length; i+=2) {
var s = star[i-1]
var t = star[i]
if(s === b) {
y = t
} else if(t === b) {
x = s
}
}
//If x/y are both valid then skip edge
if(x < 0 || y < 0) {
continue
}
//If edge is now delaunay, then don't flip it
if(inCircle(points[a], points[b], points[x], points[y]) >= 0) {
continue
}
//Flip the edge
triangulation.flip(a, b)
//Test flipping neighboring edges
testFlip(points, triangulation, stack, x, a, y)
testFlip(points, triangulation, stack, a, y, x)
testFlip(points, triangulation, stack, y, b, x)
testFlip(points, triangulation, stack, b, x, y)
}
}
/***/ }),
/* 15 */
/***/ (function(module, exports, __webpack_require__) {
"use strict";
var twoProduct = __webpack_require__(1)
var robustSum = __webpack_require__(2)
var robustDiff = __webpack_require__(4)
var robustScale = __webpack_require__(3)
var NUM_EXPAND = 6
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-2), "]"].join("")
}
}
return result
}
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 makeProduct(a, b) {
if(a.charAt(0) === "m") {
if(b.charAt(0) === "w") {
var toks = a.split("[")
return ["w", b.substr(1), "m", toks[0].substr(1)].join("")
} else {
return ["prod(", a, ",", b, ")"].join("")
}
} else {
return makeProduct(b, a)
}
}
function sign(s) {
if(s & 1 !== 0) {
return "-"
}
return ""
}
function determinant(m) {
if(m.length === 2) {
return [["diff(", makeProduct(m[0][0], m[1][1]), ",", makeProduct(m[1][0], m[0][1]), ")"].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 makeSquare(d, n) {
var terms = []
for(var i=0; i<n-2; ++i) {
terms.push(["prod(m", d, "[", i, "],m", d, "[", i, "])"].join(""))
}
return generateSum(terms)
}
function orientation(n) {
var pos = []
var neg = []
var m = matrix(n)
for(var i=0; i<n; ++i) {
m[0][i] = "1"
m[n-1][i] = "w"+i
}
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)))
}
}
var posExpr = generateSum(pos)
var negExpr = generateSum(neg)
var funcName = "exactInSphere" + n
var funcArgs = []
for(var i=0; i<n; ++i) {
funcArgs.push("m" + i)
}
var code = ["function ", funcName, "(", funcArgs.join(), "){"]
for(var i=0; i<n; ++i) {
code.push("var w",i,"=",makeSquare(i,n),";")
for(var j=0; j<n; ++j) {
if(j !== i) {
code.push("var w",i,"m",j,"=scale(w",i,",m",j,"[0]);")
}
}
}
code.push("var p=", posExpr, ",n=", negExpr, ",d=diff(p,n);return d[d.length-1];}return ", funcName)
var proc = new Function("sum", "diff", "prod", "scale", code.join(""))
return proc(robustSum, robustDiff, twoProduct, robustScale)
}
function inSphere0() { return 0 }
function inSphere1() { return 0 }
function inSphere2() { return 0 }
var CACHED = [
inSphere0,
inSphere1,
inSphere2
]
function slowInSphere(args) {
var proc = CACHED[args.length]
if(!proc) {
proc = CACHED[args.length] = orientation(args.length)
}
return proc.apply(undefined, args)
}
function generateInSphereTest() {
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 testInSphere(", 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 testInSphere")
procArgs.push(code.join(""))
var proc = Function.apply(undefined, procArgs)
module.exports = proc.apply(undefined, [slowInSphere].concat(CACHED))
for(var i=0; i<=NUM_EXPAND; ++i) {
module.exports[i] = CACHED[i]
}
}
generateInSphereTest()
/***/ }),
/* 16 */
/***/ (function(module, exports, __webpack_require__) {
"use strict";
var bsearch = __webpack_require__(0)
module.exports = classifyFaces
function FaceIndex(cells, neighbor, constraint, flags, active, next, boundary) {
this.cells = cells
this.neighbor = neighbor
this.flags = flags
this.constraint = constraint
this.active = active
this.next = next
this.boundary = boundary
}
var proto = FaceIndex.prototype
function compareCell(a, b) {
return a[0] - b[0] ||
a[1] - b[1] ||
a[2] - b[2]
}
proto.locate = (function() {
var key = [0,0,0]
return function(a, b, c) {
var x = a, y = b, z = c
if(b < c) {
if(b < a) {
x = b
y = c
z = a
}
} else if(c < a) {
x = c
y = a
z = b
}
if(x < 0) {
return -1
}
key[0] = x
key[1] = y
key[2] = z
return bsearch.eq(this.cells, key, compareCell)
}
})()
function indexCells(triangulation, infinity) {
//First get cells and canonicalize
var cells = triangulation.cells()
var nc = cells.length
for(var i=0; i<nc; ++i) {
var c = cells[i]
var x = c[0], y = c[1], z = c[2]
if(y < z) {
if(y < x) {
c[0] = y
c[1] = z
c[2] = x
}
} else if(z < x) {
c[0] = z
c[1] = x
c[2] = y
}
}
cells.sort(compareCell)
//Initialize flag array
var flags = new Array(nc)
for(var i=0; i<flags.length; ++i) {
flags[i] = 0
}
//Build neighbor index, initialize queues
var active = []
var next = []
var neighbor = new Array(3*nc)
var constraint = new Array(3*nc)
var boundary = null
if(infinity) {
boundary = []
}
var index = new FaceIndex(
cells,
neighbor,
constraint,
flags,
active,
next,
boundary)
for(var i=0; i<nc; ++i) {
var c = cells[i]
for(var j=0; j<3; ++j) {
var x = c[j], y = c[(j+1)%3]
var a = neighbor[3*i+j] = index.locate(y, x, triangulation.opposite(y, x))
var b = constraint[3*i+j] = triangulation.isConstraint(x, y)
if(a < 0) {
if(b) {
next.push(i)
} else {
active.push(i)
flags[i] = 1
}
if(infinity) {
boundary.push([y, x, -1])
}
}
}
}
return index
}
function filterCells(cells, flags, target) {
var ptr = 0
for(var i=0; i<cells.length; ++i) {
if(flags[i] === target) {
cells[ptr++] = cells[i]
}
}
cells.length = ptr
return cells
}
function classifyFaces(triangulation, target, infinity) {
var index = indexCells(triangulation, infinity)
if(target === 0) {
if(infinity) {
return index.cells.concat(index.boundary)
} else {
return index.cells
}
}
var side = 1
var active = index.active
var next = index.next
var flags = index.flags
var cells = index.cells
var constraint = index.constraint
var neighbor = index.neighbor
while(active.length > 0 || next.length > 0) {
while(active.length > 0) {
var t = active.pop()
if(flags[t] === -side) {
continue
}
flags[t] = side
var c = cells[t]
for(var j=0; j<3; ++j) {
var f = neighbor[3*t+j]
if(f >= 0 && flags[f] === 0) {
if(constraint[3*t+j]) {
next.push(f)
} else {
active.push(f)
flags[f] = side
}
}
}
}
//Swap arrays and loop
var tmp = next
next = active
active = tmp
next.length = 0
side = -side
}
var result = filterCells(cells, flags, target)
if(infinity) {
return result.concat(index.boundary)
}
return result
}
/***/ }),
/* 17 */
/***/ (function(module, exports, __webpack_require__) {
"use strict";
module.exports = boundary
var bnd = __webpack_require__(18)
var reduce = __webpack_require__(19)
function boundary(cells) {
return reduce(bnd(cells))
}
/***/ }),
/* 18 */
/***/ (function(module, exports, __webpack_require__) {
"use strict";
module.exports = boundary
function boundary (cells) {
var i, j, k
var n = cells.length
var sz = 0
for (i = 0; i < n; ++i) {
sz += cells[i].length
}
var result = new Array(sz)
var ptr = 0
for (i = 0; i < n; ++i) {
var c = cells[i]
var d = c.length
for (j = 0; j < d; ++j) {
var b = result[ptr++] = new Array(d - 1)
var p = 0
for (k = 0; k < d; ++k) {
if (k === j) {
continue
}
b[p++] = c[k]
}
if (j & 1) {
var tmp = b[1]
b[1] = b[0]
b[0] = tmp
}
}
}
return result
}
/***/ }),
/* 19 */
/***/ (function(module, exports, __webpack_require__) {
"use strict";
var compareCell = __webpack_require__(5)
var compareOrientedCell = __webpack_require__(20)
var orientation = __webpack_require__(6)
module.exports = reduceCellComplex
function reduceCellComplex(cells) {
cells.sort(compareOrientedCell)
var n = cells.length
var ptr = 0
for(var i=0; i<n; ++i) {
var c = cells[i]
var o = orientation(c)
if(o === 0) {
continue
}
if(ptr > 0) {
var f = cells[ptr-1]
if(compareCell(c, f) === 0 &&
orientation(f) !== o) {
ptr -= 1
continue
}
}
cells[ptr++] = c
}
cells.length = ptr
return cells
}
/***/ }),
/* 20 */
/***/ (function(module, exports, __webpack_require__) {
"use strict";
var compareCells = __webpack_require__(5)
var parity = __webpack_require__(6)
module.exports = compareOrientedCells
function compareOrientedCells(a, b) {
return compareCells(a, b) || parity(a) - parity(b)
}
/***/ })
/******/ ])));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment