// polyclip-ts v0.16.8 Copyright (c) 2022 Luiz Felipe Machado Barboza (function (global, factory) { typeof exports === 'object' && typeof module !== 'undefined' ? factory(exports) : typeof define === 'function' && define.amd ? define(['exports'], factory) : (global = typeof globalThis !== 'undefined' ? globalThis : global || self, factory(global.polyclip = global.polyclip || {})); })(this, (function (exports) { 'use strict'; var version = "0.16.8"; var constant = (x) => { return () => { return x; }; }; var compare$1 = (eps) => { const almostEqual = eps ? (a, b) => b.minus(a).abs().isLessThanOrEqualTo(eps) : constant(false); return (a, b) => { if (almostEqual(a, b)) return 0; return a.comparedTo(b); }; }; function orient (eps) { const almostCollinear = eps ? (area2, ax, ay, cx, cy) => area2.exponentiatedBy(2).isLessThanOrEqualTo(cx.minus(ax).exponentiatedBy(2).plus(cy.minus(ay).exponentiatedBy(2)) .times(eps)) : constant(false); return (a, b, c) => { const ax = a.x, ay = a.y, cx = c.x, cy = c.y; const area2 = ay.minus(cy).times(b.x.minus(cx)).minus(ax.minus(cx).times(b.y.minus(cy))); if (almostCollinear(area2, ax, ay, cx, cy)) return 0; return area2.comparedTo(0); }; } /* * bignumber.js v9.1.0 * A JavaScript library for arbitrary-precision arithmetic. * https://github.com/MikeMcl/bignumber.js * Copyright (c) 2022 Michael Mclaughlin * MIT Licensed. * * BigNumber.prototype methods | BigNumber methods * | * absoluteValue abs | clone * comparedTo | config set * decimalPlaces dp | DECIMAL_PLACES * dividedBy div | ROUNDING_MODE * dividedToIntegerBy idiv | EXPONENTIAL_AT * exponentiatedBy pow | RANGE * integerValue | CRYPTO * isEqualTo eq | MODULO_MODE * isFinite | POW_PRECISION * isGreaterThan gt | FORMAT * isGreaterThanOrEqualTo gte | ALPHABET * isInteger | isBigNumber * isLessThan lt | maximum max * isLessThanOrEqualTo lte | minimum min * isNaN | random * isNegative | sum * isPositive | * isZero | * minus | * modulo mod | * multipliedBy times | * negated | * plus | * precision sd | * shiftedBy | * squareRoot sqrt | * toExponential | * toFixed | * toFormat | * toFraction | * toJSON | * toNumber | * toPrecision | * toString | * valueOf | * */ var isNumeric = /^-?(?:\d+(?:\.\d*)?|\.\d+)(?:e[+-]?\d+)?$/i, mathceil = Math.ceil, mathfloor = Math.floor, bignumberError = '[BigNumber Error] ', tooManyDigits = bignumberError + 'Number primitive has more than 15 significant digits: ', BASE = 1e14, LOG_BASE = 14, MAX_SAFE_INTEGER = 0x1fffffffffffff, // 2^53 - 1 // MAX_INT32 = 0x7fffffff, // 2^31 - 1 POWS_TEN = [1, 10, 100, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9, 1e10, 1e11, 1e12, 1e13], SQRT_BASE = 1e7, // EDITABLE // The limit on the value of DECIMAL_PLACES, TO_EXP_NEG, TO_EXP_POS, MIN_EXP, MAX_EXP, and // the arguments to toExponential, toFixed, toFormat, and toPrecision. MAX = 1E9; // 0 to MAX_INT32 /* * Create and return a BigNumber constructor. */ function clone(configObject) { var div, convertBase, parseNumeric, P = BigNumber.prototype = { constructor: BigNumber, toString: null, valueOf: null }, ONE = new BigNumber(1), //----------------------------- EDITABLE CONFIG DEFAULTS ------------------------------- // The default values below must be integers within the inclusive ranges stated. // The values can also be changed at run-time using BigNumber.set. // The maximum number of decimal places for operations involving division. DECIMAL_PLACES = 20, // 0 to MAX // The rounding mode used when rounding to the above decimal places, and when using // toExponential, toFixed, toFormat and toPrecision, and round (default value). // UP 0 Away from zero. // DOWN 1 Towards zero. // CEIL 2 Towards +Infinity. // FLOOR 3 Towards -Infinity. // HALF_UP 4 Towards nearest neighbour. If equidistant, up. // HALF_DOWN 5 Towards nearest neighbour. If equidistant, down. // HALF_EVEN 6 Towards nearest neighbour. If equidistant, towards even neighbour. // HALF_CEIL 7 Towards nearest neighbour. If equidistant, towards +Infinity. // HALF_FLOOR 8 Towards nearest neighbour. If equidistant, towards -Infinity. ROUNDING_MODE = 4, // 0 to 8 // EXPONENTIAL_AT : [TO_EXP_NEG , TO_EXP_POS] // The exponent value at and beneath which toString returns exponential notation. // Number type: -7 TO_EXP_NEG = -7, // 0 to -MAX // The exponent value at and above which toString returns exponential notation. // Number type: 21 TO_EXP_POS = 21, // 0 to MAX // RANGE : [MIN_EXP, MAX_EXP] // The minimum exponent value, beneath which underflow to zero occurs. // Number type: -324 (5e-324) MIN_EXP = -1e7, // -1 to -MAX // The maximum exponent value, above which overflow to Infinity occurs. // Number type: 308 (1.7976931348623157e+308) // For MAX_EXP > 1e7, e.g. new BigNumber('1e100000000').plus(1) may be slow. MAX_EXP = 1e7, // 1 to MAX // Whether to use cryptographically-secure random number generation, if available. CRYPTO = false, // true or false // The modulo mode used when calculating the modulus: a mod n. // The quotient (q = a / n) is calculated according to the corresponding rounding mode. // The remainder (r) is calculated as: r = a - n * q. // // UP 0 The remainder is positive if the dividend is negative, else is negative. // DOWN 1 The remainder has the same sign as the dividend. // This modulo mode is commonly known as 'truncated division' and is // equivalent to (a % n) in JavaScript. // FLOOR 3 The remainder has the same sign as the divisor (Python %). // HALF_EVEN 6 This modulo mode implements the IEEE 754 remainder function. // EUCLID 9 Euclidian division. q = sign(n) * floor(a / abs(n)). // The remainder is always positive. // // The truncated division, floored division, Euclidian division and IEEE 754 remainder // modes are commonly used for the modulus operation. // Although the other rounding modes can also be used, they may not give useful results. MODULO_MODE = 1, // 0 to 9 // The maximum number of significant digits of the result of the exponentiatedBy operation. // If POW_PRECISION is 0, there will be unlimited significant digits. POW_PRECISION = 0, // 0 to MAX // The format specification used by the BigNumber.prototype.toFormat method. FORMAT = { prefix: '', groupSize: 3, secondaryGroupSize: 0, groupSeparator: ',', decimalSeparator: '.', fractionGroupSize: 0, fractionGroupSeparator: '\xA0', // non-breaking space suffix: '' }, // The alphabet used for base conversion. It must be at least 2 characters long, with no '+', // '-', '.', whitespace, or repeated character. // '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ$_' ALPHABET = '0123456789abcdefghijklmnopqrstuvwxyz', alphabetHasNormalDecimalDigits = true; //------------------------------------------------------------------------------------------ // CONSTRUCTOR /* * The BigNumber constructor and exported function. * Create and return a new instance of a BigNumber object. * * v {number|string|BigNumber} A numeric value. * [b] {number} The base of v. Integer, 2 to ALPHABET.length inclusive. */ function BigNumber(v, b) { var alphabet, c, caseChanged, e, i, isNum, len, str, x = this; // Enable constructor call without `new`. if (!(x instanceof BigNumber)) return new BigNumber(v, b); if (b == null) { if (v && v._isBigNumber === true) { x.s = v.s; if (!v.c || v.e > MAX_EXP) { x.c = x.e = null; } else if (v.e < MIN_EXP) { x.c = [x.e = 0]; } else { x.e = v.e; x.c = v.c.slice(); } return; } if ((isNum = typeof v == 'number') && v * 0 == 0) { // Use `1 / n` to handle minus zero also. x.s = 1 / v < 0 ? (v = -v, -1) : 1; // Fast path for integers, where n < 2147483648 (2**31). if (v === ~~v) { for (e = 0, i = v; i >= 10; i /= 10, e++); if (e > MAX_EXP) { x.c = x.e = null; } else { x.e = e; x.c = [v]; } return; } str = String(v); } else { if (!isNumeric.test(str = String(v))) return parseNumeric(x, str, isNum); x.s = str.charCodeAt(0) == 45 ? (str = str.slice(1), -1) : 1; } // Decimal point? if ((e = str.indexOf('.')) > -1) str = str.replace('.', ''); // Exponential form? if ((i = str.search(/e/i)) > 0) { // Determine exponent. if (e < 0) e = i; e += +str.slice(i + 1); str = str.substring(0, i); } else if (e < 0) { // Integer. e = str.length; } } else { // '[BigNumber Error] Base {not a primitive number|not an integer|out of range}: {b}' intCheck(b, 2, ALPHABET.length, 'Base'); // Allow exponential notation to be used with base 10 argument, while // also rounding to DECIMAL_PLACES as with other bases. if (b == 10 && alphabetHasNormalDecimalDigits) { x = new BigNumber(v); return round(x, DECIMAL_PLACES + x.e + 1, ROUNDING_MODE); } str = String(v); if (isNum = typeof v == 'number') { // Avoid potential interpretation of Infinity and NaN as base 44+ values. if (v * 0 != 0) return parseNumeric(x, str, isNum, b); x.s = 1 / v < 0 ? (str = str.slice(1), -1) : 1; // '[BigNumber Error] Number primitive has more than 15 significant digits: {n}' if (BigNumber.DEBUG && str.replace(/^0\.0*|\./, '').length > 15) { throw Error (tooManyDigits + v); } } else { x.s = str.charCodeAt(0) === 45 ? (str = str.slice(1), -1) : 1; } alphabet = ALPHABET.slice(0, b); e = i = 0; // Check that str is a valid base b number. // Don't use RegExp, so alphabet can contain special characters. for (len = str.length; i < len; i++) { if (alphabet.indexOf(c = str.charAt(i)) < 0) { if (c == '.') { // If '.' is not the first character and it has not be found before. if (i > e) { e = len; continue; } } else if (!caseChanged) { // Allow e.g. hexadecimal 'FF' as well as 'ff'. if (str == str.toUpperCase() && (str = str.toLowerCase()) || str == str.toLowerCase() && (str = str.toUpperCase())) { caseChanged = true; i = -1; e = 0; continue; } } return parseNumeric(x, String(v), isNum, b); } } // Prevent later check for length on converted number. isNum = false; str = convertBase(str, b, 10, x.s); // Decimal point? if ((e = str.indexOf('.')) > -1) str = str.replace('.', ''); else e = str.length; } // Determine leading zeros. for (i = 0; str.charCodeAt(i) === 48; i++); // Determine trailing zeros. for (len = str.length; str.charCodeAt(--len) === 48;); if (str = str.slice(i, ++len)) { len -= i; // '[BigNumber Error] Number primitive has more than 15 significant digits: {n}' if (isNum && BigNumber.DEBUG && len > 15 && (v > MAX_SAFE_INTEGER || v !== mathfloor(v))) { throw Error (tooManyDigits + (x.s * v)); } // Overflow? if ((e = e - i - 1) > MAX_EXP) { // Infinity. x.c = x.e = null; // Underflow? } else if (e < MIN_EXP) { // Zero. x.c = [x.e = 0]; } else { x.e = e; x.c = []; // Transform base // e is the base 10 exponent. // i is where to slice str to get the first element of the coefficient array. i = (e + 1) % LOG_BASE; if (e < 0) i += LOG_BASE; // i < 1 if (i < len) { if (i) x.c.push(+str.slice(0, i)); for (len -= LOG_BASE; i < len;) { x.c.push(+str.slice(i, i += LOG_BASE)); } i = LOG_BASE - (str = str.slice(i)).length; } else { i -= len; } for (; i--; str += '0'); x.c.push(+str); } } else { // Zero. x.c = [x.e = 0]; } } // CONSTRUCTOR PROPERTIES BigNumber.clone = clone; BigNumber.ROUND_UP = 0; BigNumber.ROUND_DOWN = 1; BigNumber.ROUND_CEIL = 2; BigNumber.ROUND_FLOOR = 3; BigNumber.ROUND_HALF_UP = 4; BigNumber.ROUND_HALF_DOWN = 5; BigNumber.ROUND_HALF_EVEN = 6; BigNumber.ROUND_HALF_CEIL = 7; BigNumber.ROUND_HALF_FLOOR = 8; BigNumber.EUCLID = 9; /* * Configure infrequently-changing library-wide settings. * * Accept an object with the following optional properties (if the value of a property is * a number, it must be an integer within the inclusive range stated): * * DECIMAL_PLACES {number} 0 to MAX * ROUNDING_MODE {number} 0 to 8 * EXPONENTIAL_AT {number|number[]} -MAX to MAX or [-MAX to 0, 0 to MAX] * RANGE {number|number[]} -MAX to MAX (not zero) or [-MAX to -1, 1 to MAX] * CRYPTO {boolean} true or false * MODULO_MODE {number} 0 to 9 * POW_PRECISION {number} 0 to MAX * ALPHABET {string} A string of two or more unique characters which does * not contain '.'. * FORMAT {object} An object with some of the following properties: * prefix {string} * groupSize {number} * secondaryGroupSize {number} * groupSeparator {string} * decimalSeparator {string} * fractionGroupSize {number} * fractionGroupSeparator {string} * suffix {string} * * (The values assigned to the above FORMAT object properties are not checked for validity.) * * E.g. * BigNumber.config({ DECIMAL_PLACES : 20, ROUNDING_MODE : 4 }) * * Ignore properties/parameters set to null or undefined, except for ALPHABET. * * Return an object with the properties current values. */ BigNumber.config = BigNumber.set = function (obj) { var p, v; if (obj != null) { if (typeof obj == 'object') { // DECIMAL_PLACES {number} Integer, 0 to MAX inclusive. // '[BigNumber Error] DECIMAL_PLACES {not a primitive number|not an integer|out of range}: {v}' if (obj.hasOwnProperty(p = 'DECIMAL_PLACES')) { v = obj[p]; intCheck(v, 0, MAX, p); DECIMAL_PLACES = v; } // ROUNDING_MODE {number} Integer, 0 to 8 inclusive. // '[BigNumber Error] ROUNDING_MODE {not a primitive number|not an integer|out of range}: {v}' if (obj.hasOwnProperty(p = 'ROUNDING_MODE')) { v = obj[p]; intCheck(v, 0, 8, p); ROUNDING_MODE = v; } // EXPONENTIAL_AT {number|number[]} // Integer, -MAX to MAX inclusive or // [integer -MAX to 0 inclusive, 0 to MAX inclusive]. // '[BigNumber Error] EXPONENTIAL_AT {not a primitive number|not an integer|out of range}: {v}' if (obj.hasOwnProperty(p = 'EXPONENTIAL_AT')) { v = obj[p]; if (v && v.pop) { intCheck(v[0], -MAX, 0, p); intCheck(v[1], 0, MAX, p); TO_EXP_NEG = v[0]; TO_EXP_POS = v[1]; } else { intCheck(v, -MAX, MAX, p); TO_EXP_NEG = -(TO_EXP_POS = v < 0 ? -v : v); } } // RANGE {number|number[]} Non-zero integer, -MAX to MAX inclusive or // [integer -MAX to -1 inclusive, integer 1 to MAX inclusive]. // '[BigNumber Error] RANGE {not a primitive number|not an integer|out of range|cannot be zero}: {v}' if (obj.hasOwnProperty(p = 'RANGE')) { v = obj[p]; if (v && v.pop) { intCheck(v[0], -MAX, -1, p); intCheck(v[1], 1, MAX, p); MIN_EXP = v[0]; MAX_EXP = v[1]; } else { intCheck(v, -MAX, MAX, p); if (v) { MIN_EXP = -(MAX_EXP = v < 0 ? -v : v); } else { throw Error (bignumberError + p + ' cannot be zero: ' + v); } } } // CRYPTO {boolean} true or false. // '[BigNumber Error] CRYPTO not true or false: {v}' // '[BigNumber Error] crypto unavailable' if (obj.hasOwnProperty(p = 'CRYPTO')) { v = obj[p]; if (v === !!v) { if (v) { if (typeof crypto != 'undefined' && crypto && (crypto.getRandomValues || crypto.randomBytes)) { CRYPTO = v; } else { CRYPTO = !v; throw Error (bignumberError + 'crypto unavailable'); } } else { CRYPTO = v; } } else { throw Error (bignumberError + p + ' not true or false: ' + v); } } // MODULO_MODE {number} Integer, 0 to 9 inclusive. // '[BigNumber Error] MODULO_MODE {not a primitive number|not an integer|out of range}: {v}' if (obj.hasOwnProperty(p = 'MODULO_MODE')) { v = obj[p]; intCheck(v, 0, 9, p); MODULO_MODE = v; } // POW_PRECISION {number} Integer, 0 to MAX inclusive. // '[BigNumber Error] POW_PRECISION {not a primitive number|not an integer|out of range}: {v}' if (obj.hasOwnProperty(p = 'POW_PRECISION')) { v = obj[p]; intCheck(v, 0, MAX, p); POW_PRECISION = v; } // FORMAT {object} // '[BigNumber Error] FORMAT not an object: {v}' if (obj.hasOwnProperty(p = 'FORMAT')) { v = obj[p]; if (typeof v == 'object') FORMAT = v; else throw Error (bignumberError + p + ' not an object: ' + v); } // ALPHABET {string} // '[BigNumber Error] ALPHABET invalid: {v}' if (obj.hasOwnProperty(p = 'ALPHABET')) { v = obj[p]; // Disallow if less than two characters, // or if it contains '+', '-', '.', whitespace, or a repeated character. if (typeof v == 'string' && !/^.?$|[+\-.\s]|(.).*\1/.test(v)) { alphabetHasNormalDecimalDigits = v.slice(0, 10) == '0123456789'; ALPHABET = v; } else { throw Error (bignumberError + p + ' invalid: ' + v); } } } else { // '[BigNumber Error] Object expected: {v}' throw Error (bignumberError + 'Object expected: ' + obj); } } return { DECIMAL_PLACES: DECIMAL_PLACES, ROUNDING_MODE: ROUNDING_MODE, EXPONENTIAL_AT: [TO_EXP_NEG, TO_EXP_POS], RANGE: [MIN_EXP, MAX_EXP], CRYPTO: CRYPTO, MODULO_MODE: MODULO_MODE, POW_PRECISION: POW_PRECISION, FORMAT: FORMAT, ALPHABET: ALPHABET }; }; /* * Return true if v is a BigNumber instance, otherwise return false. * * If BigNumber.DEBUG is true, throw if a BigNumber instance is not well-formed. * * v {any} * * '[BigNumber Error] Invalid BigNumber: {v}' */ BigNumber.isBigNumber = function (v) { if (!v || v._isBigNumber !== true) return false; if (!BigNumber.DEBUG) return true; var i, n, c = v.c, e = v.e, s = v.s; out: if ({}.toString.call(c) == '[object Array]') { if ((s === 1 || s === -1) && e >= -MAX && e <= MAX && e === mathfloor(e)) { // If the first element is zero, the BigNumber value must be zero. if (c[0] === 0) { if (e === 0 && c.length === 1) return true; break out; } // Calculate number of digits that c[0] should have, based on the exponent. i = (e + 1) % LOG_BASE; if (i < 1) i += LOG_BASE; // Calculate number of digits of c[0]. //if (Math.ceil(Math.log(c[0] + 1) / Math.LN10) == i) { if (String(c[0]).length == i) { for (i = 0; i < c.length; i++) { n = c[i]; if (n < 0 || n >= BASE || n !== mathfloor(n)) break out; } // Last element cannot be zero, unless it is the only element. if (n !== 0) return true; } } // Infinity/NaN } else if (c === null && e === null && (s === null || s === 1 || s === -1)) { return true; } throw Error (bignumberError + 'Invalid BigNumber: ' + v); }; /* * Return a new BigNumber whose value is the maximum of the arguments. * * arguments {number|string|BigNumber} */ BigNumber.maximum = BigNumber.max = function () { return maxOrMin(arguments, P.lt); }; /* * Return a new BigNumber whose value is the minimum of the arguments. * * arguments {number|string|BigNumber} */ BigNumber.minimum = BigNumber.min = function () { return maxOrMin(arguments, P.gt); }; /* * Return a new BigNumber with a random value equal to or greater than 0 and less than 1, * and with dp, or DECIMAL_PLACES if dp is omitted, decimal places (or less if trailing * zeros are produced). * * [dp] {number} Decimal places. Integer, 0 to MAX inclusive. * * '[BigNumber Error] Argument {not a primitive number|not an integer|out of range}: {dp}' * '[BigNumber Error] crypto unavailable' */ BigNumber.random = (function () { var pow2_53 = 0x20000000000000; // Return a 53 bit integer n, where 0 <= n < 9007199254740992. // Check if Math.random() produces more than 32 bits of randomness. // If it does, assume at least 53 bits are produced, otherwise assume at least 30 bits. // 0x40000000 is 2^30, 0x800000 is 2^23, 0x1fffff is 2^21 - 1. var random53bitInt = (Math.random() * pow2_53) & 0x1fffff ? function () { return mathfloor(Math.random() * pow2_53); } : function () { return ((Math.random() * 0x40000000 | 0) * 0x800000) + (Math.random() * 0x800000 | 0); }; return function (dp) { var a, b, e, k, v, i = 0, c = [], rand = new BigNumber(ONE); if (dp == null) dp = DECIMAL_PLACES; else intCheck(dp, 0, MAX); k = mathceil(dp / LOG_BASE); if (CRYPTO) { // Browsers supporting crypto.getRandomValues. if (crypto.getRandomValues) { a = crypto.getRandomValues(new Uint32Array(k *= 2)); for (; i < k;) { // 53 bits: // ((Math.pow(2, 32) - 1) * Math.pow(2, 21)).toString(2) // 11111 11111111 11111111 11111111 11100000 00000000 00000000 // ((Math.pow(2, 32) - 1) >>> 11).toString(2) // 11111 11111111 11111111 // 0x20000 is 2^21. v = a[i] * 0x20000 + (a[i + 1] >>> 11); // Rejection sampling: // 0 <= v < 9007199254740992 // Probability that v >= 9e15, is // 7199254740992 / 9007199254740992 ~= 0.0008, i.e. 1 in 1251 if (v >= 9e15) { b = crypto.getRandomValues(new Uint32Array(2)); a[i] = b[0]; a[i + 1] = b[1]; } else { // 0 <= v <= 8999999999999999 // 0 <= (v % 1e14) <= 99999999999999 c.push(v % 1e14); i += 2; } } i = k / 2; // Node.js supporting crypto.randomBytes. } else if (crypto.randomBytes) { // buffer a = crypto.randomBytes(k *= 7); for (; i < k;) { // 0x1000000000000 is 2^48, 0x10000000000 is 2^40 // 0x100000000 is 2^32, 0x1000000 is 2^24 // 11111 11111111 11111111 11111111 11111111 11111111 11111111 // 0 <= v < 9007199254740992 v = ((a[i] & 31) * 0x1000000000000) + (a[i + 1] * 0x10000000000) + (a[i + 2] * 0x100000000) + (a[i + 3] * 0x1000000) + (a[i + 4] << 16) + (a[i + 5] << 8) + a[i + 6]; if (v >= 9e15) { crypto.randomBytes(7).copy(a, i); } else { // 0 <= (v % 1e14) <= 99999999999999 c.push(v % 1e14); i += 7; } } i = k / 7; } else { CRYPTO = false; throw Error (bignumberError + 'crypto unavailable'); } } // Use Math.random. if (!CRYPTO) { for (; i < k;) { v = random53bitInt(); if (v < 9e15) c[i++] = v % 1e14; } } k = c[--i]; dp %= LOG_BASE; // Convert trailing digits to zeros according to dp. if (k && dp) { v = POWS_TEN[LOG_BASE - dp]; c[i] = mathfloor(k / v) * v; } // Remove trailing elements which are zero. for (; c[i] === 0; c.pop(), i--); // Zero? if (i < 0) { c = [e = 0]; } else { // Remove leading elements which are zero and adjust exponent accordingly. for (e = -1 ; c[0] === 0; c.splice(0, 1), e -= LOG_BASE); // Count the digits of the first element of c to determine leading zeros, and... for (i = 1, v = c[0]; v >= 10; v /= 10, i++); // adjust the exponent accordingly. if (i < LOG_BASE) e -= LOG_BASE - i; } rand.e = e; rand.c = c; return rand; }; })(); /* * Return a BigNumber whose value is the sum of the arguments. * * arguments {number|string|BigNumber} */ BigNumber.sum = function () { var i = 1, args = arguments, sum = new BigNumber(args[0]); for (; i < args.length;) sum = sum.plus(args[i++]); return sum; }; // PRIVATE FUNCTIONS // Called by BigNumber and BigNumber.prototype.toString. convertBase = (function () { var decimal = '0123456789'; /* * Convert string of baseIn to an array of numbers of baseOut. * Eg. toBaseOut('255', 10, 16) returns [15, 15]. * Eg. toBaseOut('ff', 16, 10) returns [2, 5, 5]. */ function toBaseOut(str, baseIn, baseOut, alphabet) { var j, arr = [0], arrL, i = 0, len = str.length; for (; i < len;) { for (arrL = arr.length; arrL--; arr[arrL] *= baseIn); arr[0] += alphabet.indexOf(str.charAt(i++)); for (j = 0; j < arr.length; j++) { if (arr[j] > baseOut - 1) { if (arr[j + 1] == null) arr[j + 1] = 0; arr[j + 1] += arr[j] / baseOut | 0; arr[j] %= baseOut; } } } return arr.reverse(); } // Convert a numeric string of baseIn to a numeric string of baseOut. // If the caller is toString, we are converting from base 10 to baseOut. // If the caller is BigNumber, we are converting from baseIn to base 10. return function (str, baseIn, baseOut, sign, callerIsToString) { var alphabet, d, e, k, r, x, xc, y, i = str.indexOf('.'), dp = DECIMAL_PLACES, rm = ROUNDING_MODE; // Non-integer. if (i >= 0) { k = POW_PRECISION; // Unlimited precision. POW_PRECISION = 0; str = str.replace('.', ''); y = new BigNumber(baseIn); x = y.pow(str.length - i); POW_PRECISION = k; // Convert str as if an integer, then restore the fraction part by dividing the // result by its base raised to a power. y.c = toBaseOut(toFixedPoint(coeffToString(x.c), x.e, '0'), 10, baseOut, decimal); y.e = y.c.length; } // Convert the number as integer. xc = toBaseOut(str, baseIn, baseOut, callerIsToString ? (alphabet = ALPHABET, decimal) : (alphabet = decimal, ALPHABET)); // xc now represents str as an integer and converted to baseOut. e is the exponent. e = k = xc.length; // Remove trailing zeros. for (; xc[--k] == 0; xc.pop()); // Zero? if (!xc[0]) return alphabet.charAt(0); // Does str represent an integer? If so, no need for the division. if (i < 0) { --e; } else { x.c = xc; x.e = e; // The sign is needed for correct rounding. x.s = sign; x = div(x, y, dp, rm, baseOut); xc = x.c; r = x.r; e = x.e; } // xc now represents str converted to baseOut. // THe index of the rounding digit. d = e + dp + 1; // The rounding digit: the digit to the right of the digit that may be rounded up. i = xc[d]; // Look at the rounding digits and mode to determine whether to round up. k = baseOut / 2; r = r || d < 0 || xc[d + 1] != null; r = rm < 4 ? (i != null || r) && (rm == 0 || rm == (x.s < 0 ? 3 : 2)) : i > k || i == k &&(rm == 4 || r || rm == 6 && xc[d - 1] & 1 || rm == (x.s < 0 ? 8 : 7)); // If the index of the rounding digit is not greater than zero, or xc represents // zero, then the result of the base conversion is zero or, if rounding up, a value // such as 0.00001. if (d < 1 || !xc[0]) { // 1^-dp or 0 str = r ? toFixedPoint(alphabet.charAt(1), -dp, alphabet.charAt(0)) : alphabet.charAt(0); } else { // Truncate xc to the required number of decimal places. xc.length = d; // Round up? if (r) { // Rounding up may mean the previous digit has to be rounded up and so on. for (--baseOut; ++xc[--d] > baseOut;) { xc[d] = 0; if (!d) { ++e; xc = [1].concat(xc); } } } // Determine trailing zeros. for (k = xc.length; !xc[--k];); // E.g. [4, 11, 15] becomes 4bf. for (i = 0, str = ''; i <= k; str += alphabet.charAt(xc[i++])); // Add leading zeros, decimal point and trailing zeros as required. str = toFixedPoint(str, e, alphabet.charAt(0)); } // The caller will add the sign. return str; }; })(); // Perform division in the specified base. Called by div and convertBase. div = (function () { // Assume non-zero x and k. function multiply(x, k, base) { var m, temp, xlo, xhi, carry = 0, i = x.length, klo = k % SQRT_BASE, khi = k / SQRT_BASE | 0; for (x = x.slice(); i--;) { xlo = x[i] % SQRT_BASE; xhi = x[i] / SQRT_BASE | 0; m = khi * xlo + xhi * klo; temp = klo * xlo + ((m % SQRT_BASE) * SQRT_BASE) + carry; carry = (temp / base | 0) + (m / SQRT_BASE | 0) + khi * xhi; x[i] = temp % base; } if (carry) x = [carry].concat(x); return x; } function compare(a, b, aL, bL) { var i, cmp; if (aL != bL) { cmp = aL > bL ? 1 : -1; } else { for (i = cmp = 0; i < aL; i++) { if (a[i] != b[i]) { cmp = a[i] > b[i] ? 1 : -1; break; } } } return cmp; } function subtract(a, b, aL, base) { var i = 0; // Subtract b from a. for (; aL--;) { a[aL] -= i; i = a[aL] < b[aL] ? 1 : 0; a[aL] = i * base + a[aL] - b[aL]; } // Remove leading zeros. for (; !a[0] && a.length > 1; a.splice(0, 1)); } // x: dividend, y: divisor. return function (x, y, dp, rm, base) { var cmp, e, i, more, n, prod, prodL, q, qc, rem, remL, rem0, xi, xL, yc0, yL, yz, s = x.s == y.s ? 1 : -1, xc = x.c, yc = y.c; // Either NaN, Infinity or 0? if (!xc || !xc[0] || !yc || !yc[0]) { return new BigNumber( // Return NaN if either NaN, or both Infinity or 0. !x.s || !y.s || (xc ? yc && xc[0] == yc[0] : !yc) ? NaN : // Return ±0 if x is ±0 or y is ±Infinity, or return ±Infinity as y is ±0. xc && xc[0] == 0 || !yc ? s * 0 : s / 0 ); } q = new BigNumber(s); qc = q.c = []; e = x.e - y.e; s = dp + e + 1; if (!base) { base = BASE; e = bitFloor(x.e / LOG_BASE) - bitFloor(y.e / LOG_BASE); s = s / LOG_BASE | 0; } // Result exponent may be one less then the current value of e. // The coefficients of the BigNumbers from convertBase may have trailing zeros. for (i = 0; yc[i] == (xc[i] || 0); i++); if (yc[i] > (xc[i] || 0)) e--; if (s < 0) { qc.push(1); more = true; } else { xL = xc.length; yL = yc.length; i = 0; s += 2; // Normalise xc and yc so highest order digit of yc is >= base / 2. n = mathfloor(base / (yc[0] + 1)); // Not necessary, but to handle odd bases where yc[0] == (base / 2) - 1. // if (n > 1 || n++ == 1 && yc[0] < base / 2) { if (n > 1) { yc = multiply(yc, n, base); xc = multiply(xc, n, base); yL = yc.length; xL = xc.length; } xi = yL; rem = xc.slice(0, yL); remL = rem.length; // Add zeros to make remainder as long as divisor. for (; remL < yL; rem[remL++] = 0); yz = yc.slice(); yz = [0].concat(yz); yc0 = yc[0]; if (yc[1] >= base / 2) yc0++; // Not necessary, but to prevent trial digit n > base, when using base 3. // else if (base == 3 && yc0 == 1) yc0 = 1 + 1e-15; do { n = 0; // Compare divisor and remainder. cmp = compare(yc, rem, yL, remL); // If divisor < remainder. if (cmp < 0) { // Calculate trial digit, n. rem0 = rem[0]; if (yL != remL) rem0 = rem0 * base + (rem[1] || 0); // n is how many times the divisor goes into the current remainder. n = mathfloor(rem0 / yc0); // Algorithm: // product = divisor multiplied by trial digit (n). // Compare product and remainder. // If product is greater than remainder: // Subtract divisor from product, decrement trial digit. // Subtract product from remainder. // If product was less than remainder at the last compare: // Compare new remainder and divisor. // If remainder is greater than divisor: // Subtract divisor from remainder, increment trial digit. if (n > 1) { // n may be > base only when base is 3. if (n >= base) n = base - 1; // product = divisor * trial digit. prod = multiply(yc, n, base); prodL = prod.length; remL = rem.length; // Compare product and remainder. // If product > remainder then trial digit n too high. // n is 1 too high about 5% of the time, and is not known to have // ever been more than 1 too high. while (compare(prod, rem, prodL, remL) == 1) { n--; // Subtract divisor from product. subtract(prod, yL < prodL ? yz : yc, prodL, base); prodL = prod.length; cmp = 1; } } else { // n is 0 or 1, cmp is -1. // If n is 0, there is no need to compare yc and rem again below, // so change cmp to 1 to avoid it. // If n is 1, leave cmp as -1, so yc and rem are compared again. if (n == 0) { // divisor < remainder, so n must be at least 1. cmp = n = 1; } // product = divisor prod = yc.slice(); prodL = prod.length; } if (prodL < remL) prod = [0].concat(prod); // Subtract product from remainder. subtract(rem, prod, remL, base); remL = rem.length; // If product was < remainder. if (cmp == -1) { // Compare divisor and new remainder. // If divisor < new remainder, subtract divisor from remainder. // Trial digit n too low. // n is 1 too low about 5% of the time, and very rarely 2 too low. while (compare(yc, rem, yL, remL) < 1) { n++; // Subtract divisor from remainder. subtract(rem, yL < remL ? yz : yc, remL, base); remL = rem.length; } } } else if (cmp === 0) { n++; rem = [0]; } // else cmp === 1 and n will be 0 // Add the next digit, n, to the result array. qc[i++] = n; // Update the remainder. if (rem[0]) { rem[remL++] = xc[xi] || 0; } else { rem = [xc[xi]]; remL = 1; } } while ((xi++ < xL || rem[0] != null) && s--); more = rem[0] != null; // Leading zero? if (!qc[0]) qc.splice(0, 1); } if (base == BASE) { // To calculate q.e, first get the number of digits of qc[0]. for (i = 1, s = qc[0]; s >= 10; s /= 10, i++); round(q, dp + (q.e = i + e * LOG_BASE - 1) + 1, rm, more); // Caller is convertBase. } else { q.e = e; q.r = +more; } return q; }; })(); /* * Return a string representing the value of BigNumber n in fixed-point or exponential * notation rounded to the specified decimal places or significant digits. * * n: a BigNumber. * i: the index of the last digit required (i.e. the digit that may be rounded up). * rm: the rounding mode. * id: 1 (toExponential) or 2 (toPrecision). */ function format(n, i, rm, id) { var c0, e, ne, len, str; if (rm == null) rm = ROUNDING_MODE; else intCheck(rm, 0, 8); if (!n.c) return n.toString(); c0 = n.c[0]; ne = n.e; if (i == null) { str = coeffToString(n.c); str = id == 1 || id == 2 && (ne <= TO_EXP_NEG || ne >= TO_EXP_POS) ? toExponential(str, ne) : toFixedPoint(str, ne, '0'); } else { n = round(new BigNumber(n), i, rm); // n.e may have changed if the value was rounded up. e = n.e; str = coeffToString(n.c); len = str.length; // toPrecision returns exponential notation if the number of significant digits // specified is less than the number of digits necessary to represent the integer // part of the value in fixed-point notation. // Exponential notation. if (id == 1 || id == 2 && (i <= e || e <= TO_EXP_NEG)) { // Append zeros? for (; len < i; str += '0', len++); str = toExponential(str, e); // Fixed-point notation. } else { i -= ne; str = toFixedPoint(str, e, '0'); // Append zeros? if (e + 1 > len) { if (--i > 0) for (str += '.'; i--; str += '0'); } else { i += e - len; if (i > 0) { if (e + 1 == len) str += '.'; for (; i--; str += '0'); } } } } return n.s < 0 && c0 ? '-' + str : str; } // Handle BigNumber.max and BigNumber.min. function maxOrMin(args, method) { var n, i = 1, m = new BigNumber(args[0]); for (; i < args.length; i++) { n = new BigNumber(args[i]); // If any number is NaN, return NaN. if (!n.s) { m = n; break; } else if (method.call(m, n)) { m = n; } } return m; } /* * Strip trailing zeros, calculate base 10 exponent and check against MIN_EXP and MAX_EXP. * Called by minus, plus and times. */ function normalise(n, c, e) { var i = 1, j = c.length; // Remove trailing zeros. for (; !c[--j]; c.pop()); // Calculate the base 10 exponent. First get the number of digits of c[0]. for (j = c[0]; j >= 10; j /= 10, i++); // Overflow? if ((e = i + e * LOG_BASE - 1) > MAX_EXP) { // Infinity. n.c = n.e = null; // Underflow? } else if (e < MIN_EXP) { // Zero. n.c = [n.e = 0]; } else { n.e = e; n.c = c; } return n; } // Handle values that fail the validity test in BigNumber. parseNumeric = (function () { var basePrefix = /^(-?)0([xbo])(?=\w[\w.]*$)/i, dotAfter = /^([^.]+)\.$/, dotBefore = /^\.([^.]+)$/, isInfinityOrNaN = /^-?(Infinity|NaN)$/, whitespaceOrPlus = /^\s*\+(?=[\w.])|^\s+|\s+$/g; return function (x, str, isNum, b) { var base, s = isNum ? str : str.replace(whitespaceOrPlus, ''); // No exception on ±Infinity or NaN. if (isInfinityOrNaN.test(s)) { x.s = isNaN(s) ? null : s < 0 ? -1 : 1; } else { if (!isNum) { // basePrefix = /^(-?)0([xbo])(?=\w[\w.]*$)/i s = s.replace(basePrefix, function (m, p1, p2) { base = (p2 = p2.toLowerCase()) == 'x' ? 16 : p2 == 'b' ? 2 : 8; return !b || b == base ? p1 : m; }); if (b) { base = b; // E.g. '1.' to '1', '.1' to '0.1' s = s.replace(dotAfter, '$1').replace(dotBefore, '0.$1'); } if (str != s) return new BigNumber(s, base); } // '[BigNumber Error] Not a number: {n}' // '[BigNumber Error] Not a base {b} number: {n}' if (BigNumber.DEBUG) { throw Error (bignumberError + 'Not a' + (b ? ' base ' + b : '') + ' number: ' + str); } // NaN x.s = null; } x.c = x.e = null; } })(); /* * Round x to sd significant digits using rounding mode rm. Check for over/under-flow. * If r is truthy, it is known that there are more digits after the rounding digit. */ function round(x, sd, rm, r) { var d, i, j, k, n, ni, rd, xc = x.c, pows10 = POWS_TEN; // if x is not Infinity or NaN... if (xc) { // rd is the rounding digit, i.e. the digit after the digit that may be rounded up. // n is a base 1e14 number, the value of the element of array x.c containing rd. // ni is the index of n within x.c. // d is the number of digits of n. // i is the index of rd within n including leading zeros. // j is the actual index of rd within n (if < 0, rd is a leading zero). out: { // Get the number of digits of the first element of xc. for (d = 1, k = xc[0]; k >= 10; k /= 10, d++); i = sd - d; // If the rounding digit is in the first element of xc... if (i < 0) { i += LOG_BASE; j = sd; n = xc[ni = 0]; // Get the rounding digit at index j of n. rd = n / pows10[d - j - 1] % 10 | 0; } else { ni = mathceil((i + 1) / LOG_BASE); if (ni >= xc.length) { if (r) { // Needed by sqrt. for (; xc.length <= ni; xc.push(0)); n = rd = 0; d = 1; i %= LOG_BASE; j = i - LOG_BASE + 1; } else { break out; } } else { n = k = xc[ni]; // Get the number of digits of n. for (d = 1; k >= 10; k /= 10, d++); // Get the index of rd within n. i %= LOG_BASE; // Get the index of rd within n, adjusted for leading zeros. // The number of leading zeros of n is given by LOG_BASE - d. j = i - LOG_BASE + d; // Get the rounding digit at index j of n. rd = j < 0 ? 0 : n / pows10[d - j - 1] % 10 | 0; } } r = r || sd < 0 || // Are there any non-zero digits after the rounding digit? // The expression n % pows10[d - j - 1] returns all digits of n to the right // of the digit at j, e.g. if n is 908714 and j is 2, the expression gives 714. xc[ni + 1] != null || (j < 0 ? n : n % pows10[d - j - 1]); r = rm < 4 ? (rd || r) && (rm == 0 || rm == (x.s < 0 ? 3 : 2)) : rd > 5 || rd == 5 && (rm == 4 || r || rm == 6 && // Check whether the digit to the left of the rounding digit is odd. ((i > 0 ? j > 0 ? n / pows10[d - j] : 0 : xc[ni - 1]) % 10) & 1 || rm == (x.s < 0 ? 8 : 7)); if (sd < 1 || !xc[0]) { xc.length = 0; if (r) { // Convert sd to decimal places. sd -= x.e + 1; // 1, 0.1, 0.01, 0.001, 0.0001 etc. xc[0] = pows10[(LOG_BASE - sd % LOG_BASE) % LOG_BASE]; x.e = -sd || 0; } else { // Zero. xc[0] = x.e = 0; } return x; } // Remove excess digits. if (i == 0) { xc.length = ni; k = 1; ni--; } else { xc.length = ni + 1; k = pows10[LOG_BASE - i]; // E.g. 56700 becomes 56000 if 7 is the rounding digit. // j > 0 means i > number of leading zeros of n. xc[ni] = j > 0 ? mathfloor(n / pows10[d - j] % pows10[j]) * k : 0; } // Round up? if (r) { for (; ;) { // If the digit to be rounded up is in the first element of xc... if (ni == 0) { // i will be the length of xc[0] before k is added. for (i = 1, j = xc[0]; j >= 10; j /= 10, i++); j = xc[0] += k; for (k = 1; j >= 10; j /= 10, k++); // if i != k the length has increased. if (i != k) { x.e++; if (xc[0] == BASE) xc[0] = 1; } break; } else { xc[ni] += k; if (xc[ni] != BASE) break; xc[ni--] = 0; k = 1; } } } // Remove trailing zeros. for (i = xc.length; xc[--i] === 0; xc.pop()); } // Overflow? Infinity. if (x.e > MAX_EXP) { x.c = x.e = null; // Underflow? Zero. } else if (x.e < MIN_EXP) { x.c = [x.e = 0]; } } return x; } function valueOf(n) { var str, e = n.e; if (e === null) return n.toString(); str = coeffToString(n.c); str = e <= TO_EXP_NEG || e >= TO_EXP_POS ? toExponential(str, e) : toFixedPoint(str, e, '0'); return n.s < 0 ? '-' + str : str; } // PROTOTYPE/INSTANCE METHODS /* * Return a new BigNumber whose value is the absolute value of this BigNumber. */ P.absoluteValue = P.abs = function () { var x = new BigNumber(this); if (x.s < 0) x.s = 1; return x; }; /* * Return * 1 if the value of this BigNumber is greater than the value of BigNumber(y, b), * -1 if the value of this BigNumber is less than the value of BigNumber(y, b), * 0 if they have the same value, * or null if the value of either is NaN. */ P.comparedTo = function (y, b) { return compare(this, new BigNumber(y, b)); }; /* * If dp is undefined or null or true or false, return the number of decimal places of the * value of this BigNumber, or null if the value of this BigNumber is ±Infinity or NaN. * * Otherwise, if dp is a number, return a new BigNumber whose value is the value of this * BigNumber rounded to a maximum of dp decimal places using rounding mode rm, or * ROUNDING_MODE if rm is omitted. * * [dp] {number} Decimal places: integer, 0 to MAX inclusive. * [rm] {number} Rounding mode. Integer, 0 to 8 inclusive. * * '[BigNumber Error] Argument {not a primitive number|not an integer|out of range}: {dp|rm}' */ P.decimalPlaces = P.dp = function (dp, rm) { var c, n, v, x = this; if (dp != null) { intCheck(dp, 0, MAX); if (rm == null) rm = ROUNDING_MODE; else intCheck(rm, 0, 8); return round(new BigNumber(x), dp + x.e + 1, rm); } if (!(c = x.c)) return null; n = ((v = c.length - 1) - bitFloor(this.e / LOG_BASE)) * LOG_BASE; // Subtract the number of trailing zeros of the last number. if (v = c[v]) for (; v % 10 == 0; v /= 10, n--); if (n < 0) n = 0; return n; }; /* * n / 0 = I * n / N = N * n / I = 0 * 0 / n = 0 * 0 / 0 = N * 0 / N = N * 0 / I = 0 * N / n = N * N / 0 = N * N / N = N * N / I = N * I / n = I * I / 0 = I * I / N = N * I / I = N * * Return a new BigNumber whose value is the value of this BigNumber divided by the value of * BigNumber(y, b), rounded according to DECIMAL_PLACES and ROUNDING_MODE. */ P.dividedBy = P.div = function (y, b) { return div(this, new BigNumber(y, b), DECIMAL_PLACES, ROUNDING_MODE); }; /* * Return a new BigNumber whose value is the integer part of dividing the value of this * BigNumber by the value of BigNumber(y, b). */ P.dividedToIntegerBy = P.idiv = function (y, b) { return div(this, new BigNumber(y, b), 0, 1); }; /* * Return a BigNumber whose value is the value of this BigNumber exponentiated by n. * * If m is present, return the result modulo m. * If n is negative round according to DECIMAL_PLACES and ROUNDING_MODE. * If POW_PRECISION is non-zero and m is not present, round to POW_PRECISION using ROUNDING_MODE. * * The modular power operation works efficiently when x, n, and m are integers, otherwise it * is equivalent to calculating x.exponentiatedBy(n).modulo(m) with a POW_PRECISION of 0. * * n {number|string|BigNumber} The exponent. An integer. * [m] {number|string|BigNumber} The modulus. * * '[BigNumber Error] Exponent not an integer: {n}' */ P.exponentiatedBy = P.pow = function (n, m) { var half, isModExp, i, k, more, nIsBig, nIsNeg, nIsOdd, y, x = this; n = new BigNumber(n); // Allow NaN and ±Infinity, but not other non-integers. if (n.c && !n.isInteger()) { throw Error (bignumberError + 'Exponent not an integer: ' + valueOf(n)); } if (m != null) m = new BigNumber(m); // Exponent of MAX_SAFE_INTEGER is 15. nIsBig = n.e > 14; // If x is NaN, ±Infinity, ±0 or ±1, or n is ±Infinity, NaN or ±0. if (!x.c || !x.c[0] || x.c[0] == 1 && !x.e && x.c.length == 1 || !n.c || !n.c[0]) { // The sign of the result of pow when x is negative depends on the evenness of n. // If +n overflows to ±Infinity, the evenness of n would be not be known. y = new BigNumber(Math.pow(+valueOf(x), nIsBig ? 2 - isOdd(n) : +valueOf(n))); return m ? y.mod(m) : y; } nIsNeg = n.s < 0; if (m) { // x % m returns NaN if abs(m) is zero, or m is NaN. if (m.c ? !m.c[0] : !m.s) return new BigNumber(NaN); isModExp = !nIsNeg && x.isInteger() && m.isInteger(); if (isModExp) x = x.mod(m); // Overflow to ±Infinity: >=2**1e10 or >=1.0000024**1e15. // Underflow to ±0: <=0.79**1e10 or <=0.9999975**1e15. } else if (n.e > 9 && (x.e > 0 || x.e < -1 || (x.e == 0 // [1, 240000000] ? x.c[0] > 1 || nIsBig && x.c[1] >= 24e7 // [80000000000000] [99999750000000] : x.c[0] < 8e13 || nIsBig && x.c[0] <= 9999975e7))) { // If x is negative and n is odd, k = -0, else k = 0. k = x.s < 0 && isOdd(n) ? -0 : 0; // If x >= 1, k = ±Infinity. if (x.e > -1) k = 1 / k; // If n is negative return ±0, else return ±Infinity. return new BigNumber(nIsNeg ? 1 / k : k); } else if (POW_PRECISION) { // Truncating each coefficient array to a length of k after each multiplication // equates to truncating significant digits to POW_PRECISION + [28, 41], // i.e. there will be a minimum of 28 guard digits retained. k = mathceil(POW_PRECISION / LOG_BASE + 2); } if (nIsBig) { half = new BigNumber(0.5); if (nIsNeg) n.s = 1; nIsOdd = isOdd(n); } else { i = Math.abs(+valueOf(n)); nIsOdd = i % 2; } y = new BigNumber(ONE); // Performs 54 loop iterations for n of 9007199254740991. for (; ;) { if (nIsOdd) { y = y.times(x); if (!y.c) break; if (k) { if (y.c.length > k) y.c.length = k; } else if (isModExp) { y = y.mod(m); //y = y.minus(div(y, m, 0, MODULO_MODE).times(m)); } } if (i) { i = mathfloor(i / 2); if (i === 0) break; nIsOdd = i % 2; } else { n = n.times(half); round(n, n.e + 1, 1); if (n.e > 14) { nIsOdd = isOdd(n); } else { i = +valueOf(n); if (i === 0) break; nIsOdd = i % 2; } } x = x.times(x); if (k) { if (x.c && x.c.length > k) x.c.length = k; } else if (isModExp) { x = x.mod(m); //x = x.minus(div(x, m, 0, MODULO_MODE).times(m)); } } if (isModExp) return y; if (nIsNeg) y = ONE.div(y); return m ? y.mod(m) : k ? round(y, POW_PRECISION, ROUNDING_MODE, more) : y; }; /* * Return a new BigNumber whose value is the value of this BigNumber rounded to an integer * using rounding mode rm, or ROUNDING_MODE if rm is omitted. * * [rm] {number} Rounding mode. Integer, 0 to 8 inclusive. * * '[BigNumber Error] Argument {not a primitive number|not an integer|out of range}: {rm}' */ P.integerValue = function (rm) { var n = new BigNumber(this); if (rm == null) rm = ROUNDING_MODE; else intCheck(rm, 0, 8); return round(n, n.e + 1, rm); }; /* * Return true if the value of this BigNumber is equal to the value of BigNumber(y, b), * otherwise return false. */ P.isEqualTo = P.eq = function (y, b) { return compare(this, new BigNumber(y, b)) === 0; }; /* * Return true if the value of this BigNumber is a finite number, otherwise return false. */ P.isFinite = function () { return !!this.c; }; /* * Return true if the value of this BigNumber is greater than the value of BigNumber(y, b), * otherwise return false. */ P.isGreaterThan = P.gt = function (y, b) { return compare(this, new BigNumber(y, b)) > 0; }; /* * Return true if the value of this BigNumber is greater than or equal to the value of * BigNumber(y, b), otherwise return false. */ P.isGreaterThanOrEqualTo = P.gte = function (y, b) { return (b = compare(this, new BigNumber(y, b))) === 1 || b === 0; }; /* * Return true if the value of this BigNumber is an integer, otherwise return false. */ P.isInteger = function () { return !!this.c && bitFloor(this.e / LOG_BASE) > this.c.length - 2; }; /* * Return true if the value of this BigNumber is less than the value of BigNumber(y, b), * otherwise return false. */ P.isLessThan = P.lt = function (y, b) { return compare(this, new BigNumber(y, b)) < 0; }; /* * Return true if the value of this BigNumber is less than or equal to the value of * BigNumber(y, b), otherwise return false. */ P.isLessThanOrEqualTo = P.lte = function (y, b) { return (b = compare(this, new BigNumber(y, b))) === -1 || b === 0; }; /* * Return true if the value of this BigNumber is NaN, otherwise return false. */ P.isNaN = function () { return !this.s; }; /* * Return true if the value of this BigNumber is negative, otherwise return false. */ P.isNegative = function () { return this.s < 0; }; /* * Return true if the value of this BigNumber is positive, otherwise return false. */ P.isPositive = function () { return this.s > 0; }; /* * Return true if the value of this BigNumber is 0 or -0, otherwise return false. */ P.isZero = function () { return !!this.c && this.c[0] == 0; }; /* * n - 0 = n * n - N = N * n - I = -I * 0 - n = -n * 0 - 0 = 0 * 0 - N = N * 0 - I = -I * N - n = N * N - 0 = N * N - N = N * N - I = N * I - n = I * I - 0 = I * I - N = N * I - I = N * * Return a new BigNumber whose value is the value of this BigNumber minus the value of * BigNumber(y, b). */ P.minus = function (y, b) { var i, j, t, xLTy, x = this, a = x.s; y = new BigNumber(y, b); b = y.s; // Either NaN? if (!a || !b) return new BigNumber(NaN); // Signs differ? if (a != b) { y.s = -b; return x.plus(y); } var xe = x.e / LOG_BASE, ye = y.e / LOG_BASE, xc = x.c, yc = y.c; if (!xe || !ye) { // Either Infinity? if (!xc || !yc) return xc ? (y.s = -b, y) : new BigNumber(yc ? x : NaN); // Either zero? if (!xc[0] || !yc[0]) { // Return y if y is non-zero, x if x is non-zero, or zero if both are zero. return yc[0] ? (y.s = -b, y) : new BigNumber(xc[0] ? x : // IEEE 754 (2008) 6.3: n - n = -0 when rounding to -Infinity ROUNDING_MODE == 3 ? -0 : 0); } } xe = bitFloor(xe); ye = bitFloor(ye); xc = xc.slice(); // Determine which is the bigger number. if (a = xe - ye) { if (xLTy = a < 0) { a = -a; t = xc; } else { ye = xe; t = yc; } t.reverse(); // Prepend zeros to equalise exponents. for (b = a; b--; t.push(0)); t.reverse(); } else { // Exponents equal. Check digit by digit. j = (xLTy = (a = xc.length) < (b = yc.length)) ? a : b; for (a = b = 0; b < j; b++) { if (xc[b] != yc[b]) { xLTy = xc[b] < yc[b]; break; } } } // x < y? Point xc to the array of the bigger number. if (xLTy) t = xc, xc = yc, yc = t, y.s = -y.s; b = (j = yc.length) - (i = xc.length); // Append zeros to xc if shorter. // No need to add zeros to yc if shorter as subtract only needs to start at yc.length. if (b > 0) for (; b--; xc[i++] = 0); b = BASE - 1; // Subtract yc from xc. for (; j > a;) { if (xc[--j] < yc[j]) { for (i = j; i && !xc[--i]; xc[i] = b); --xc[i]; xc[j] += BASE; } xc[j] -= yc[j]; } // Remove leading zeros and adjust exponent accordingly. for (; xc[0] == 0; xc.splice(0, 1), --ye); // Zero? if (!xc[0]) { // Following IEEE 754 (2008) 6.3, // n - n = +0 but n - n = -0 when rounding towards -Infinity. y.s = ROUNDING_MODE == 3 ? -1 : 1; y.c = [y.e = 0]; return y; } // No need to check for Infinity as +x - +y != Infinity && -x - -y != Infinity // for finite x and y. return normalise(y, xc, ye); }; /* * n % 0 = N * n % N = N * n % I = n * 0 % n = 0 * -0 % n = -0 * 0 % 0 = N * 0 % N = N * 0 % I = 0 * N % n = N * N % 0 = N * N % N = N * N % I = N * I % n = N * I % 0 = N * I % N = N * I % I = N * * Return a new BigNumber whose value is the value of this BigNumber modulo the value of * BigNumber(y, b). The result depends on the value of MODULO_MODE. */ P.modulo = P.mod = function (y, b) { var q, s, x = this; y = new BigNumber(y, b); // Return NaN if x is Infinity or NaN, or y is NaN or zero. if (!x.c || !y.s || y.c && !y.c[0]) { return new BigNumber(NaN); // Return x if y is Infinity or x is zero. } else if (!y.c || x.c && !x.c[0]) { return new BigNumber(x); } if (MODULO_MODE == 9) { // Euclidian division: q = sign(y) * floor(x / abs(y)) // r = x - qy where 0 <= r < abs(y) s = y.s; y.s = 1; q = div(x, y, 0, 3); y.s = s; q.s *= s; } else { q = div(x, y, 0, MODULO_MODE); } y = x.minus(q.times(y)); // To match JavaScript %, ensure sign of zero is sign of dividend. if (!y.c[0] && MODULO_MODE == 1) y.s = x.s; return y; }; /* * n * 0 = 0 * n * N = N * n * I = I * 0 * n = 0 * 0 * 0 = 0 * 0 * N = N * 0 * I = N * N * n = N * N * 0 = N * N * N = N * N * I = N * I * n = I * I * 0 = N * I * N = N * I * I = I * * Return a new BigNumber whose value is the value of this BigNumber multiplied by the value * of BigNumber(y, b). */ P.multipliedBy = P.times = function (y, b) { var c, e, i, j, k, m, xcL, xlo, xhi, ycL, ylo, yhi, zc, base, sqrtBase, x = this, xc = x.c, yc = (y = new BigNumber(y, b)).c; // Either NaN, ±Infinity or ±0? if (!xc || !yc || !xc[0] || !yc[0]) { // Return NaN if either is NaN, or one is 0 and the other is Infinity. if (!x.s || !y.s || xc && !xc[0] && !yc || yc && !yc[0] && !xc) { y.c = y.e = y.s = null; } else { y.s *= x.s; // Return ±Infinity if either is ±Infinity. if (!xc || !yc) { y.c = y.e = null; // Return ±0 if either is ±0. } else { y.c = [0]; y.e = 0; } } return y; } e = bitFloor(x.e / LOG_BASE) + bitFloor(y.e / LOG_BASE); y.s *= x.s; xcL = xc.length; ycL = yc.length; // Ensure xc points to longer array and xcL to its length. if (xcL < ycL) zc = xc, xc = yc, yc = zc, i = xcL, xcL = ycL, ycL = i; // Initialise the result array with zeros. for (i = xcL + ycL, zc = []; i--; zc.push(0)); base = BASE; sqrtBase = SQRT_BASE; for (i = ycL; --i >= 0;) { c = 0; ylo = yc[i] % sqrtBase; yhi = yc[i] / sqrtBase | 0; for (k = xcL, j = i + k; j > i;) { xlo = xc[--k] % sqrtBase; xhi = xc[k] / sqrtBase | 0; m = yhi * xlo + xhi * ylo; xlo = ylo * xlo + ((m % sqrtBase) * sqrtBase) + zc[j] + c; c = (xlo / base | 0) + (m / sqrtBase | 0) + yhi * xhi; zc[j--] = xlo % base; } zc[j] = c; } if (c) { ++e; } else { zc.splice(0, 1); } return normalise(y, zc, e); }; /* * Return a new BigNumber whose value is the value of this BigNumber negated, * i.e. multiplied by -1. */ P.negated = function () { var x = new BigNumber(this); x.s = -x.s || null; return x; }; /* * n + 0 = n * n + N = N * n + I = I * 0 + n = n * 0 + 0 = 0 * 0 + N = N * 0 + I = I * N + n = N * N + 0 = N * N + N = N * N + I = N * I + n = I * I + 0 = I * I + N = N * I + I = I * * Return a new BigNumber whose value is the value of this BigNumber plus the value of * BigNumber(y, b). */ P.plus = function (y, b) { var t, x = this, a = x.s; y = new BigNumber(y, b); b = y.s; // Either NaN? if (!a || !b) return new BigNumber(NaN); // Signs differ? if (a != b) { y.s = -b; return x.minus(y); } var xe = x.e / LOG_BASE, ye = y.e / LOG_BASE, xc = x.c, yc = y.c; if (!xe || !ye) { // Return ±Infinity if either ±Infinity. if (!xc || !yc) return new BigNumber(a / 0); // Either zero? // Return y if y is non-zero, x if x is non-zero, or zero if both are zero. if (!xc[0] || !yc[0]) return yc[0] ? y : new BigNumber(xc[0] ? x : a * 0); } xe = bitFloor(xe); ye = bitFloor(ye); xc = xc.slice(); // Prepend zeros to equalise exponents. Faster to use reverse then do unshifts. if (a = xe - ye) { if (a > 0) { ye = xe; t = yc; } else { a = -a; t = xc; } t.reverse(); for (; a--; t.push(0)); t.reverse(); } a = xc.length; b = yc.length; // Point xc to the longer array, and b to the shorter length. if (a - b < 0) t = yc, yc = xc, xc = t, b = a; // Only start adding at yc.length - 1 as the further digits of xc can be ignored. for (a = 0; b;) { a = (xc[--b] = xc[b] + yc[b] + a) / BASE | 0; xc[b] = BASE === xc[b] ? 0 : xc[b] % BASE; } if (a) { xc = [a].concat(xc); ++ye; } // No need to check for zero, as +x + +y != 0 && -x + -y != 0 // ye = MAX_EXP + 1 possible return normalise(y, xc, ye); }; /* * If sd is undefined or null or true or false, return the number of significant digits of * the value of this BigNumber, or null if the value of this BigNumber is ±Infinity or NaN. * If sd is true include integer-part trailing zeros in the count. * * Otherwise, if sd is a number, return a new BigNumber whose value is the value of this * BigNumber rounded to a maximum of sd significant digits using rounding mode rm, or * ROUNDING_MODE if rm is omitted. * * sd {number|boolean} number: significant digits: integer, 1 to MAX inclusive. * boolean: whether to count integer-part trailing zeros: true or false. * [rm] {number} Rounding mode. Integer, 0 to 8 inclusive. * * '[BigNumber Error] Argument {not a primitive number|not an integer|out of range}: {sd|rm}' */ P.precision = P.sd = function (sd, rm) { var c, n, v, x = this; if (sd != null && sd !== !!sd) { intCheck(sd, 1, MAX); if (rm == null) rm = ROUNDING_MODE; else intCheck(rm, 0, 8); return round(new BigNumber(x), sd, rm); } if (!(c = x.c)) return null; v = c.length - 1; n = v * LOG_BASE + 1; if (v = c[v]) { // Subtract the number of trailing zeros of the last element. for (; v % 10 == 0; v /= 10, n--); // Add the number of digits of the first element. for (v = c[0]; v >= 10; v /= 10, n++); } if (sd && x.e + 1 > n) n = x.e + 1; return n; }; /* * Return a new BigNumber whose value is the value of this BigNumber shifted by k places * (powers of 10). Shift to the right if n > 0, and to the left if n < 0. * * k {number} Integer, -MAX_SAFE_INTEGER to MAX_SAFE_INTEGER inclusive. * * '[BigNumber Error] Argument {not a primitive number|not an integer|out of range}: {k}' */ P.shiftedBy = function (k) { intCheck(k, -MAX_SAFE_INTEGER, MAX_SAFE_INTEGER); return this.times('1e' + k); }; /* * sqrt(-n) = N * sqrt(N) = N * sqrt(-I) = N * sqrt(I) = I * sqrt(0) = 0 * sqrt(-0) = -0 * * Return a new BigNumber whose value is the square root of the value of this BigNumber, * rounded according to DECIMAL_PLACES and ROUNDING_MODE. */ P.squareRoot = P.sqrt = function () { var m, n, r, rep, t, x = this, c = x.c, s = x.s, e = x.e, dp = DECIMAL_PLACES + 4, half = new BigNumber('0.5'); // Negative/NaN/Infinity/zero? if (s !== 1 || !c || !c[0]) { return new BigNumber(!s || s < 0 && (!c || c[0]) ? NaN : c ? x : 1 / 0); } // Initial estimate. s = Math.sqrt(+valueOf(x)); // Math.sqrt underflow/overflow? // Pass x to Math.sqrt as integer, then adjust the exponent of the result. if (s == 0 || s == 1 / 0) { n = coeffToString(c); if ((n.length + e) % 2 == 0) n += '0'; s = Math.sqrt(+n); e = bitFloor((e + 1) / 2) - (e < 0 || e % 2); if (s == 1 / 0) { n = '5e' + e; } else { n = s.toExponential(); n = n.slice(0, n.indexOf('e') + 1) + e; } r = new BigNumber(n); } else { r = new BigNumber(s + ''); } // Check for zero. // r could be zero if MIN_EXP is changed after the this value was created. // This would cause a division by zero (x/t) and hence Infinity below, which would cause // coeffToString to throw. if (r.c[0]) { e = r.e; s = e + dp; if (s < 3) s = 0; // Newton-Raphson iteration. for (; ;) { t = r; r = half.times(t.plus(div(x, t, dp, 1))); if (coeffToString(t.c).slice(0, s) === (n = coeffToString(r.c)).slice(0, s)) { // The exponent of r may here be one less than the final result exponent, // e.g 0.0009999 (e-4) --> 0.001 (e-3), so adjust s so the rounding digits // are indexed correctly. if (r.e < e) --s; n = n.slice(s - 3, s + 1); // The 4th rounding digit may be in error by -1 so if the 4 rounding digits // are 9999 or 4999 (i.e. approaching a rounding boundary) continue the // iteration. if (n == '9999' || !rep && n == '4999') { // On the first iteration only, check to see if rounding up gives the // exact result as the nines may infinitely repeat. if (!rep) { round(t, t.e + DECIMAL_PLACES + 2, 0); if (t.times(t).eq(x)) { r = t; break; } } dp += 4; s += 4; rep = 1; } else { // If rounding digits are null, 0{0,4} or 50{0,3}, check for exact // result. If not, then there are further digits and m will be truthy. if (!+n || !+n.slice(1) && n.charAt(0) == '5') { // Truncate to the first rounding digit. round(r, r.e + DECIMAL_PLACES + 2, 1); m = !r.times(r).eq(x); } break; } } } } return round(r, r.e + DECIMAL_PLACES + 1, ROUNDING_MODE, m); }; /* * Return a string representing the value of this BigNumber in exponential notation and * rounded using ROUNDING_MODE to dp fixed decimal places. * * [dp] {number} Decimal places. Integer, 0 to MAX inclusive. * [rm] {number} Rounding mode. Integer, 0 to 8 inclusive. * * '[BigNumber Error] Argument {not a primitive number|not an integer|out of range}: {dp|rm}' */ P.toExponential = function (dp, rm) { if (dp != null) { intCheck(dp, 0, MAX); dp++; } return format(this, dp, rm, 1); }; /* * Return a string representing the value of this BigNumber in fixed-point notation rounding * to dp fixed decimal places using rounding mode rm, or ROUNDING_MODE if rm is omitted. * * Note: as with JavaScript's number type, (-0).toFixed(0) is '0', * but e.g. (-0.00001).toFixed(0) is '-0'. * * [dp] {number} Decimal places. Integer, 0 to MAX inclusive. * [rm] {number} Rounding mode. Integer, 0 to 8 inclusive. * * '[BigNumber Error] Argument {not a primitive number|not an integer|out of range}: {dp|rm}' */ P.toFixed = function (dp, rm) { if (dp != null) { intCheck(dp, 0, MAX); dp = dp + this.e + 1; } return format(this, dp, rm); }; /* * Return a string representing the value of this BigNumber in fixed-point notation rounded * using rm or ROUNDING_MODE to dp decimal places, and formatted according to the properties * of the format or FORMAT object (see BigNumber.set). * * The formatting object may contain some or all of the properties shown below. * * FORMAT = { * prefix: '', * groupSize: 3, * secondaryGroupSize: 0, * groupSeparator: ',', * decimalSeparator: '.', * fractionGroupSize: 0, * fractionGroupSeparator: '\xA0', // non-breaking space * suffix: '' * }; * * [dp] {number} Decimal places. Integer, 0 to MAX inclusive. * [rm] {number} Rounding mode. Integer, 0 to 8 inclusive. * [format] {object} Formatting options. See FORMAT pbject above. * * '[BigNumber Error] Argument {not a primitive number|not an integer|out of range}: {dp|rm}' * '[BigNumber Error] Argument not an object: {format}' */ P.toFormat = function (dp, rm, format) { var str, x = this; if (format == null) { if (dp != null && rm && typeof rm == 'object') { format = rm; rm = null; } else if (dp && typeof dp == 'object') { format = dp; dp = rm = null; } else { format = FORMAT; } } else if (typeof format != 'object') { throw Error (bignumberError + 'Argument not an object: ' + format); } str = x.toFixed(dp, rm); if (x.c) { var i, arr = str.split('.'), g1 = +format.groupSize, g2 = +format.secondaryGroupSize, groupSeparator = format.groupSeparator || '', intPart = arr[0], fractionPart = arr[1], isNeg = x.s < 0, intDigits = isNeg ? intPart.slice(1) : intPart, len = intDigits.length; if (g2) i = g1, g1 = g2, g2 = i, len -= i; if (g1 > 0 && len > 0) { i = len % g1 || g1; intPart = intDigits.substr(0, i); for (; i < len; i += g1) intPart += groupSeparator + intDigits.substr(i, g1); if (g2 > 0) intPart += groupSeparator + intDigits.slice(i); if (isNeg) intPart = '-' + intPart; } str = fractionPart ? intPart + (format.decimalSeparator || '') + ((g2 = +format.fractionGroupSize) ? fractionPart.replace(new RegExp('\\d{' + g2 + '}\\B', 'g'), '$&' + (format.fractionGroupSeparator || '')) : fractionPart) : intPart; } return (format.prefix || '') + str + (format.suffix || ''); }; /* * Return an array of two BigNumbers representing the value of this BigNumber as a simple * fraction with an integer numerator and an integer denominator. * The denominator will be a positive non-zero value less than or equal to the specified * maximum denominator. If a maximum denominator is not specified, the denominator will be * the lowest value necessary to represent the number exactly. * * [md] {number|string|BigNumber} Integer >= 1, or Infinity. The maximum denominator. * * '[BigNumber Error] Argument {not an integer|out of range} : {md}' */ P.toFraction = function (md) { var d, d0, d1, d2, e, exp, n, n0, n1, q, r, s, x = this, xc = x.c; if (md != null) { n = new BigNumber(md); // Throw if md is less than one or is not an integer, unless it is Infinity. if (!n.isInteger() && (n.c || n.s !== 1) || n.lt(ONE)) { throw Error (bignumberError + 'Argument ' + (n.isInteger() ? 'out of range: ' : 'not an integer: ') + valueOf(n)); } } if (!xc) return new BigNumber(x); d = new BigNumber(ONE); n1 = d0 = new BigNumber(ONE); d1 = n0 = new BigNumber(ONE); s = coeffToString(xc); // Determine initial denominator. // d is a power of 10 and the minimum max denominator that specifies the value exactly. e = d.e = s.length - x.e - 1; d.c[0] = POWS_TEN[(exp = e % LOG_BASE) < 0 ? LOG_BASE + exp : exp]; md = !md || n.comparedTo(d) > 0 ? (e > 0 ? d : n1) : n; exp = MAX_EXP; MAX_EXP = 1 / 0; n = new BigNumber(s); // n0 = d1 = 0 n0.c[0] = 0; for (; ;) { q = div(n, d, 0, 1); d2 = d0.plus(q.times(d1)); if (d2.comparedTo(md) == 1) break; d0 = d1; d1 = d2; n1 = n0.plus(q.times(d2 = n1)); n0 = d2; d = n.minus(q.times(d2 = d)); n = d2; } d2 = div(md.minus(d0), d1, 0, 1); n0 = n0.plus(d2.times(n1)); d0 = d0.plus(d2.times(d1)); n0.s = n1.s = x.s; e = e * 2; // Determine which fraction is closer to x, n0/d0 or n1/d1 r = div(n1, d1, e, ROUNDING_MODE).minus(x).abs().comparedTo( div(n0, d0, e, ROUNDING_MODE).minus(x).abs()) < 1 ? [n1, d1] : [n0, d0]; MAX_EXP = exp; return r; }; /* * Return the value of this BigNumber converted to a number primitive. */ P.toNumber = function () { return +valueOf(this); }; /* * Return a string representing the value of this BigNumber rounded to sd significant digits * using rounding mode rm or ROUNDING_MODE. If sd is less than the number of digits * necessary to represent the integer part of the value in fixed-point notation, then use * exponential notation. * * [sd] {number} Significant digits. Integer, 1 to MAX inclusive. * [rm] {number} Rounding mode. Integer, 0 to 8 inclusive. * * '[BigNumber Error] Argument {not a primitive number|not an integer|out of range}: {sd|rm}' */ P.toPrecision = function (sd, rm) { if (sd != null) intCheck(sd, 1, MAX); return format(this, sd, rm, 2); }; /* * Return a string representing the value of this BigNumber in base b, or base 10 if b is * omitted. If a base is specified, including base 10, round according to DECIMAL_PLACES and * ROUNDING_MODE. If a base is not specified, and this BigNumber has a positive exponent * that is equal to or greater than TO_EXP_POS, or a negative exponent equal to or less than * TO_EXP_NEG, return exponential notation. * * [b] {number} Integer, 2 to ALPHABET.length inclusive. * * '[BigNumber Error] Base {not a primitive number|not an integer|out of range}: {b}' */ P.toString = function (b) { var str, n = this, s = n.s, e = n.e; // Infinity or NaN? if (e === null) { if (s) { str = 'Infinity'; if (s < 0) str = '-' + str; } else { str = 'NaN'; } } else { if (b == null) { str = e <= TO_EXP_NEG || e >= TO_EXP_POS ? toExponential(coeffToString(n.c), e) : toFixedPoint(coeffToString(n.c), e, '0'); } else if (b === 10 && alphabetHasNormalDecimalDigits) { n = round(new BigNumber(n), DECIMAL_PLACES + e + 1, ROUNDING_MODE); str = toFixedPoint(coeffToString(n.c), n.e, '0'); } else { intCheck(b, 2, ALPHABET.length, 'Base'); str = convertBase(toFixedPoint(coeffToString(n.c), e, '0'), 10, b, s, true); } if (s < 0 && n.c[0]) str = '-' + str; } return str; }; /* * Return as toString, but do not accept a base argument, and include the minus sign for * negative zero. */ P.valueOf = P.toJSON = function () { return valueOf(this); }; P._isBigNumber = true; P[Symbol.toStringTag] = 'BigNumber'; // Node.js v10.12.0+ P[Symbol.for('nodejs.util.inspect.custom')] = P.valueOf; if (configObject != null) BigNumber.set(configObject); return BigNumber; } // PRIVATE HELPER FUNCTIONS // These functions don't need access to variables, // e.g. DECIMAL_PLACES, in the scope of the `clone` function above. function bitFloor(n) { var i = n | 0; return n > 0 || n === i ? i : i - 1; } // Return a coefficient array as a string of base 10 digits. function coeffToString(a) { var s, z, i = 1, j = a.length, r = a[0] + ''; for (; i < j;) { s = a[i++] + ''; z = LOG_BASE - s.length; for (; z--; s = '0' + s); r += s; } // Determine trailing zeros. for (j = r.length; r.charCodeAt(--j) === 48;); return r.slice(0, j + 1 || 1); } // Compare the value of BigNumbers x and y. function compare(x, y) { var a, b, xc = x.c, yc = y.c, i = x.s, j = y.s, k = x.e, l = y.e; // Either NaN? if (!i || !j) return null; a = xc && !xc[0]; b = yc && !yc[0]; // Either zero? if (a || b) return a ? b ? 0 : -j : i; // Signs differ? if (i != j) return i; a = i < 0; b = k == l; // Either Infinity? if (!xc || !yc) return b ? 0 : !xc ^ a ? 1 : -1; // Compare exponents. if (!b) return k > l ^ a ? 1 : -1; j = (k = xc.length) < (l = yc.length) ? k : l; // Compare digit by digit. for (i = 0; i < j; i++) if (xc[i] != yc[i]) return xc[i] > yc[i] ^ a ? 1 : -1; // Compare lengths. return k == l ? 0 : k > l ^ a ? 1 : -1; } /* * Check that n is a primitive number, an integer, and in range, otherwise throw. */ function intCheck(n, min, max, name) { if (n < min || n > max || n !== mathfloor(n)) { throw Error (bignumberError + (name || 'Argument') + (typeof n == 'number' ? n < min || n > max ? ' out of range: ' : ' not an integer: ' : ' not a primitive number: ') + String(n)); } } // Assumes finite n. function isOdd(n) { var k = n.c.length - 1; return bitFloor(n.e / LOG_BASE) == k && n.c[k] % 2 != 0; } function toExponential(str, e) { return (str.length > 1 ? str.charAt(0) + '.' + str.slice(1) : str) + (e < 0 ? 'e' : 'e+') + e; } function toFixedPoint(str, e, z) { var len, zs; // Negative exponent? if (e < 0) { // Prepend zeros. for (zs = z + '.'; ++e; zs += z); str = zs + str; // Positive exponent } else { len = str.length; // Append zeros. if (++e > len) { for (zs = z, e -= len; --e; zs += z); str += zs; } else if (e < len) { str = str.slice(0, e) + '.' + str.slice(e); } } return str; } // EXPORT var BigNumber = clone(); // src/index.ts var SplayTreeNode = class { key; left = null; right = null; constructor(key) { this.key = key; } }; var SplayTreeSetNode = class extends SplayTreeNode { constructor(key) { super(key); } }; var SplayTree = class { size = 0; modificationCount = 0; splayCount = 0; splay(key) { const root = this.root; if (root == null) { this.compare(key, key); return -1; } let right = null; let newTreeRight = null; let left = null; let newTreeLeft = null; let current = root; const compare = this.compare; let comp; while (true) { comp = compare(current.key, key); if (comp > 0) { let currentLeft = current.left; if (currentLeft == null) break; comp = compare(currentLeft.key, key); if (comp > 0) { current.left = currentLeft.right; currentLeft.right = current; current = currentLeft; currentLeft = current.left; if (currentLeft == null) break; } if (right == null) { newTreeRight = current; } else { right.left = current; } right = current; current = currentLeft; } else if (comp < 0) { let currentRight = current.right; if (currentRight == null) break; comp = compare(currentRight.key, key); if (comp < 0) { current.right = currentRight.left; currentRight.left = current; current = currentRight; currentRight = current.right; if (currentRight == null) break; } if (left == null) { newTreeLeft = current; } else { left.right = current; } left = current; current = currentRight; } else { break; } } if (left != null) { left.right = current.left; current.left = newTreeLeft; } if (right != null) { right.left = current.right; current.right = newTreeRight; } if (this.root !== current) { this.root = current; this.splayCount++; } return comp; } splayMin(node) { let current = node; let nextLeft = current.left; while (nextLeft != null) { const left = nextLeft; current.left = left.right; left.right = current; current = left; nextLeft = current.left; } return current; } splayMax(node) { let current = node; let nextRight = current.right; while (nextRight != null) { const right = nextRight; current.right = right.left; right.left = current; current = right; nextRight = current.right; } return current; } _delete(key) { if (this.root == null) return null; const comp = this.splay(key); if (comp != 0) return null; let root = this.root; const result = root; const left = root.left; this.size--; if (left == null) { this.root = root.right; } else { const right = root.right; root = this.splayMax(left); root.right = right; this.root = root; } this.modificationCount++; return result; } addNewRoot(node, comp) { this.size++; this.modificationCount++; const root = this.root; if (root == null) { this.root = node; return; } if (comp < 0) { node.left = root; node.right = root.right; root.right = null; } else { node.right = root; node.left = root.left; root.left = null; } this.root = node; } _first() { const root = this.root; if (root == null) return null; this.root = this.splayMin(root); return this.root; } _last() { const root = this.root; if (root == null) return null; this.root = this.splayMax(root); return this.root; } clear() { this.root = null; this.size = 0; this.modificationCount++; } has(key) { return this.validKey(key) && this.splay(key) == 0; } defaultCompare() { return (a, b) => a < b ? -1 : a > b ? 1 : 0; } wrap() { return { getRoot: () => { return this.root; }, setRoot: (root) => { this.root = root; }, getSize: () => { return this.size; }, getModificationCount: () => { return this.modificationCount; }, getSplayCount: () => { return this.splayCount; }, setSplayCount: (count) => { this.splayCount = count; }, splay: (key) => { return this.splay(key); }, has: (key) => { return this.has(key); } }; } }; var SplayTreeSet = class _SplayTreeSet extends SplayTree { root = null; compare; validKey; constructor(compare, isValidKey) { super(); this.compare = compare ?? this.defaultCompare(); this.validKey = isValidKey ?? ((v) => v != null && v != void 0); } delete(element) { if (!this.validKey(element)) return false; return this._delete(element) != null; } deleteAll(elements) { for (const element of elements) { this.delete(element); } } forEach(f) { const nodes = this[Symbol.iterator](); let result; while (result = nodes.next(), !result.done) { f(result.value, result.value, this); } } add(element) { const compare = this.splay(element); if (compare != 0) this.addNewRoot(new SplayTreeSetNode(element), compare); return this; } addAndReturn(element) { const compare = this.splay(element); if (compare != 0) this.addNewRoot(new SplayTreeSetNode(element), compare); return this.root.key; } addAll(elements) { for (const element of elements) { this.add(element); } } isEmpty() { return this.root == null; } isNotEmpty() { return this.root != null; } single() { if (this.size == 0) throw "Bad state: No element"; if (this.size > 1) throw "Bad state: Too many element"; return this.root.key; } first() { if (this.size == 0) throw "Bad state: No element"; return this._first().key; } last() { if (this.size == 0) throw "Bad state: No element"; return this._last().key; } lastBefore(element) { if (element == null) throw "Invalid arguments(s)"; if (this.root == null) return null; const comp = this.splay(element); if (comp < 0) return this.root.key; let node = this.root.left; if (node == null) return null; let nodeRight = node.right; while (nodeRight != null) { node = nodeRight; nodeRight = node.right; } return node.key; } firstAfter(element) { if (element == null) throw "Invalid arguments(s)"; if (this.root == null) return null; const comp = this.splay(element); if (comp > 0) return this.root.key; let node = this.root.right; if (node == null) return null; let nodeLeft = node.left; while (nodeLeft != null) { node = nodeLeft; nodeLeft = node.left; } return node.key; } retainAll(elements) { const retainSet = new _SplayTreeSet(this.compare, this.validKey); const modificationCount = this.modificationCount; for (const object of elements) { if (modificationCount != this.modificationCount) { throw "Concurrent modification during iteration."; } if (this.validKey(object) && this.splay(object) == 0) { retainSet.add(this.root.key); } } if (retainSet.size != this.size) { this.root = retainSet.root; this.size = retainSet.size; this.modificationCount++; } } lookup(object) { if (!this.validKey(object)) return null; const comp = this.splay(object); if (comp != 0) return null; return this.root.key; } intersection(other) { const result = new _SplayTreeSet(this.compare, this.validKey); for (const element of this) { if (other.has(element)) result.add(element); } return result; } difference(other) { const result = new _SplayTreeSet(this.compare, this.validKey); for (const element of this) { if (!other.has(element)) result.add(element); } return result; } union(other) { const u = this.clone(); u.addAll(other); return u; } clone() { const set = new _SplayTreeSet(this.compare, this.validKey); set.size = this.size; set.root = this.copyNode(this.root); return set; } copyNode(node) { if (node == null) return null; function copyChildren(node2, dest) { let left; let right; do { left = node2.left; right = node2.right; if (left != null) { const newLeft = new SplayTreeSetNode(left.key); dest.left = newLeft; copyChildren(left, newLeft); } if (right != null) { const newRight = new SplayTreeSetNode(right.key); dest.right = newRight; node2 = right; dest = newRight; } } while (right != null); } const result = new SplayTreeSetNode(node.key); copyChildren(node, result); return result; } toSet() { return this.clone(); } entries() { return new SplayTreeSetEntryIterableIterator(this.wrap()); } keys() { return this[Symbol.iterator](); } values() { return this[Symbol.iterator](); } [Symbol.iterator]() { return new SplayTreeKeyIterableIterator(this.wrap()); } [Symbol.toStringTag] = "[object Set]"; }; var SplayTreeIterableIterator = class { tree; path = new Array(); modificationCount = null; splayCount; constructor(tree) { this.tree = tree; this.splayCount = tree.getSplayCount(); } [Symbol.iterator]() { return this; } next() { if (this.moveNext()) return { done: false, value: this.current() }; return { done: true, value: null }; } current() { if (!this.path.length) return null; const node = this.path[this.path.length - 1]; return this.getValue(node); } rebuildPath(key) { this.path.splice(0, this.path.length); this.tree.splay(key); this.path.push(this.tree.getRoot()); this.splayCount = this.tree.getSplayCount(); } findLeftMostDescendent(node) { while (node != null) { this.path.push(node); node = node.left; } } moveNext() { if (this.modificationCount != this.tree.getModificationCount()) { if (this.modificationCount == null) { this.modificationCount = this.tree.getModificationCount(); let node2 = this.tree.getRoot(); while (node2 != null) { this.path.push(node2); node2 = node2.left; } return this.path.length > 0; } throw "Concurrent modification during iteration."; } if (!this.path.length) return false; if (this.splayCount != this.tree.getSplayCount()) { this.rebuildPath(this.path[this.path.length - 1].key); } let node = this.path[this.path.length - 1]; let next = node.right; if (next != null) { while (next != null) { this.path.push(next); next = next.left; } return true; } this.path.pop(); while (this.path.length && this.path[this.path.length - 1].right === node) { node = this.path.pop(); } return this.path.length > 0; } }; var SplayTreeKeyIterableIterator = class extends SplayTreeIterableIterator { getValue(node) { return node.key; } }; var SplayTreeSetEntryIterableIterator = class extends SplayTreeIterableIterator { getValue(node) { return [node.key, node.key]; } }; var identity = (x) => { return x; }; var snap = (eps) => { if (eps) { const xTree = new SplayTreeSet(compare$1(eps)); const yTree = new SplayTreeSet(compare$1(eps)); const snapCoord = (coord, tree) => { return tree.addAndReturn(coord); }; const snap = (v) => { return { x: snapCoord(v.x, xTree), y: snapCoord(v.y, yTree), }; }; snap({ x: new BigNumber(0), y: new BigNumber(0) }); return snap; } return identity; }; const set = (eps) => { return { set: (eps) => { precision = set(eps); }, reset: () => set(eps), compare: compare$1(eps), snap: snap(eps), orient: orient(eps) }; }; let precision = set(); /** * A bounding box has the format: * * { ll: { x: xmin, y: ymin }, ur: { x: xmax, y: ymax } } * */ const isInBbox = (bbox, point) => { return (bbox.ll.x.isLessThanOrEqualTo(point.x) && point.x.isLessThanOrEqualTo(bbox.ur.x) && bbox.ll.y.isLessThanOrEqualTo(point.y) && point.y.isLessThanOrEqualTo(bbox.ur.y)); }; /* Returns either null, or a bbox (aka an ordered pair of points) * If there is only one point of overlap, a bbox with identical points * will be returned */ const getBboxOverlap = (b1, b2) => { // check if the bboxes overlap at all if (b2.ur.x.isLessThan(b1.ll.x) || b1.ur.x.isLessThan(b2.ll.x) || b2.ur.y.isLessThan(b1.ll.y) || b1.ur.y.isLessThan(b2.ll.y)) return null; // find the middle two X values const lowerX = b1.ll.x.isLessThan(b2.ll.x) ? b2.ll.x : b1.ll.x; const upperX = b1.ur.x.isLessThan(b2.ur.x) ? b1.ur.x : b2.ur.x; // find the middle two Y values const lowerY = b1.ll.y.isLessThan(b2.ll.y) ? b2.ll.y : b1.ll.y; const upperY = b1.ur.y.isLessThan(b2.ur.y) ? b1.ur.y : b2.ur.y; // put those middle values together to get the overlap return { ll: { x: lowerX, y: lowerY }, ur: { x: upperX, y: upperY } }; }; /* Cross Product of two vectors with first point at origin */ const crossProduct = (a, b) => a.x.times(b.y).minus(a.y.times(b.x)); /* Dot Product of two vectors with first point at origin */ const dotProduct = (a, b) => a.x.times(b.x).plus(a.y.times(b.y)); const length = (v) => dotProduct(v, v).sqrt(); /* Get the sine of the angle from pShared -> pAngle to pShaed -> pBase */ const sineOfAngle = (pShared, pBase, pAngle) => { const vBase = { x: pBase.x.minus(pShared.x), y: pBase.y.minus(pShared.y) }; const vAngle = { x: pAngle.x.minus(pShared.x), y: pAngle.y.minus(pShared.y) }; return crossProduct(vAngle, vBase).div(length(vAngle)).div(length(vBase)); }; /* Get the cosine of the angle from pShared -> pAngle to pShaed -> pBase */ const cosineOfAngle = (pShared, pBase, pAngle) => { const vBase = { x: pBase.x.minus(pShared.x), y: pBase.y.minus(pShared.y) }; const vAngle = { x: pAngle.x.minus(pShared.x), y: pAngle.y.minus(pShared.y) }; return dotProduct(vAngle, vBase).div(length(vAngle)).div(length(vBase)); }; /* Get the x coordinate where the given line (defined by a point and vector) * crosses the horizontal line with the given y coordiante. * In the case of parrallel lines (including overlapping ones) returns null. */ const horizontalIntersection = (pt, v, y) => { if (v.y.isZero()) return null; return { x: pt.x.plus((v.x.div(v.y)).times(y.minus(pt.y))), y: y }; }; /* Get the y coordinate where the given line (defined by a point and vector) * crosses the vertical line with the given x coordiante. * In the case of parrallel lines (including overlapping ones) returns null. */ const verticalIntersection = (pt, v, x) => { if (v.x.isZero()) return null; return { x: x, y: pt.y.plus((v.y.div(v.x)).times(x.minus(pt.x))) }; }; /* Get the intersection of two lines, each defined by a base point and a vector. * In the case of parrallel lines (including overlapping ones) returns null. */ const intersection$1 = (pt1, v1, pt2, v2) => { // take some shortcuts for vertical and horizontal lines // this also ensures we don't calculate an intersection and then discover // it's actually outside the bounding box of the line if (v1.x.isZero()) return verticalIntersection(pt2, v2, pt1.x); if (v2.x.isZero()) return verticalIntersection(pt1, v1, pt2.x); if (v1.y.isZero()) return horizontalIntersection(pt2, v2, pt1.y); if (v2.y.isZero()) return horizontalIntersection(pt1, v1, pt2.y); // General case for non-overlapping segments. // This algorithm is based on Schneider and Eberly. // http://www.cimec.org.ar/~ncalvo/Schneider_Eberly.pdf - pg 244 const kross = crossProduct(v1, v2); if (kross.isZero()) return null; const ve = { x: pt2.x.minus(pt1.x), y: pt2.y.minus(pt1.y) }; const d1 = crossProduct(ve, v1).div(kross); const d2 = crossProduct(ve, v2).div(kross); // take the average of the two calculations to minimize rounding error const x1 = pt1.x.plus(d2.times(v1.x)), x2 = pt2.x.plus(d1.times(v2.x)); const y1 = pt1.y.plus(d2.times(v1.y)), y2 = pt2.y.plus(d1.times(v2.y)); const x = x1.plus(x2).div(2); const y = y1.plus(y2).div(2); return { x: x, y: y }; }; class SweepEvent { point; isLeft; segment; otherSE; consumedBy; // for ordering sweep events in the sweep event queue static compare(a, b) { // favor event with a point that the sweep line hits first const ptCmp = SweepEvent.comparePoints(a.point, b.point); if (ptCmp !== 0) return ptCmp; // the points are the same, so link them if needed if (a.point !== b.point) a.link(b); // favor right events over left if (a.isLeft !== b.isLeft) return a.isLeft ? 1 : -1; // we have two matching left or right endpoints // ordering of this case is the same as for their segments return Segment.compare(a.segment, b.segment); } // for ordering points in sweep line order static comparePoints(aPt, bPt) { if (aPt.x.isLessThan(bPt.x)) return -1; if (aPt.x.isGreaterThan(bPt.x)) return 1; if (aPt.y.isLessThan(bPt.y)) return -1; if (aPt.y.isGreaterThan(bPt.y)) return 1; return 0; } // Warning: 'point' input will be modified and re-used (for performance) constructor(point, isLeft) { if (point.events === undefined) point.events = [this]; else point.events.push(this); this.point = point; this.isLeft = isLeft; // this.segment, this.otherSE set by factory } link(other) { if (other.point === this.point) { throw new Error("Tried to link already linked events"); } const otherEvents = other.point.events; for (let i = 0, iMax = otherEvents.length; i < iMax; i++) { const evt = otherEvents[i]; this.point.events.push(evt); evt.point = this.point; } this.checkForConsuming(); } /* Do a pass over our linked events and check to see if any pair * of segments match, and should be consumed. */ checkForConsuming() { // FIXME: The loops in this method run O(n^2) => no good. // Maintain little ordered sweep event trees? // Can we maintaining an ordering that avoids the need // for the re-sorting with getLeftmostComparator in geom-out? // Compare each pair of events to see if other events also match const numEvents = this.point.events.length; for (let i = 0; i < numEvents; i++) { const evt1 = this.point.events[i]; if (evt1.segment.consumedBy !== undefined) continue; for (let j = i + 1; j < numEvents; j++) { const evt2 = this.point.events[j]; if (evt2.consumedBy !== undefined) continue; if (evt1.otherSE.point.events !== evt2.otherSE.point.events) continue; evt1.segment.consume(evt2.segment); } } } getAvailableLinkedEvents() { // point.events is always of length 2 or greater const events = []; for (let i = 0, iMax = this.point.events.length; i < iMax; i++) { const evt = this.point.events[i]; if (evt !== this && !evt.segment.ringOut && evt.segment.isInResult()) { events.push(evt); } } return events; } /** * Returns a comparator function for sorting linked events that will * favor the event that will give us the smallest left-side angle. * All ring construction starts as low as possible heading to the right, * so by always turning left as sharp as possible we'll get polygons * without uncessary loops & holes. * * The comparator function has a compute cache such that it avoids * re-computing already-computed values. */ getLeftmostComparator(baseEvent) { const cache = new Map(); const fillCache = (linkedEvent) => { const nextEvent = linkedEvent.otherSE; cache.set(linkedEvent, { sine: sineOfAngle(this.point, baseEvent.point, nextEvent.point), cosine: cosineOfAngle(this.point, baseEvent.point, nextEvent.point), }); }; return (a, b) => { if (!cache.has(a)) fillCache(a); if (!cache.has(b)) fillCache(b); const { sine: asine, cosine: acosine } = cache.get(a); const { sine: bsine, cosine: bcosine } = cache.get(b); // both on or above x-axis if (asine.isGreaterThanOrEqualTo(0) && bsine.isGreaterThanOrEqualTo(0)) { if (acosine.isLessThan(bcosine)) return 1; if (acosine.isGreaterThan(bcosine)) return -1; return 0; } // both below x-axis if (asine.isLessThan(0) && bsine.isLessThan(0)) { if (acosine.isLessThan(bcosine)) return -1; if (acosine.isGreaterThan(bcosine)) return 1; return 0; } // one above x-axis, one below if (bsine.isLessThan(asine)) return -1; if (bsine.isGreaterThan(asine)) return 1; return 0; }; } } // Give segments unique ID's to get consistent sorting of // segments and sweep events when all else is identical let segmentId = 0; class Segment { id; leftSE; rightSE; rings; windings; ringOut; consumedBy; prev; _prevInResult; _beforeState; _afterState; _isInResult; /* This compare() function is for ordering segments in the sweep * line tree, and does so according to the following criteria: * * Consider the vertical line that lies an infinestimal step to the * right of the right-more of the two left endpoints of the input * segments. Imagine slowly moving a point up from negative infinity * in the increasing y direction. Which of the two segments will that * point intersect first? That segment comes 'before' the other one. * * If neither segment would be intersected by such a line, (if one * or more of the segments are vertical) then the line to be considered * is directly on the right-more of the two left inputs. */ static compare(a, b) { const alx = a.leftSE.point.x; const blx = b.leftSE.point.x; const arx = a.rightSE.point.x; const brx = b.rightSE.point.x; // check if they're even in the same vertical plane if (brx.isLessThan(alx)) return 1; if (arx.isLessThan(blx)) return -1; const aly = a.leftSE.point.y; const bly = b.leftSE.point.y; const ary = a.rightSE.point.y; const bry = b.rightSE.point.y; // is left endpoint of segment B the right-more? if (alx.isLessThan(blx)) { // are the two segments in the same horizontal plane? if (bly.isLessThan(aly) && bly.isLessThan(ary)) return 1; if (bly.isGreaterThan(aly) && bly.isGreaterThan(ary)) return -1; // is the B left endpoint colinear to segment A? const aCmpBLeft = a.comparePoint(b.leftSE.point); if (aCmpBLeft < 0) return 1; if (aCmpBLeft > 0) return -1; // is the A right endpoint colinear to segment B ? const bCmpARight = b.comparePoint(a.rightSE.point); if (bCmpARight !== 0) return bCmpARight; // colinear segments, consider the one with left-more // left endpoint to be first (arbitrary?) return -1; } // is left endpoint of segment A the right-more? if (alx.isGreaterThan(blx)) { if (aly.isLessThan(bly) && aly.isLessThan(bry)) return -1; if (aly.isGreaterThan(bly) && aly.isGreaterThan(bry)) return 1; // is the A left endpoint colinear to segment B? const bCmpALeft = b.comparePoint(a.leftSE.point); if (bCmpALeft !== 0) return bCmpALeft; // is the B right endpoint colinear to segment A? const aCmpBRight = a.comparePoint(b.rightSE.point); if (aCmpBRight < 0) return 1; if (aCmpBRight > 0) return -1; // colinear segments, consider the one with left-more // left endpoint to be first (arbitrary?) return 1; } // if we get here, the two left endpoints are in the same // vertical plane, ie alx === blx // consider the lower left-endpoint to come first if (aly.isLessThan(bly)) return -1; if (aly.isGreaterThan(bly)) return 1; // left endpoints are identical // check for colinearity by using the left-more right endpoint // is the A right endpoint more left-more? if (arx.isLessThan(brx)) { const bCmpARight = b.comparePoint(a.rightSE.point); if (bCmpARight !== 0) return bCmpARight; } // is the B right endpoint more left-more? if (arx.isGreaterThan(brx)) { const aCmpBRight = a.comparePoint(b.rightSE.point); if (aCmpBRight < 0) return 1; if (aCmpBRight > 0) return -1; } if (!arx.eq(brx)) { // are these two [almost] vertical segments with opposite orientation? // if so, the one with the lower right endpoint comes first const ay = ary.minus(aly); const ax = arx.minus(alx); const by = bry.minus(bly); const bx = brx.minus(blx); if (ay.isGreaterThan(ax) && by.isLessThan(bx)) return 1; if (ay.isLessThan(ax) && by.isGreaterThan(bx)) return -1; } // we have colinear segments with matching orientation // consider the one with more left-more right endpoint to be first if (arx.isGreaterThan(brx)) return 1; if (arx.isLessThan(brx)) return -1; // if we get here, two two right endpoints are in the same // vertical plane, ie arx === brx // consider the lower right-endpoint to come first if (ary.isLessThan(bry)) return -1; if (ary.isGreaterThan(bry)) return 1; // right endpoints identical as well, so the segments are idential // fall back on creation order as consistent tie-breaker if (a.id < b.id) return -1; if (a.id > b.id) return 1; // identical segment, ie a === b return 0; } /* Warning: a reference to ringWindings input will be stored, * and possibly will be later modified */ constructor(leftSE, rightSE, rings, windings) { this.id = ++segmentId; this.leftSE = leftSE; leftSE.segment = this; leftSE.otherSE = rightSE; this.rightSE = rightSE; rightSE.segment = this; rightSE.otherSE = leftSE; this.rings = rings; this.windings = windings; // left unset for performance, set later in algorithm // this.ringOut, this.consumedBy, this.prev } static fromRing(pt1, pt2, ring) { let leftPt, rightPt, winding; // ordering the two points according to sweep line ordering const cmpPts = SweepEvent.comparePoints(pt1, pt2); if (cmpPts < 0) { leftPt = pt1; rightPt = pt2; winding = 1; } else if (cmpPts > 0) { leftPt = pt2; rightPt = pt1; winding = -1; } else throw new Error(`Tried to create degenerate segment at [${pt1.x}, ${pt1.y}]`); const leftSE = new SweepEvent(leftPt, true); const rightSE = new SweepEvent(rightPt, false); return new Segment(leftSE, rightSE, [ring], [winding]); } /* When a segment is split, the rightSE is replaced with a new sweep event */ replaceRightSE(newRightSE) { this.rightSE = newRightSE; this.rightSE.segment = this; this.rightSE.otherSE = this.leftSE; this.leftSE.otherSE = this.rightSE; } bbox() { const y1 = this.leftSE.point.y; const y2 = this.rightSE.point.y; return { ll: { x: this.leftSE.point.x, y: y1.isLessThan(y2) ? y1 : y2 }, ur: { x: this.rightSE.point.x, y: y1.isGreaterThan(y2) ? y1 : y2 }, }; } /* A vector from the left point to the right */ vector() { return { x: this.rightSE.point.x.minus(this.leftSE.point.x), y: this.rightSE.point.y.minus(this.leftSE.point.y), }; } isAnEndpoint(pt) { return ((pt.x.eq(this.leftSE.point.x) && pt.y.eq(this.leftSE.point.y)) || (pt.x.eq(this.rightSE.point.x) && pt.y.eq(this.rightSE.point.y))); } /* Compare this segment with a point. * * A point P is considered to be colinear to a segment if there * exists a distance D such that if we travel along the segment * from one * endpoint towards the other a distance D, we find * ourselves at point P. * * Return value indicates: * * 1: point lies above the segment (to the left of vertical) * 0: point is colinear to segment * -1: point lies below the segment (to the right of vertical) */ comparePoint(point) { return precision.orient(this.leftSE.point, point, this.rightSE.point); } /** * Given another segment, returns the first non-trivial intersection * between the two segments (in terms of sweep line ordering), if it exists. * * A 'non-trivial' intersection is one that will cause one or both of the * segments to be split(). As such, 'trivial' vs. 'non-trivial' intersection: * * * endpoint of segA with endpoint of segB --> trivial * * endpoint of segA with point along segB --> non-trivial * * endpoint of segB with point along segA --> non-trivial * * point along segA with point along segB --> non-trivial * * If no non-trivial intersection exists, return null * Else, return null. */ getIntersection(other) { // If bboxes don't overlap, there can't be any intersections const tBbox = this.bbox(); const oBbox = other.bbox(); const bboxOverlap = getBboxOverlap(tBbox, oBbox); if (bboxOverlap === null) return null; // We first check to see if the endpoints can be considered intersections. // This will 'snap' intersections to endpoints if possible, and will // handle cases of colinearity. const tlp = this.leftSE.point; const trp = this.rightSE.point; const olp = other.leftSE.point; const orp = other.rightSE.point; // does each endpoint touch the other segment? // note that we restrict the 'touching' definition to only allow segments // to touch endpoints that lie forward from where we are in the sweep line pass const touchesOtherLSE = isInBbox(tBbox, olp) && this.comparePoint(olp) === 0; const touchesThisLSE = isInBbox(oBbox, tlp) && other.comparePoint(tlp) === 0; const touchesOtherRSE = isInBbox(tBbox, orp) && this.comparePoint(orp) === 0; const touchesThisRSE = isInBbox(oBbox, trp) && other.comparePoint(trp) === 0; // do left endpoints match? if (touchesThisLSE && touchesOtherLSE) { // these two cases are for colinear segments with matching left // endpoints, and one segment being longer than the other if (touchesThisRSE && !touchesOtherRSE) return trp; if (!touchesThisRSE && touchesOtherRSE) return orp; // either the two segments match exactly (two trival intersections) // or just on their left endpoint (one trivial intersection return null; } // does this left endpoint matches (other doesn't) if (touchesThisLSE) { // check for segments that just intersect on opposing endpoints if (touchesOtherRSE) { if (tlp.x.eq(orp.x) && tlp.y.eq(orp.y)) return null; } // t-intersection on left endpoint return tlp; } // does other left endpoint matches (this doesn't) if (touchesOtherLSE) { // check for segments that just intersect on opposing endpoints if (touchesThisRSE) { if (trp.x.eq(olp.x) && trp.y.eq(olp.y)) return null; } // t-intersection on left endpoint return olp; } // trivial intersection on right endpoints if (touchesThisRSE && touchesOtherRSE) return null; // t-intersections on just one right endpoint if (touchesThisRSE) return trp; if (touchesOtherRSE) return orp; // None of our endpoints intersect. Look for a general intersection between // infinite lines laid over the segments const pt = intersection$1(tlp, this.vector(), olp, other.vector()); // are the segments parrallel? Note that if they were colinear with overlap, // they would have an endpoint intersection and that case was already handled above if (pt === null) return null; // is the intersection found between the lines not on the segments? if (!isInBbox(bboxOverlap, pt)) return null; // round the the computed point if needed return precision.snap(pt); } /** * Split the given segment into multiple segments on the given points. * * Each existing segment will retain its leftSE and a new rightSE will be * generated for it. * * A new segment will be generated which will adopt the original segment's * rightSE, and a new leftSE will be generated for it. * * If there are more than two points given to split on, new segments * in the middle will be generated with new leftSE and rightSE's. * * An array of the newly generated SweepEvents will be returned. * * Warning: input array of points is modified */ split(point) { const newEvents = []; const alreadyLinked = point.events !== undefined; const newLeftSE = new SweepEvent(point, true); const newRightSE = new SweepEvent(point, false); const oldRightSE = this.rightSE; this.replaceRightSE(newRightSE); newEvents.push(newRightSE); newEvents.push(newLeftSE); const newSeg = new Segment(newLeftSE, oldRightSE, this.rings.slice(), this.windings.slice()); // when splitting a nearly vertical downward-facing segment, // sometimes one of the resulting new segments is vertical, in which // case its left and right events may need to be swapped if (SweepEvent.comparePoints(newSeg.leftSE.point, newSeg.rightSE.point) > 0) { newSeg.swapEvents(); } if (SweepEvent.comparePoints(this.leftSE.point, this.rightSE.point) > 0) { this.swapEvents(); } // in the point we just used to create new sweep events with was already // linked to other events, we need to check if either of the affected // segments should be consumed if (alreadyLinked) { newLeftSE.checkForConsuming(); newRightSE.checkForConsuming(); } return newEvents; } /* Swap which event is left and right */ swapEvents() { const tmpEvt = this.rightSE; this.rightSE = this.leftSE; this.leftSE = tmpEvt; this.leftSE.isLeft = true; this.rightSE.isLeft = false; for (let i = 0, iMax = this.windings.length; i < iMax; i++) { this.windings[i] *= -1; } } /* Consume another segment. We take their rings under our wing * and mark them as consumed. Use for perfectly overlapping segments */ consume(other) { let consumer = this; let consumee = other; while (consumer.consumedBy) consumer = consumer.consumedBy; while (consumee.consumedBy) consumee = consumee.consumedBy; const cmp = Segment.compare(consumer, consumee); if (cmp === 0) return; // already consumed // the winner of the consumption is the earlier segment // according to sweep line ordering if (cmp > 0) { const tmp = consumer; consumer = consumee; consumee = tmp; } // make sure a segment doesn't consume it's prev if (consumer.prev === consumee) { const tmp = consumer; consumer = consumee; consumee = tmp; } for (let i = 0, iMax = consumee.rings.length; i < iMax; i++) { const ring = consumee.rings[i]; const winding = consumee.windings[i]; const index = consumer.rings.indexOf(ring); if (index === -1) { consumer.rings.push(ring); consumer.windings.push(winding); } else consumer.windings[index] += winding; } consumee.rings = null; consumee.windings = null; consumee.consumedBy = consumer; // mark sweep events consumed as to maintain ordering in sweep event queue consumee.leftSE.consumedBy = consumer.leftSE; consumee.rightSE.consumedBy = consumer.rightSE; } /* The first segment previous segment chain that is in the result */ prevInResult() { if (this._prevInResult !== undefined) return this._prevInResult; if (!this.prev) this._prevInResult = null; else if (this.prev.isInResult()) this._prevInResult = this.prev; else this._prevInResult = this.prev.prevInResult(); return this._prevInResult; } beforeState() { if (this._beforeState !== undefined) return this._beforeState; if (!this.prev) this._beforeState = { rings: [], windings: [], multiPolys: [], }; else { const seg = this.prev.consumedBy || this.prev; this._beforeState = seg.afterState(); } return this._beforeState; } afterState() { if (this._afterState !== undefined) return this._afterState; const beforeState = this.beforeState(); this._afterState = { rings: beforeState.rings.slice(0), windings: beforeState.windings.slice(0), multiPolys: [], }; const ringsAfter = this._afterState.rings; const windingsAfter = this._afterState.windings; const mpsAfter = this._afterState.multiPolys; // calculate ringsAfter, windingsAfter for (let i = 0, iMax = this.rings.length; i < iMax; i++) { const ring = this.rings[i]; const winding = this.windings[i]; const index = ringsAfter.indexOf(ring); if (index === -1) { ringsAfter.push(ring); windingsAfter.push(winding); } else windingsAfter[index] += winding; } // calcualte polysAfter const polysAfter = []; const polysExclude = []; for (let i = 0, iMax = ringsAfter.length; i < iMax; i++) { if (windingsAfter[i] === 0) continue; // non-zero rule const ring = ringsAfter[i]; const poly = ring.poly; if (polysExclude.indexOf(poly) !== -1) continue; if (ring.isExterior) polysAfter.push(poly); else { if (polysExclude.indexOf(poly) === -1) polysExclude.push(poly); const index = polysAfter.indexOf(ring.poly); if (index !== -1) polysAfter.splice(index, 1); } } // calculate multiPolysAfter for (let i = 0, iMax = polysAfter.length; i < iMax; i++) { const mp = polysAfter[i].multiPoly; if (mpsAfter.indexOf(mp) === -1) mpsAfter.push(mp); } return this._afterState; } /* Is this segment part of the final result? */ isInResult() { // if we've been consumed, we're not in the result if (this.consumedBy) return false; if (this._isInResult !== undefined) return this._isInResult; const mpsBefore = this.beforeState().multiPolys; const mpsAfter = this.afterState().multiPolys; switch (operation.type) { case "union": { // UNION - included iff: // * On one side of us there is 0 poly interiors AND // * On the other side there is 1 or more. const noBefores = mpsBefore.length === 0; const noAfters = mpsAfter.length === 0; this._isInResult = noBefores !== noAfters; break; } case "intersection": { // INTERSECTION - included iff: // * on one side of us all multipolys are rep. with poly interiors AND // * on the other side of us, not all multipolys are repsented // with poly interiors let least; let most; if (mpsBefore.length < mpsAfter.length) { least = mpsBefore.length; most = mpsAfter.length; } else { least = mpsAfter.length; most = mpsBefore.length; } this._isInResult = most === operation.numMultiPolys && least < most; break; } case "xor": { // XOR - included iff: // * the difference between the number of multipolys represented // with poly interiors on our two sides is an odd number const diff = Math.abs(mpsBefore.length - mpsAfter.length); this._isInResult = diff % 2 === 1; break; } case "difference": { // DIFFERENCE included iff: // * on exactly one side, we have just the subject const isJustSubject = (mps) => mps.length === 1 && mps[0].isSubject; this._isInResult = isJustSubject(mpsBefore) !== isJustSubject(mpsAfter); break; } } return this._isInResult; } } class RingIn { poly; isExterior; segments; bbox; constructor(geomRing, poly, isExterior) { if (!Array.isArray(geomRing) || geomRing.length === 0) { throw new Error("Input geometry is not a valid Polygon or MultiPolygon"); } this.poly = poly; this.isExterior = isExterior; this.segments = []; if (typeof geomRing[0][0] !== "number" || typeof geomRing[0][1] !== "number") { throw new Error("Input geometry is not a valid Polygon or MultiPolygon"); } const firstPoint = precision.snap({ x: new BigNumber(geomRing[0][0]), y: new BigNumber(geomRing[0][1]) }); this.bbox = { ll: { x: firstPoint.x, y: firstPoint.y }, ur: { x: firstPoint.x, y: firstPoint.y }, }; let prevPoint = firstPoint; for (let i = 1, iMax = geomRing.length; i < iMax; i++) { if (typeof geomRing[i][0] !== "number" || typeof geomRing[i][1] !== "number") { throw new Error("Input geometry is not a valid Polygon or MultiPolygon"); } const point = precision.snap({ x: new BigNumber(geomRing[i][0]), y: new BigNumber(geomRing[i][1]) }); // skip repeated points if (point.x.eq(prevPoint.x) && point.y.eq(prevPoint.y)) continue; this.segments.push(Segment.fromRing(prevPoint, point, this)); if (point.x.isLessThan(this.bbox.ll.x)) this.bbox.ll.x = point.x; if (point.y.isLessThan(this.bbox.ll.y)) this.bbox.ll.y = point.y; if (point.x.isGreaterThan(this.bbox.ur.x)) this.bbox.ur.x = point.x; if (point.y.isGreaterThan(this.bbox.ur.y)) this.bbox.ur.y = point.y; prevPoint = point; } // add segment from last to first if last is not the same as first if (!firstPoint.x.eq(prevPoint.x) || !firstPoint.y.eq(prevPoint.y)) { this.segments.push(Segment.fromRing(prevPoint, firstPoint, this)); } } getSweepEvents() { const sweepEvents = []; for (let i = 0, iMax = this.segments.length; i < iMax; i++) { const segment = this.segments[i]; sweepEvents.push(segment.leftSE); sweepEvents.push(segment.rightSE); } return sweepEvents; } } class PolyIn { multiPoly; exteriorRing; interiorRings; bbox; constructor(geomPoly, multiPoly) { if (!Array.isArray(geomPoly)) { throw new Error("Input geometry is not a valid Polygon or MultiPolygon"); } this.exteriorRing = new RingIn(geomPoly[0], this, true); // copy by value this.bbox = { ll: { x: this.exteriorRing.bbox.ll.x, y: this.exteriorRing.bbox.ll.y }, ur: { x: this.exteriorRing.bbox.ur.x, y: this.exteriorRing.bbox.ur.y }, }; this.interiorRings = []; for (let i = 1, iMax = geomPoly.length; i < iMax; i++) { const ring = new RingIn(geomPoly[i], this, false); if (ring.bbox.ll.x.isLessThan(this.bbox.ll.x)) this.bbox.ll.x = ring.bbox.ll.x; if (ring.bbox.ll.y.isLessThan(this.bbox.ll.y)) this.bbox.ll.y = ring.bbox.ll.y; if (ring.bbox.ur.x.isGreaterThan(this.bbox.ur.x)) this.bbox.ur.x = ring.bbox.ur.x; if (ring.bbox.ur.y.isGreaterThan(this.bbox.ur.y)) this.bbox.ur.y = ring.bbox.ur.y; this.interiorRings.push(ring); } this.multiPoly = multiPoly; } getSweepEvents() { const sweepEvents = this.exteriorRing.getSweepEvents(); for (let i = 0, iMax = this.interiorRings.length; i < iMax; i++) { const ringSweepEvents = this.interiorRings[i].getSweepEvents(); for (let j = 0, jMax = ringSweepEvents.length; j < jMax; j++) { sweepEvents.push(ringSweepEvents[j]); } } return sweepEvents; } } class MultiPolyIn { isSubject; polys; bbox; constructor(geom, isSubject) { if (!Array.isArray(geom)) { throw new Error("Input geometry is not a valid Polygon or MultiPolygon"); } try { // if the input looks like a polygon, convert it to a multipolygon if (typeof geom[0][0][0] === "number") geom = [geom]; } catch (ex) { // The input is either malformed or has empty arrays. // In either case, it will be handled later on. } this.polys = []; this.bbox = { ll: { x: new BigNumber(Number.POSITIVE_INFINITY), y: new BigNumber(Number.POSITIVE_INFINITY) }, ur: { x: new BigNumber(Number.NEGATIVE_INFINITY), y: new BigNumber(Number.NEGATIVE_INFINITY) }, }; for (let i = 0, iMax = geom.length; i < iMax; i++) { const poly = new PolyIn(geom[i], this); if (poly.bbox.ll.x.isLessThan(this.bbox.ll.x)) this.bbox.ll.x = poly.bbox.ll.x; if (poly.bbox.ll.y.isLessThan(this.bbox.ll.y)) this.bbox.ll.y = poly.bbox.ll.y; if (poly.bbox.ur.x.isGreaterThan(this.bbox.ur.x)) this.bbox.ur.x = poly.bbox.ur.x; if (poly.bbox.ur.y.isGreaterThan(this.bbox.ur.y)) this.bbox.ur.y = poly.bbox.ur.y; this.polys.push(poly); } this.isSubject = isSubject; } getSweepEvents() { const sweepEvents = []; for (let i = 0, iMax = this.polys.length; i < iMax; i++) { const polySweepEvents = this.polys[i].getSweepEvents(); for (let j = 0, jMax = polySweepEvents.length; j < jMax; j++) { sweepEvents.push(polySweepEvents[j]); } } return sweepEvents; } } class RingOut { events; poly; _isExteriorRing; _enclosingRing; /* Given the segments from the sweep line pass, compute & return a series * of closed rings from all the segments marked to be part of the result */ static factory(allSegments) { const ringsOut = []; for (let i = 0, iMax = allSegments.length; i < iMax; i++) { const segment = allSegments[i]; if (!segment.isInResult() || segment.ringOut) continue; let prevEvent = null; let event = segment.leftSE; let nextEvent = segment.rightSE; const events = [event]; const startingPoint = event.point; const intersectionLEs = []; /* Walk the chain of linked events to form a closed ring */ while (true) { prevEvent = event; event = nextEvent; events.push(event); /* Is the ring complete? */ if (event.point === startingPoint) break; while (true) { const availableLEs = event.getAvailableLinkedEvents(); /* Did we hit a dead end? This shouldn't happen. Indicates some earlier * part of the algorithm malfunctioned... please file a bug report. */ if (availableLEs.length === 0) { const firstPt = events[0].point; const lastPt = events[events.length - 1].point; throw new Error(`Unable to complete output ring starting at [${firstPt.x},` + ` ${firstPt.y}]. Last matching segment found ends at` + ` [${lastPt.x}, ${lastPt.y}].`); } /* Only one way to go, so cotinue on the path */ if (availableLEs.length === 1) { nextEvent = availableLEs[0].otherSE; break; } /* We must have an intersection. Check for a completed loop */ let indexLE = null; for (let j = 0, jMax = intersectionLEs.length; j < jMax; j++) { if (intersectionLEs[j].point === event.point) { indexLE = j; break; } } /* Found a completed loop. Cut that off and make a ring */ if (indexLE !== null) { const intersectionLE = intersectionLEs.splice(indexLE)[0]; const ringEvents = events.splice(intersectionLE.index); ringEvents.unshift(ringEvents[0].otherSE); ringsOut.push(new RingOut(ringEvents.reverse())); continue; } /* register the intersection */ intersectionLEs.push({ index: events.length, point: event.point, }); /* Choose the left-most option to continue the walk */ const comparator = event.getLeftmostComparator(prevEvent); nextEvent = availableLEs.sort(comparator)[0].otherSE; break; } } ringsOut.push(new RingOut(events)); } return ringsOut; } constructor(events) { this.events = events; for (let i = 0, iMax = events.length; i < iMax; i++) { events[i].segment.ringOut = this; } this.poly = null; } getGeom() { // Remove superfluous points (ie extra points along a straight line), let prevPt = this.events[0].point; const points = [prevPt]; for (let i = 1, iMax = this.events.length - 1; i < iMax; i++) { const pt = this.events[i].point; const nextPt = this.events[i + 1].point; if (precision.orient(pt, prevPt, nextPt) === 0) continue; points.push(pt); prevPt = pt; } // ring was all (within rounding error of angle calc) colinear points if (points.length === 1) return null; // check if the starting point is necessary const pt = points[0]; const nextPt = points[1]; if (precision.orient(pt, prevPt, nextPt) === 0) points.shift(); points.push(points[0]); const step = this.isExteriorRing() ? 1 : -1; const iStart = this.isExteriorRing() ? 0 : points.length - 1; const iEnd = this.isExteriorRing() ? points.length : -1; const orderedPoints = []; for (let i = iStart; i != iEnd; i += step) orderedPoints.push([points[i].x.toNumber(), points[i].y.toNumber()]); return orderedPoints; } isExteriorRing() { if (this._isExteriorRing === undefined) { const enclosing = this.enclosingRing(); this._isExteriorRing = enclosing ? !enclosing.isExteriorRing() : true; } return this._isExteriorRing; } enclosingRing() { if (this._enclosingRing === undefined) { this._enclosingRing = this._calcEnclosingRing(); } return this._enclosingRing; } /* Returns the ring that encloses this one, if any */ _calcEnclosingRing() { // start with the ealier sweep line event so that the prevSeg // chain doesn't lead us inside of a loop of ours let leftMostEvt = this.events[0]; for (let i = 1, iMax = this.events.length; i < iMax; i++) { const evt = this.events[i]; if (SweepEvent.compare(leftMostEvt, evt) > 0) leftMostEvt = evt; } let prevSeg = leftMostEvt.segment.prevInResult(); let prevPrevSeg = prevSeg ? prevSeg.prevInResult() : null; while (true) { // no segment found, thus no ring can enclose us if (!prevSeg) return null; // no segments below prev segment found, thus the ring of the prev // segment must loop back around and enclose us if (!prevPrevSeg) return prevSeg.ringOut; // if the two segments are of different rings, the ring of the prev // segment must either loop around us or the ring of the prev prev // seg, which would make us and the ring of the prev peers if (prevPrevSeg.ringOut !== prevSeg.ringOut) { if (prevPrevSeg.ringOut?.enclosingRing() !== prevSeg.ringOut) { return prevSeg.ringOut; } else return prevSeg.ringOut?.enclosingRing(); } // two segments are from the same ring, so this was a penisula // of that ring. iterate downward, keep searching prevSeg = prevPrevSeg.prevInResult(); prevPrevSeg = prevSeg ? prevSeg.prevInResult() : null; } } } class PolyOut { exteriorRing; interiorRings; constructor(exteriorRing) { this.exteriorRing = exteriorRing; exteriorRing.poly = this; this.interiorRings = []; } addInterior(ring) { this.interiorRings.push(ring); ring.poly = this; } getGeom() { const geom0 = this.exteriorRing.getGeom(); // exterior ring was all (within rounding error of angle calc) colinear points if (geom0 === null) return null; const geom = [geom0]; for (let i = 0, iMax = this.interiorRings.length; i < iMax; i++) { const ringGeom = this.interiorRings[i].getGeom(); // interior ring was all (within rounding error of angle calc) colinear points if (ringGeom === null) continue; geom.push(ringGeom); } return geom; } } class MultiPolyOut { rings; polys; constructor(rings) { this.rings = rings; this.polys = this._composePolys(rings); } getGeom() { const geom = []; for (let i = 0, iMax = this.polys.length; i < iMax; i++) { const polyGeom = this.polys[i].getGeom(); // exterior ring was all (within rounding error of angle calc) colinear points if (polyGeom === null) continue; geom.push(polyGeom); } return geom; } _composePolys(rings) { const polys = []; for (let i = 0, iMax = rings.length; i < iMax; i++) { const ring = rings[i]; if (ring.poly) continue; if (ring.isExteriorRing()) polys.push(new PolyOut(ring)); else { const enclosingRing = ring.enclosingRing(); if (!enclosingRing?.poly) polys.push(new PolyOut(enclosingRing)); enclosingRing?.poly?.addInterior(ring); } } return polys; } } /** * NOTE: We must be careful not to change any segments while * they are in the SplayTree. AFAIK, there's no way to tell * the tree to rebalance itself - thus before splitting * a segment that's in the tree, we remove it from the tree, * do the split, then re-insert it. (Even though splitting a * segment *shouldn't* change its correct position in the * sweep line tree, the reality is because of rounding errors, * it sometimes does.) */ class SweepLine { queue; tree; segments; constructor(queue, comparator = Segment.compare) { this.queue = queue; this.tree = new SplayTreeSet(comparator); this.segments = []; } process(event) { const segment = event.segment; const newEvents = []; // if we've already been consumed by another segment, // clean up our body parts and get out if (event.consumedBy) { if (event.isLeft) this.queue.delete(event.otherSE); else this.tree.delete(segment); return newEvents; } if (event.isLeft) this.tree.add(segment); let prevSeg = segment; let nextSeg = segment; // skip consumed segments still in tree do { prevSeg = this.tree.lastBefore(prevSeg); } while (prevSeg != null && prevSeg.consumedBy != undefined); // skip consumed segments still in tree do { nextSeg = this.tree.firstAfter(nextSeg); } while (nextSeg != null && nextSeg.consumedBy != undefined); if (event.isLeft) { // Check for intersections against the previous segment in the sweep line let prevMySplitter = null; if (prevSeg) { const prevInter = prevSeg.getIntersection(segment); if (prevInter !== null) { if (!segment.isAnEndpoint(prevInter)) prevMySplitter = prevInter; if (!prevSeg.isAnEndpoint(prevInter)) { const newEventsFromSplit = this._splitSafely(prevSeg, prevInter); for (let i = 0, iMax = newEventsFromSplit.length; i < iMax; i++) { newEvents.push(newEventsFromSplit[i]); } } } } // Check for intersections against the next segment in the sweep line let nextMySplitter = null; if (nextSeg) { const nextInter = nextSeg.getIntersection(segment); if (nextInter !== null) { if (!segment.isAnEndpoint(nextInter)) nextMySplitter = nextInter; if (!nextSeg.isAnEndpoint(nextInter)) { const newEventsFromSplit = this._splitSafely(nextSeg, nextInter); for (let i = 0, iMax = newEventsFromSplit.length; i < iMax; i++) { newEvents.push(newEventsFromSplit[i]); } } } } // For simplicity, even if we find more than one intersection we only // spilt on the 'earliest' (sweep-line style) of the intersections. // The other intersection will be handled in a future process(). if (prevMySplitter !== null || nextMySplitter !== null) { let mySplitter = null; if (prevMySplitter === null) mySplitter = nextMySplitter; else if (nextMySplitter === null) mySplitter = prevMySplitter; else { const cmpSplitters = SweepEvent.comparePoints(prevMySplitter, nextMySplitter); mySplitter = cmpSplitters <= 0 ? prevMySplitter : nextMySplitter; } // Rounding errors can cause changes in ordering, // so remove afected segments and right sweep events before splitting this.queue.delete(segment.rightSE); newEvents.push(segment.rightSE); const newEventsFromSplit = segment.split(mySplitter); for (let i = 0, iMax = newEventsFromSplit.length; i < iMax; i++) { newEvents.push(newEventsFromSplit[i]); } } if (newEvents.length > 0) { // We found some intersections, so re-do the current event to // make sure sweep line ordering is totally consistent for later // use with the segment 'prev' pointers this.tree.delete(segment); newEvents.push(event); } else { // done with left event this.segments.push(segment); segment.prev = prevSeg; } } else { // event.isRight // since we're about to be removed from the sweep line, check for // intersections between our previous and next segments if (prevSeg && nextSeg) { const inter = prevSeg.getIntersection(nextSeg); if (inter !== null) { if (!prevSeg.isAnEndpoint(inter)) { const newEventsFromSplit = this._splitSafely(prevSeg, inter); for (let i = 0, iMax = newEventsFromSplit.length; i < iMax; i++) { newEvents.push(newEventsFromSplit[i]); } } if (!nextSeg.isAnEndpoint(inter)) { const newEventsFromSplit = this._splitSafely(nextSeg, inter); for (let i = 0, iMax = newEventsFromSplit.length; i < iMax; i++) { newEvents.push(newEventsFromSplit[i]); } } } } this.tree.delete(segment); } return newEvents; } /* Safely split a segment that is currently in the datastructures * IE - a segment other than the one that is currently being processed. */ _splitSafely(seg, pt) { // Rounding errors can cause changes in ordering, // so remove afected segments and right sweep events before splitting // removeNode() doesn't work, so have re-find the seg // https://github.com/w8r/splay-tree/pull/5 this.tree.delete(seg); const rightSE = seg.rightSE; this.queue.delete(rightSE); const newEvents = seg.split(pt); newEvents.push(rightSE); // splitting can trigger consumption if (seg.consumedBy === undefined) this.tree.add(seg); return newEvents; } } class Operation { type; numMultiPolys; run(type, geom, moreGeoms) { operation.type = type; /* Convert inputs to MultiPoly objects */ const multipolys = [new MultiPolyIn(geom, true)]; for (let i = 0, iMax = moreGeoms.length; i < iMax; i++) { multipolys.push(new MultiPolyIn(moreGeoms[i], false)); } operation.numMultiPolys = multipolys.length; /* BBox optimization for difference operation * If the bbox of a multipolygon that's part of the clipping doesn't * intersect the bbox of the subject at all, we can just drop that * multiploygon. */ if (operation.type === "difference") { // in place removal const subject = multipolys[0]; let i = 1; while (i < multipolys.length) { if (getBboxOverlap(multipolys[i].bbox, subject.bbox) !== null) i++; else multipolys.splice(i, 1); } } /* BBox optimization for intersection operation * If we can find any pair of multipolygons whose bbox does not overlap, * then the result will be empty. */ if (operation.type === "intersection") { // TODO: this is O(n^2) in number of polygons. By sorting the bboxes, // it could be optimized to O(n * ln(n)) for (let i = 0, iMax = multipolys.length; i < iMax; i++) { const mpA = multipolys[i]; for (let j = i + 1, jMax = multipolys.length; j < jMax; j++) { if (getBboxOverlap(mpA.bbox, multipolys[j].bbox) === null) return []; } } } /* Put segment endpoints in a priority queue */ const queue = new SplayTreeSet(SweepEvent.compare); for (let i = 0, iMax = multipolys.length; i < iMax; i++) { const sweepEvents = multipolys[i].getSweepEvents(); for (let j = 0, jMax = sweepEvents.length; j < jMax; j++) { queue.add(sweepEvents[j]); } } /* Pass the sweep line over those endpoints */ const sweepLine = new SweepLine(queue); let evt = null; if (queue.size != 0) { evt = queue.first(); queue.delete(evt); } while (evt) { const newEvents = sweepLine.process(evt); for (let i = 0, iMax = newEvents.length; i < iMax; i++) { const evt = newEvents[i]; if (evt.consumedBy === undefined) queue.add(evt); } if (queue.size != 0) { evt = queue.first(); queue.delete(evt); } else { evt = null; } } // free some memory we don't need anymore precision.reset(); /* Collect and compile segments we're keeping into a multipolygon */ const ringsOut = RingOut.factory(sweepLine.segments); const result = new MultiPolyOut(ringsOut); return result.getGeom(); } } // singleton available by import const operation = new Operation(); const union = (geom, ...moreGeoms) => operation.run("union", geom, moreGeoms); const intersection = (geom, ...moreGeoms) => operation.run("intersection", geom, moreGeoms); const xor = (geom, ...moreGeoms) => operation.run("xor", geom, moreGeoms); const difference = (geom, ...moreGeoms) => operation.run("difference", geom, moreGeoms); const setPrecision = precision.set; exports.difference = difference; exports.intersection = intersection; exports.setPrecision = setPrecision; exports.union = union; exports.version = version; exports.xor = xor; Object.defineProperty(exports, '__esModule', { value: true }); }));