Created
March 5, 2021 08:46
-
-
Save desmondyeoh/414b089472130f1730f2be57fa90a6df to your computer and use it in GitHub Desktop.
S2ID BigQuery
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/// S2 Geometry functions | |
// the regional scoreboard is based on a level 6 S2 Cell | |
// - https://docs.google.com/presentation/d/1Hl4KapfAENAOf4gv-pSngKwvS_jwNVHRPZTTDzXXn6Q/view?pli=1#slide=id.i22 | |
// at the time of writing there's no actual API for the intel map to retrieve scoreboard data, | |
// but it's still useful to plot the score cells on the intel map | |
// the S2 geometry is based on projecting the earth sphere onto a cube, with some scaling of face coordinates to | |
// keep things close to approximate equal area for adjacent cells | |
// to convert a lat,lng into a cell id: | |
// - convert lat,lng to x,y,z | |
// - convert x,y,z into face,u,v | |
// - u,v scaled to s,t with quadratic formula | |
// - s,t converted to integer i,j offsets | |
// - i,j converted to a position along a Hubbert space-filling curve | |
// - combine face,position to get the cell id | |
//NOTE: compared to the google S2 geometry library, we vary from their code in the following ways | |
// - cell IDs: they combine face and the hilbert curve position into a single 64 bit number. this gives efficient space | |
// and speed. javascript doesn't have appropriate data types, and speed is not cricical, so we use | |
// as [face,[bitpair,bitpair,...]] instead | |
// - i,j: they always use 30 bits, adjusting as needed. we use 0 to (1<<level)-1 instead | |
// (so GetSizeIJ for a cell is always 1) | |
/** | |
* wasm optimizations, to do native i64 multiplication and divide | |
*/ | |
var wasm = null; | |
try { | |
wasm = new WebAssembly.Instance(new WebAssembly.Module(new Uint8Array([ | |
0, 97, 115, 109, 1, 0, 0, 0, 1, 13, 2, 96, 0, 1, 127, 96, 4, 127, 127, 127, 127, 1, 127, 3, 7, 6, 0, 1, 1, 1, 1, 1, 6, 6, 1, 127, 1, 65, 0, 11, 7, 50, 6, 3, 109, 117, 108, 0, 1, 5, 100, 105, 118, 95, 115, 0, 2, 5, 100, 105, 118, 95, 117, 0, 3, 5, 114, 101, 109, 95, 115, 0, 4, 5, 114, 101, 109, 95, 117, 0, 5, 8, 103, 101, 116, 95, 104, 105, 103, 104, 0, 0, 10, 191, 1, 6, 4, 0, 35, 0, 11, 36, 1, 1, 126, 32, 0, 173, 32, 1, 173, 66, 32, 134, 132, 32, 2, 173, 32, 3, 173, 66, 32, 134, 132, 126, 34, 4, 66, 32, 135, 167, 36, 0, 32, 4, 167, 11, 36, 1, 1, 126, 32, 0, 173, 32, 1, 173, 66, 32, 134, 132, 32, 2, 173, 32, 3, 173, 66, 32, 134, 132, 127, 34, 4, 66, 32, 135, 167, 36, 0, 32, 4, 167, 11, 36, 1, 1, 126, 32, 0, 173, 32, 1, 173, 66, 32, 134, 132, 32, 2, 173, 32, 3, 173, 66, 32, 134, 132, 128, 34, 4, 66, 32, 135, 167, 36, 0, 32, 4, 167, 11, 36, 1, 1, 126, 32, 0, 173, 32, 1, 173, 66, 32, 134, 132, 32, 2, 173, 32, 3, 173, 66, 32, 134, 132, 129, 34, 4, 66, 32, 135, 167, 36, 0, 32, 4, 167, 11, 36, 1, 1, 126, 32, 0, 173, 32, 1, 173, 66, 32, 134, 132, 32, 2, 173, 32, 3, 173, 66, 32, 134, 132, 130, 34, 4, 66, 32, 135, 167, 36, 0, 32, 4, 167, 11 | |
])), {}).exports; | |
} catch (e) { | |
// no wasm support :( | |
} | |
/** | |
* Constructs a 64 bit two's-complement integer, given its low and high 32 bit values as *signed* integers. | |
* See the from* functions below for more convenient ways of constructing Longs. | |
* @exports Long | |
* @class A Long class for representing a 64 bit two's-complement integer value. | |
* @param {number} low The low (signed) 32 bits of the long | |
* @param {number} high The high (signed) 32 bits of the long | |
* @param {boolean=} unsigned Whether unsigned or not, defaults to signed | |
* @constructor | |
*/ | |
function Long(low, high, unsigned) { | |
/** | |
* The low 32 bits as a signed value. | |
* @type {number} | |
*/ | |
this.low = low | 0; | |
/** | |
* The high 32 bits as a signed value. | |
* @type {number} | |
*/ | |
this.high = high | 0; | |
/** | |
* Whether unsigned or not. | |
* @type {boolean} | |
*/ | |
this.unsigned = !!unsigned; | |
} | |
// The internal representation of a long is the two given signed, 32-bit values. | |
// We use 32-bit pieces because these are the size of integers on which | |
// Javascript performs bit-operations. For operations like addition and | |
// multiplication, we split each number into 16 bit pieces, which can easily be | |
// multiplied within Javascript's floating-point representation without overflow | |
// or change in sign. | |
// | |
// In the algorithms below, we frequently reduce the negative case to the | |
// positive case by negating the input(s) and then post-processing the result. | |
// Note that we must ALWAYS check specially whether those values are MIN_VALUE | |
// (-2^63) because -MIN_VALUE == MIN_VALUE (since 2^63 cannot be represented as | |
// a positive number, it overflows back into a negative). Not handling this | |
// case would often result in infinite recursion. | |
// | |
// Common constant values ZERO, ONE, NEG_ONE, etc. are defined below the from* | |
// methods on which they depend. | |
/** | |
* An indicator used to reliably determine if an object is a Long or not. | |
* @type {boolean} | |
* @const | |
* @private | |
*/ | |
Long.prototype.__isLong__; | |
Object.defineProperty(Long.prototype, "__isLong__", { value: true }); | |
/** | |
* @function | |
* @param {*} obj Object | |
* @returns {boolean} | |
* @inner | |
*/ | |
function isLong(obj) { | |
return (obj && obj["__isLong__"]) === true; | |
} | |
/** | |
* Tests if the specified object is a Long. | |
* @function | |
* @param {*} obj Object | |
* @returns {boolean} | |
*/ | |
Long.isLong = isLong; | |
/** | |
* A cache of the Long representations of small integer values. | |
* @type {!Object} | |
* @inner | |
*/ | |
var INT_CACHE = {}; | |
/** | |
* A cache of the Long representations of small unsigned integer values. | |
* @type {!Object} | |
* @inner | |
*/ | |
var UINT_CACHE = {}; | |
/** | |
* @param {number} value | |
* @param {boolean=} unsigned | |
* @returns {!Long} | |
* @inner | |
*/ | |
function fromInt(value, unsigned) { | |
var obj, cachedObj, cache; | |
if (unsigned) { | |
value >>>= 0; | |
if (cache = (0 <= value && value < 256)) { | |
cachedObj = UINT_CACHE[value]; | |
if (cachedObj) | |
return cachedObj; | |
} | |
obj = fromBits(value, (value | 0) < 0 ? -1 : 0, true); | |
if (cache) | |
UINT_CACHE[value] = obj; | |
return obj; | |
} else { | |
value |= 0; | |
if (cache = (-128 <= value && value < 128)) { | |
cachedObj = INT_CACHE[value]; | |
if (cachedObj) | |
return cachedObj; | |
} | |
obj = fromBits(value, value < 0 ? -1 : 0, false); | |
if (cache) | |
INT_CACHE[value] = obj; | |
return obj; | |
} | |
} | |
/** | |
* Returns a Long representing the given 32 bit integer value. | |
* @function | |
* @param {number} value The 32 bit integer in question | |
* @param {boolean=} unsigned Whether unsigned or not, defaults to signed | |
* @returns {!Long} The corresponding Long value | |
*/ | |
Long.fromInt = fromInt; | |
/** | |
* @param {number} value | |
* @param {boolean=} unsigned | |
* @returns {!Long} | |
* @inner | |
*/ | |
function fromNumber(value, unsigned) { | |
if (isNaN(value)) | |
return unsigned ? UZERO : ZERO; | |
if (unsigned) { | |
if (value < 0) | |
return UZERO; | |
if (value >= TWO_PWR_64_DBL) | |
return MAX_UNSIGNED_VALUE; | |
} else { | |
if (value <= -TWO_PWR_63_DBL) | |
return MIN_VALUE; | |
if (value + 1 >= TWO_PWR_63_DBL) | |
return MAX_VALUE; | |
} | |
if (value < 0) | |
return fromNumber(-value, unsigned).neg(); | |
return fromBits((value % TWO_PWR_32_DBL) | 0, (value / TWO_PWR_32_DBL) | 0, unsigned); | |
} | |
/** | |
* Returns a Long representing the given value, provided that it is a finite number. Otherwise, zero is returned. | |
* @function | |
* @param {number} value The number in question | |
* @param {boolean=} unsigned Whether unsigned or not, defaults to signed | |
* @returns {!Long} The corresponding Long value | |
*/ | |
Long.fromNumber = fromNumber; | |
/** | |
* @param {number} lowBits | |
* @param {number} highBits | |
* @param {boolean=} unsigned | |
* @returns {!Long} | |
* @inner | |
*/ | |
function fromBits(lowBits, highBits, unsigned) { | |
return new Long(lowBits, highBits, unsigned); | |
} | |
/** | |
* Returns a Long representing the 64 bit integer that comes by concatenating the given low and high bits. Each is | |
* assumed to use 32 bits. | |
* @function | |
* @param {number} lowBits The low 32 bits | |
* @param {number} highBits The high 32 bits | |
* @param {boolean=} unsigned Whether unsigned or not, defaults to signed | |
* @returns {!Long} The corresponding Long value | |
*/ | |
Long.fromBits = fromBits; | |
/** | |
* @function | |
* @param {number} base | |
* @param {number} exponent | |
* @returns {number} | |
* @inner | |
*/ | |
var pow_dbl = Math.pow; // Used 4 times (4*8 to 15+4) | |
/** | |
* @param {string} str | |
* @param {(boolean|number)=} unsigned | |
* @param {number=} radix | |
* @returns {!Long} | |
* @inner | |
*/ | |
function fromString(str, unsigned, radix) { | |
if (str.length === 0) | |
throw Error('empty string'); | |
if (str === "NaN" || str === "Infinity" || str === "+Infinity" || str === "-Infinity") | |
return ZERO; | |
if (typeof unsigned === 'number') { | |
// For goog.math.long compatibility | |
radix = unsigned, | |
unsigned = false; | |
} else { | |
unsigned = !! unsigned; | |
} | |
radix = radix || 10; | |
if (radix < 2 || 36 < radix) | |
throw RangeError('radix'); | |
var p; | |
if ((p = str.indexOf('-')) > 0) | |
throw Error('interior hyphen'); | |
else if (p === 0) { | |
return fromString(str.substring(1), unsigned, radix).neg(); | |
} | |
// Do several (8) digits each time through the loop, so as to | |
// minimize the calls to the very expensive emulated div. | |
var radixToPower = fromNumber(pow_dbl(radix, 8)); | |
var result = ZERO; | |
for (var i = 0; i < str.length; i += 8) { | |
var size = Math.min(8, str.length - i), | |
value = parseInt(str.substring(i, i + size), radix); | |
if (size < 8) { | |
var power = fromNumber(pow_dbl(radix, size)); | |
result = result.mul(power).add(fromNumber(value)); | |
} else { | |
result = result.mul(radixToPower); | |
result = result.add(fromNumber(value)); | |
} | |
} | |
result.unsigned = unsigned; | |
return result; | |
} | |
/** | |
* Returns a Long representation of the given string, written using the specified radix. | |
* @function | |
* @param {string} str The textual representation of the Long | |
* @param {(boolean|number)=} unsigned Whether unsigned or not, defaults to signed | |
* @param {number=} radix The radix in which the text is written (2-36), defaults to 10 | |
* @returns {!Long} The corresponding Long value | |
*/ | |
Long.fromString = fromString; | |
/** | |
* @function | |
* @param {!Long|number|string|!{low: number, high: number, unsigned: boolean}} val | |
* @param {boolean=} unsigned | |
* @returns {!Long} | |
* @inner | |
*/ | |
function fromValue(val, unsigned) { | |
if (typeof val === 'number') | |
return fromNumber(val, unsigned); | |
if (typeof val === 'string') | |
return fromString(val, unsigned); | |
// Throws for non-objects, converts non-instanceof Long: | |
return fromBits(val.low, val.high, typeof unsigned === 'boolean' ? unsigned : val.unsigned); | |
} | |
/** | |
* Converts the specified value to a Long using the appropriate from* function for its type. | |
* @function | |
* @param {!Long|number|string|!{low: number, high: number, unsigned: boolean}} val Value | |
* @param {boolean=} unsigned Whether unsigned or not, defaults to signed | |
* @returns {!Long} | |
*/ | |
Long.fromValue = fromValue; | |
// NOTE: the compiler should inline these constant values below and then remove these variables, so there should be | |
// no runtime penalty for these. | |
/** | |
* @type {number} | |
* @const | |
* @inner | |
*/ | |
var TWO_PWR_16_DBL = 1 << 16; | |
/** | |
* @type {number} | |
* @const | |
* @inner | |
*/ | |
var TWO_PWR_24_DBL = 1 << 24; | |
/** | |
* @type {number} | |
* @const | |
* @inner | |
*/ | |
var TWO_PWR_32_DBL = TWO_PWR_16_DBL * TWO_PWR_16_DBL; | |
/** | |
* @type {number} | |
* @const | |
* @inner | |
*/ | |
var TWO_PWR_64_DBL = TWO_PWR_32_DBL * TWO_PWR_32_DBL; | |
/** | |
* @type {number} | |
* @const | |
* @inner | |
*/ | |
var TWO_PWR_63_DBL = TWO_PWR_64_DBL / 2; | |
/** | |
* @type {!Long} | |
* @const | |
* @inner | |
*/ | |
var TWO_PWR_24 = fromInt(TWO_PWR_24_DBL); | |
/** | |
* @type {!Long} | |
* @inner | |
*/ | |
var ZERO = fromInt(0); | |
/** | |
* Signed zero. | |
* @type {!Long} | |
*/ | |
Long.ZERO = ZERO; | |
/** | |
* @type {!Long} | |
* @inner | |
*/ | |
var UZERO = fromInt(0, true); | |
/** | |
* Unsigned zero. | |
* @type {!Long} | |
*/ | |
Long.UZERO = UZERO; | |
/** | |
* @type {!Long} | |
* @inner | |
*/ | |
var ONE = fromInt(1); | |
/** | |
* Signed one. | |
* @type {!Long} | |
*/ | |
Long.ONE = ONE; | |
/** | |
* @type {!Long} | |
* @inner | |
*/ | |
var UONE = fromInt(1, true); | |
/** | |
* Unsigned one. | |
* @type {!Long} | |
*/ | |
Long.UONE = UONE; | |
/** | |
* @type {!Long} | |
* @inner | |
*/ | |
var NEG_ONE = fromInt(-1); | |
/** | |
* Signed negative one. | |
* @type {!Long} | |
*/ | |
Long.NEG_ONE = NEG_ONE; | |
/** | |
* @type {!Long} | |
* @inner | |
*/ | |
var MAX_VALUE = fromBits(0xFFFFFFFF|0, 0x7FFFFFFF|0, false); | |
/** | |
* Maximum signed value. | |
* @type {!Long} | |
*/ | |
Long.MAX_VALUE = MAX_VALUE; | |
/** | |
* @type {!Long} | |
* @inner | |
*/ | |
var MAX_UNSIGNED_VALUE = fromBits(0xFFFFFFFF|0, 0xFFFFFFFF|0, true); | |
/** | |
* Maximum unsigned value. | |
* @type {!Long} | |
*/ | |
Long.MAX_UNSIGNED_VALUE = MAX_UNSIGNED_VALUE; | |
/** | |
* @type {!Long} | |
* @inner | |
*/ | |
var MIN_VALUE = fromBits(0, 0x80000000|0, false); | |
/** | |
* Minimum signed value. | |
* @type {!Long} | |
*/ | |
Long.MIN_VALUE = MIN_VALUE; | |
/** | |
* @alias Long.prototype | |
* @inner | |
*/ | |
var LongPrototype = Long.prototype; | |
/** | |
* Converts the Long to a 32 bit integer, assuming it is a 32 bit integer. | |
* @returns {number} | |
*/ | |
LongPrototype.toInt = function toInt() { | |
return this.unsigned ? this.low >>> 0 : this.low; | |
}; | |
/** | |
* Converts the Long to a the nearest floating-point representation of this value (double, 53 bit mantissa). | |
* @returns {number} | |
*/ | |
LongPrototype.toNumber = function toNumber() { | |
if (this.unsigned) | |
return ((this.high >>> 0) * TWO_PWR_32_DBL) + (this.low >>> 0); | |
return this.high * TWO_PWR_32_DBL + (this.low >>> 0); | |
}; | |
/** | |
* Converts the Long to a string written in the specified radix. | |
* @param {number=} radix Radix (2-36), defaults to 10 | |
* @returns {string} | |
* @override | |
* @throws {RangeError} If `radix` is out of range | |
*/ | |
LongPrototype.toString = function toString(radix) { | |
radix = radix || 10; | |
if (radix < 2 || 36 < radix) | |
throw RangeError('radix'); | |
if (this.isZero()) | |
return '0'; | |
if (this.isNegative()) { // Unsigned Longs are never negative | |
if (this.eq(MIN_VALUE)) { | |
// We need to change the Long value before it can be negated, so we remove | |
// the bottom-most digit in this base and then recurse to do the rest. | |
var radixLong = fromNumber(radix), | |
div = this.div(radixLong), | |
rem1 = div.mul(radixLong).sub(this); | |
return div.toString(radix) + rem1.toInt().toString(radix); | |
} else | |
return '-' + this.neg().toString(radix); | |
} | |
// Do several (6) digits each time through the loop, so as to | |
// minimize the calls to the very expensive emulated div. | |
var radixToPower = fromNumber(pow_dbl(radix, 6), this.unsigned), | |
rem = this; | |
var result = ''; | |
while (true) { | |
var remDiv = rem.div(radixToPower), | |
intval = rem.sub(remDiv.mul(radixToPower)).toInt() >>> 0, | |
digits = intval.toString(radix); | |
rem = remDiv; | |
if (rem.isZero()) | |
return digits + result; | |
else { | |
while (digits.length < 6) | |
digits = '0' + digits; | |
result = '' + digits + result; | |
} | |
} | |
}; | |
/** | |
* Gets the high 32 bits as a signed integer. | |
* @returns {number} Signed high bits | |
*/ | |
LongPrototype.getHighBits = function getHighBits() { | |
return this.high; | |
}; | |
/** | |
* Gets the high 32 bits as an unsigned integer. | |
* @returns {number} Unsigned high bits | |
*/ | |
LongPrototype.getHighBitsUnsigned = function getHighBitsUnsigned() { | |
return this.high >>> 0; | |
}; | |
/** | |
* Gets the low 32 bits as a signed integer. | |
* @returns {number} Signed low bits | |
*/ | |
LongPrototype.getLowBits = function getLowBits() { | |
return this.low; | |
}; | |
/** | |
* Gets the low 32 bits as an unsigned integer. | |
* @returns {number} Unsigned low bits | |
*/ | |
LongPrototype.getLowBitsUnsigned = function getLowBitsUnsigned() { | |
return this.low >>> 0; | |
}; | |
/** | |
* Gets the number of bits needed to represent the absolute value of this Long. | |
* @returns {number} | |
*/ | |
LongPrototype.getNumBitsAbs = function getNumBitsAbs() { | |
if (this.isNegative()) // Unsigned Longs are never negative | |
return this.eq(MIN_VALUE) ? 64 : this.neg().getNumBitsAbs(); | |
var val = this.high != 0 ? this.high : this.low; | |
for (var bit = 31; bit > 0; bit--) | |
if ((val & (1 << bit)) != 0) | |
break; | |
return this.high != 0 ? bit + 33 : bit + 1; | |
}; | |
/** | |
* Tests if this Long's value equals zero. | |
* @returns {boolean} | |
*/ | |
LongPrototype.isZero = function isZero() { | |
return this.high === 0 && this.low === 0; | |
}; | |
/** | |
* Tests if this Long's value equals zero. This is an alias of {@link Long#isZero}. | |
* @returns {boolean} | |
*/ | |
LongPrototype.eqz = LongPrototype.isZero; | |
/** | |
* Tests if this Long's value is negative. | |
* @returns {boolean} | |
*/ | |
LongPrototype.isNegative = function isNegative() { | |
return !this.unsigned && this.high < 0; | |
}; | |
/** | |
* Tests if this Long's value is positive. | |
* @returns {boolean} | |
*/ | |
LongPrototype.isPositive = function isPositive() { | |
return this.unsigned || this.high >= 0; | |
}; | |
/** | |
* Tests if this Long's value is odd. | |
* @returns {boolean} | |
*/ | |
LongPrototype.isOdd = function isOdd() { | |
return (this.low & 1) === 1; | |
}; | |
/** | |
* Tests if this Long's value is even. | |
* @returns {boolean} | |
*/ | |
LongPrototype.isEven = function isEven() { | |
return (this.low & 1) === 0; | |
}; | |
/** | |
* Tests if this Long's value equals the specified's. | |
* @param {!Long|number|string} other Other value | |
* @returns {boolean} | |
*/ | |
LongPrototype.equals = function equals(other) { | |
if (!isLong(other)) | |
other = fromValue(other); | |
if (this.unsigned !== other.unsigned && (this.high >>> 31) === 1 && (other.high >>> 31) === 1) | |
return false; | |
return this.high === other.high && this.low === other.low; | |
}; | |
/** | |
* Tests if this Long's value equals the specified's. This is an alias of {@link Long#equals}. | |
* @function | |
* @param {!Long|number|string} other Other value | |
* @returns {boolean} | |
*/ | |
LongPrototype.eq = LongPrototype.equals; | |
/** | |
* Tests if this Long's value differs from the specified's. | |
* @param {!Long|number|string} other Other value | |
* @returns {boolean} | |
*/ | |
LongPrototype.notEquals = function notEquals(other) { | |
return !this.eq(/* validates */ other); | |
}; | |
/** | |
* Tests if this Long's value differs from the specified's. This is an alias of {@link Long#notEquals}. | |
* @function | |
* @param {!Long|number|string} other Other value | |
* @returns {boolean} | |
*/ | |
LongPrototype.neq = LongPrototype.notEquals; | |
/** | |
* Tests if this Long's value differs from the specified's. This is an alias of {@link Long#notEquals}. | |
* @function | |
* @param {!Long|number|string} other Other value | |
* @returns {boolean} | |
*/ | |
LongPrototype.ne = LongPrototype.notEquals; | |
/** | |
* Tests if this Long's value is less than the specified's. | |
* @param {!Long|number|string} other Other value | |
* @returns {boolean} | |
*/ | |
LongPrototype.lessThan = function lessThan(other) { | |
return this.comp(/* validates */ other) < 0; | |
}; | |
/** | |
* Tests if this Long's value is less than the specified's. This is an alias of {@link Long#lessThan}. | |
* @function | |
* @param {!Long|number|string} other Other value | |
* @returns {boolean} | |
*/ | |
LongPrototype.lt = LongPrototype.lessThan; | |
/** | |
* Tests if this Long's value is less than or equal the specified's. | |
* @param {!Long|number|string} other Other value | |
* @returns {boolean} | |
*/ | |
LongPrototype.lessThanOrEqual = function lessThanOrEqual(other) { | |
return this.comp(/* validates */ other) <= 0; | |
}; | |
/** | |
* Tests if this Long's value is less than or equal the specified's. This is an alias of {@link Long#lessThanOrEqual}. | |
* @function | |
* @param {!Long|number|string} other Other value | |
* @returns {boolean} | |
*/ | |
LongPrototype.lte = LongPrototype.lessThanOrEqual; | |
/** | |
* Tests if this Long's value is less than or equal the specified's. This is an alias of {@link Long#lessThanOrEqual}. | |
* @function | |
* @param {!Long|number|string} other Other value | |
* @returns {boolean} | |
*/ | |
LongPrototype.le = LongPrototype.lessThanOrEqual; | |
/** | |
* Tests if this Long's value is greater than the specified's. | |
* @param {!Long|number|string} other Other value | |
* @returns {boolean} | |
*/ | |
LongPrototype.greaterThan = function greaterThan(other) { | |
return this.comp(/* validates */ other) > 0; | |
}; | |
/** | |
* Tests if this Long's value is greater than the specified's. This is an alias of {@link Long#greaterThan}. | |
* @function | |
* @param {!Long|number|string} other Other value | |
* @returns {boolean} | |
*/ | |
LongPrototype.gt = LongPrototype.greaterThan; | |
/** | |
* Tests if this Long's value is greater than or equal the specified's. | |
* @param {!Long|number|string} other Other value | |
* @returns {boolean} | |
*/ | |
LongPrototype.greaterThanOrEqual = function greaterThanOrEqual(other) { | |
return this.comp(/* validates */ other) >= 0; | |
}; | |
/** | |
* Tests if this Long's value is greater than or equal the specified's. This is an alias of {@link Long#greaterThanOrEqual}. | |
* @function | |
* @param {!Long|number|string} other Other value | |
* @returns {boolean} | |
*/ | |
LongPrototype.gte = LongPrototype.greaterThanOrEqual; | |
/** | |
* Tests if this Long's value is greater than or equal the specified's. This is an alias of {@link Long#greaterThanOrEqual}. | |
* @function | |
* @param {!Long|number|string} other Other value | |
* @returns {boolean} | |
*/ | |
LongPrototype.ge = LongPrototype.greaterThanOrEqual; | |
/** | |
* Compares this Long's value with the specified's. | |
* @param {!Long|number|string} other Other value | |
* @returns {number} 0 if they are the same, 1 if the this is greater and -1 | |
* if the given one is greater | |
*/ | |
LongPrototype.compare = function compare(other) { | |
if (!isLong(other)) | |
other = fromValue(other); | |
if (this.eq(other)) | |
return 0; | |
var thisNeg = this.isNegative(), | |
otherNeg = other.isNegative(); | |
if (thisNeg && !otherNeg) | |
return -1; | |
if (!thisNeg && otherNeg) | |
return 1; | |
// At this point the sign bits are the same | |
if (!this.unsigned) | |
return this.sub(other).isNegative() ? -1 : 1; | |
// Both are positive if at least one is unsigned | |
return (other.high >>> 0) > (this.high >>> 0) || (other.high === this.high && (other.low >>> 0) > (this.low >>> 0)) ? -1 : 1; | |
}; | |
/** | |
* Compares this Long's value with the specified's. This is an alias of {@link Long#compare}. | |
* @function | |
* @param {!Long|number|string} other Other value | |
* @returns {number} 0 if they are the same, 1 if the this is greater and -1 | |
* if the given one is greater | |
*/ | |
LongPrototype.comp = LongPrototype.compare; | |
/** | |
* Negates this Long's value. | |
* @returns {!Long} Negated Long | |
*/ | |
LongPrototype.negate = function negate() { | |
if (!this.unsigned && this.eq(MIN_VALUE)) | |
return MIN_VALUE; | |
return this.not().add(ONE); | |
}; | |
/** | |
* Negates this Long's value. This is an alias of {@link Long#negate}. | |
* @function | |
* @returns {!Long} Negated Long | |
*/ | |
LongPrototype.neg = LongPrototype.negate; | |
/** | |
* Returns the sum of this and the specified Long. | |
* @param {!Long|number|string} addend Addend | |
* @returns {!Long} Sum | |
*/ | |
LongPrototype.add = function add(addend) { | |
if (!isLong(addend)) | |
addend = fromValue(addend); | |
// Divide each number into 4 chunks of 16 bits, and then sum the chunks. | |
var a48 = this.high >>> 16; | |
var a32 = this.high & 0xFFFF; | |
var a16 = this.low >>> 16; | |
var a00 = this.low & 0xFFFF; | |
var b48 = addend.high >>> 16; | |
var b32 = addend.high & 0xFFFF; | |
var b16 = addend.low >>> 16; | |
var b00 = addend.low & 0xFFFF; | |
var c48 = 0, c32 = 0, c16 = 0, c00 = 0; | |
c00 += a00 + b00; | |
c16 += c00 >>> 16; | |
c00 &= 0xFFFF; | |
c16 += a16 + b16; | |
c32 += c16 >>> 16; | |
c16 &= 0xFFFF; | |
c32 += a32 + b32; | |
c48 += c32 >>> 16; | |
c32 &= 0xFFFF; | |
c48 += a48 + b48; | |
c48 &= 0xFFFF; | |
return fromBits((c16 << 16) | c00, (c48 << 16) | c32, this.unsigned); | |
}; | |
/** | |
* Returns the difference of this and the specified Long. | |
* @param {!Long|number|string} subtrahend Subtrahend | |
* @returns {!Long} Difference | |
*/ | |
LongPrototype.subtract = function subtract(subtrahend) { | |
if (!isLong(subtrahend)) | |
subtrahend = fromValue(subtrahend); | |
return this.add(subtrahend.neg()); | |
}; | |
/** | |
* Returns the difference of this and the specified Long. This is an alias of {@link Long#subtract}. | |
* @function | |
* @param {!Long|number|string} subtrahend Subtrahend | |
* @returns {!Long} Difference | |
*/ | |
LongPrototype.sub = LongPrototype.subtract; | |
/** | |
* Returns the product of this and the specified Long. | |
* @param {!Long|number|string} multiplier Multiplier | |
* @returns {!Long} Product | |
*/ | |
LongPrototype.multiply = function multiply(multiplier) { | |
if (this.isZero()) | |
return ZERO; | |
if (!isLong(multiplier)) | |
multiplier = fromValue(multiplier); | |
// use wasm support if present | |
if (wasm) { | |
var low = wasm.mul(this.low, | |
this.high, | |
multiplier.low, | |
multiplier.high); | |
return fromBits(low, wasm.get_high(), this.unsigned); | |
} | |
if (multiplier.isZero()) | |
return ZERO; | |
if (this.eq(MIN_VALUE)) | |
return multiplier.isOdd() ? MIN_VALUE : ZERO; | |
if (multiplier.eq(MIN_VALUE)) | |
return this.isOdd() ? MIN_VALUE : ZERO; | |
if (this.isNegative()) { | |
if (multiplier.isNegative()) | |
return this.neg().mul(multiplier.neg()); | |
else | |
return this.neg().mul(multiplier).neg(); | |
} else if (multiplier.isNegative()) | |
return this.mul(multiplier.neg()).neg(); | |
// If both longs are small, use float multiplication | |
if (this.lt(TWO_PWR_24) && multiplier.lt(TWO_PWR_24)) | |
return fromNumber(this.toNumber() * multiplier.toNumber(), this.unsigned); | |
// Divide each long into 4 chunks of 16 bits, and then add up 4x4 products. | |
// We can skip products that would overflow. | |
var a48 = this.high >>> 16; | |
var a32 = this.high & 0xFFFF; | |
var a16 = this.low >>> 16; | |
var a00 = this.low & 0xFFFF; | |
var b48 = multiplier.high >>> 16; | |
var b32 = multiplier.high & 0xFFFF; | |
var b16 = multiplier.low >>> 16; | |
var b00 = multiplier.low & 0xFFFF; | |
var c48 = 0, c32 = 0, c16 = 0, c00 = 0; | |
c00 += a00 * b00; | |
c16 += c00 >>> 16; | |
c00 &= 0xFFFF; | |
c16 += a16 * b00; | |
c32 += c16 >>> 16; | |
c16 &= 0xFFFF; | |
c16 += a00 * b16; | |
c32 += c16 >>> 16; | |
c16 &= 0xFFFF; | |
c32 += a32 * b00; | |
c48 += c32 >>> 16; | |
c32 &= 0xFFFF; | |
c32 += a16 * b16; | |
c48 += c32 >>> 16; | |
c32 &= 0xFFFF; | |
c32 += a00 * b32; | |
c48 += c32 >>> 16; | |
c32 &= 0xFFFF; | |
c48 += a48 * b00 + a32 * b16 + a16 * b32 + a00 * b48; | |
c48 &= 0xFFFF; | |
return fromBits((c16 << 16) | c00, (c48 << 16) | c32, this.unsigned); | |
}; | |
/** | |
* Returns the product of this and the specified Long. This is an alias of {@link Long#multiply}. | |
* @function | |
* @param {!Long|number|string} multiplier Multiplier | |
* @returns {!Long} Product | |
*/ | |
LongPrototype.mul = LongPrototype.multiply; | |
/** | |
* Returns this Long divided by the specified. The result is signed if this Long is signed or | |
* unsigned if this Long is unsigned. | |
* @param {!Long|number|string} divisor Divisor | |
* @returns {!Long} Quotient | |
*/ | |
LongPrototype.divide = function divide(divisor) { | |
if (!isLong(divisor)) | |
divisor = fromValue(divisor); | |
if (divisor.isZero()) | |
throw Error('division by zero'); | |
// use wasm support if present | |
if (wasm) { | |
// guard against signed division overflow: the largest | |
// negative number / -1 would be 1 larger than the largest | |
// positive number, due to two's complement. | |
if (!this.unsigned && | |
this.high === -0x80000000 && | |
divisor.low === -1 && divisor.high === -1) { | |
// be consistent with non-wasm code path | |
return this; | |
} | |
var low = (this.unsigned ? wasm.div_u : wasm.div_s)( | |
this.low, | |
this.high, | |
divisor.low, | |
divisor.high | |
); | |
return fromBits(low, wasm.get_high(), this.unsigned); | |
} | |
if (this.isZero()) | |
return this.unsigned ? UZERO : ZERO; | |
var approx, rem, res; | |
if (!this.unsigned) { | |
// This section is only relevant for signed longs and is derived from the | |
// closure library as a whole. | |
if (this.eq(MIN_VALUE)) { | |
if (divisor.eq(ONE) || divisor.eq(NEG_ONE)) | |
return MIN_VALUE; // recall that -MIN_VALUE == MIN_VALUE | |
else if (divisor.eq(MIN_VALUE)) | |
return ONE; | |
else { | |
// At this point, we have |other| >= 2, so |this/other| < |MIN_VALUE|. | |
var halfThis = this.shr(1); | |
approx = halfThis.div(divisor).shl(1); | |
if (approx.eq(ZERO)) { | |
return divisor.isNegative() ? ONE : NEG_ONE; | |
} else { | |
rem = this.sub(divisor.mul(approx)); | |
res = approx.add(rem.div(divisor)); | |
return res; | |
} | |
} | |
} else if (divisor.eq(MIN_VALUE)) | |
return this.unsigned ? UZERO : ZERO; | |
if (this.isNegative()) { | |
if (divisor.isNegative()) | |
return this.neg().div(divisor.neg()); | |
return this.neg().div(divisor).neg(); | |
} else if (divisor.isNegative()) | |
return this.div(divisor.neg()).neg(); | |
res = ZERO; | |
} else { | |
// The algorithm below has not been made for unsigned longs. It's therefore | |
// required to take special care of the MSB prior to running it. | |
if (!divisor.unsigned) | |
divisor = divisor.toUnsigned(); | |
if (divisor.gt(this)) | |
return UZERO; | |
if (divisor.gt(this.shru(1))) // 15 >>> 1 = 7 ; with divisor = 8 ; true | |
return UONE; | |
res = UZERO; | |
} | |
// Repeat the following until the remainder is less than other: find a | |
// floating-point that approximates remainder / other *from below*, add this | |
// into the result, and subtract it from the remainder. It is critical that | |
// the approximate value is less than or equal to the real value so that the | |
// remainder never becomes negative. | |
rem = this; | |
while (rem.gte(divisor)) { | |
// Approximate the result of division. This may be a little greater or | |
// smaller than the actual value. | |
approx = Math.max(1, Math.floor(rem.toNumber() / divisor.toNumber())); | |
// We will tweak the approximate result by changing it in the 48-th digit or | |
// the smallest non-fractional digit, whichever is larger. | |
var log2 = Math.ceil(Math.log(approx) / Math.LN2), | |
delta = (log2 <= 48) ? 1 : pow_dbl(2, log2 - 48), | |
// Decrease the approximation until it is smaller than the remainder. Note | |
// that if it is too large, the product overflows and is negative. | |
approxRes = fromNumber(approx), | |
approxRem = approxRes.mul(divisor); | |
while (approxRem.isNegative() || approxRem.gt(rem)) { | |
approx -= delta; | |
approxRes = fromNumber(approx, this.unsigned); | |
approxRem = approxRes.mul(divisor); | |
} | |
// We know the answer can't be zero... and actually, zero would cause | |
// infinite recursion since we would make no progress. | |
if (approxRes.isZero()) | |
approxRes = ONE; | |
res = res.add(approxRes); | |
rem = rem.sub(approxRem); | |
} | |
return res; | |
}; | |
/** | |
* Returns this Long divided by the specified. This is an alias of {@link Long#divide}. | |
* @function | |
* @param {!Long|number|string} divisor Divisor | |
* @returns {!Long} Quotient | |
*/ | |
LongPrototype.div = LongPrototype.divide; | |
/** | |
* Returns this Long modulo the specified. | |
* @param {!Long|number|string} divisor Divisor | |
* @returns {!Long} Remainder | |
*/ | |
LongPrototype.modulo = function modulo(divisor) { | |
if (!isLong(divisor)) | |
divisor = fromValue(divisor); | |
// use wasm support if present | |
if (wasm) { | |
var low = (this.unsigned ? wasm.rem_u : wasm.rem_s)( | |
this.low, | |
this.high, | |
divisor.low, | |
divisor.high | |
); | |
return fromBits(low, wasm.get_high(), this.unsigned); | |
} | |
return this.sub(this.div(divisor).mul(divisor)); | |
}; | |
/** | |
* Returns this Long modulo the specified. This is an alias of {@link Long#modulo}. | |
* @function | |
* @param {!Long|number|string} divisor Divisor | |
* @returns {!Long} Remainder | |
*/ | |
LongPrototype.mod = LongPrototype.modulo; | |
/** | |
* Returns this Long modulo the specified. This is an alias of {@link Long#modulo}. | |
* @function | |
* @param {!Long|number|string} divisor Divisor | |
* @returns {!Long} Remainder | |
*/ | |
LongPrototype.rem = LongPrototype.modulo; | |
/** | |
* Returns the bitwise NOT of this Long. | |
* @returns {!Long} | |
*/ | |
LongPrototype.not = function not() { | |
return fromBits(~this.low, ~this.high, this.unsigned); | |
}; | |
/** | |
* Returns the bitwise AND of this Long and the specified. | |
* @param {!Long|number|string} other Other Long | |
* @returns {!Long} | |
*/ | |
LongPrototype.and = function and(other) { | |
if (!isLong(other)) | |
other = fromValue(other); | |
return fromBits(this.low & other.low, this.high & other.high, this.unsigned); | |
}; | |
/** | |
* Returns the bitwise OR of this Long and the specified. | |
* @param {!Long|number|string} other Other Long | |
* @returns {!Long} | |
*/ | |
LongPrototype.or = function or(other) { | |
if (!isLong(other)) | |
other = fromValue(other); | |
return fromBits(this.low | other.low, this.high | other.high, this.unsigned); | |
}; | |
/** | |
* Returns the bitwise XOR of this Long and the given one. | |
* @param {!Long|number|string} other Other Long | |
* @returns {!Long} | |
*/ | |
LongPrototype.xor = function xor(other) { | |
if (!isLong(other)) | |
other = fromValue(other); | |
return fromBits(this.low ^ other.low, this.high ^ other.high, this.unsigned); | |
}; | |
/** | |
* Returns this Long with bits shifted to the left by the given amount. | |
* @param {number|!Long} numBits Number of bits | |
* @returns {!Long} Shifted Long | |
*/ | |
LongPrototype.shiftLeft = function shiftLeft(numBits) { | |
if (isLong(numBits)) | |
numBits = numBits.toInt(); | |
if ((numBits &= 63) === 0) | |
return this; | |
else if (numBits < 32) | |
return fromBits(this.low << numBits, (this.high << numBits) | (this.low >>> (32 - numBits)), this.unsigned); | |
else | |
return fromBits(0, this.low << (numBits - 32), this.unsigned); | |
}; | |
/** | |
* Returns this Long with bits shifted to the left by the given amount. This is an alias of {@link Long#shiftLeft}. | |
* @function | |
* @param {number|!Long} numBits Number of bits | |
* @returns {!Long} Shifted Long | |
*/ | |
LongPrototype.shl = LongPrototype.shiftLeft; | |
/** | |
* Returns this Long with bits arithmetically shifted to the right by the given amount. | |
* @param {number|!Long} numBits Number of bits | |
* @returns {!Long} Shifted Long | |
*/ | |
LongPrototype.shiftRight = function shiftRight(numBits) { | |
if (isLong(numBits)) | |
numBits = numBits.toInt(); | |
if ((numBits &= 63) === 0) | |
return this; | |
else if (numBits < 32) | |
return fromBits((this.low >>> numBits) | (this.high << (32 - numBits)), this.high >> numBits, this.unsigned); | |
else | |
return fromBits(this.high >> (numBits - 32), this.high >= 0 ? 0 : -1, this.unsigned); | |
}; | |
/** | |
* Returns this Long with bits arithmetically shifted to the right by the given amount. This is an alias of {@link Long#shiftRight}. | |
* @function | |
* @param {number|!Long} numBits Number of bits | |
* @returns {!Long} Shifted Long | |
*/ | |
LongPrototype.shr = LongPrototype.shiftRight; | |
/** | |
* Returns this Long with bits logically shifted to the right by the given amount. | |
* @param {number|!Long} numBits Number of bits | |
* @returns {!Long} Shifted Long | |
*/ | |
LongPrototype.shiftRightUnsigned = function shiftRightUnsigned(numBits) { | |
if (isLong(numBits)) | |
numBits = numBits.toInt(); | |
numBits &= 63; | |
if (numBits === 0) | |
return this; | |
else { | |
var high = this.high; | |
if (numBits < 32) { | |
var low = this.low; | |
return fromBits((low >>> numBits) | (high << (32 - numBits)), high >>> numBits, this.unsigned); | |
} else if (numBits === 32) | |
return fromBits(high, 0, this.unsigned); | |
else | |
return fromBits(high >>> (numBits - 32), 0, this.unsigned); | |
} | |
}; | |
/** | |
* Returns this Long with bits logically shifted to the right by the given amount. This is an alias of {@link Long#shiftRightUnsigned}. | |
* @function | |
* @param {number|!Long} numBits Number of bits | |
* @returns {!Long} Shifted Long | |
*/ | |
LongPrototype.shru = LongPrototype.shiftRightUnsigned; | |
/** | |
* Returns this Long with bits logically shifted to the right by the given amount. This is an alias of {@link Long#shiftRightUnsigned}. | |
* @function | |
* @param {number|!Long} numBits Number of bits | |
* @returns {!Long} Shifted Long | |
*/ | |
LongPrototype.shr_u = LongPrototype.shiftRightUnsigned; | |
/** | |
* Converts this Long to signed. | |
* @returns {!Long} Signed long | |
*/ | |
LongPrototype.toSigned = function toSigned() { | |
if (!this.unsigned) | |
return this; | |
return fromBits(this.low, this.high, false); | |
}; | |
/** | |
* Converts this Long to unsigned. | |
* @returns {!Long} Unsigned long | |
*/ | |
LongPrototype.toUnsigned = function toUnsigned() { | |
if (this.unsigned) | |
return this; | |
return fromBits(this.low, this.high, true); | |
}; | |
/** | |
* Converts this Long to its byte representation. | |
* @param {boolean=} le Whether little or big endian, defaults to big endian | |
* @returns {!Array.<number>} Byte representation | |
*/ | |
LongPrototype.toBytes = function toBytes(le) { | |
return le ? this.toBytesLE() : this.toBytesBE(); | |
}; | |
/** | |
* Converts this Long to its little endian byte representation. | |
* @returns {!Array.<number>} Little endian byte representation | |
*/ | |
LongPrototype.toBytesLE = function toBytesLE() { | |
var hi = this.high, | |
lo = this.low; | |
return [ | |
lo & 0xff, | |
lo >>> 8 & 0xff, | |
lo >>> 16 & 0xff, | |
lo >>> 24 , | |
hi & 0xff, | |
hi >>> 8 & 0xff, | |
hi >>> 16 & 0xff, | |
hi >>> 24 | |
]; | |
}; | |
/** | |
* Converts this Long to its big endian byte representation. | |
* @returns {!Array.<number>} Big endian byte representation | |
*/ | |
LongPrototype.toBytesBE = function toBytesBE() { | |
var hi = this.high, | |
lo = this.low; | |
return [ | |
hi >>> 24 , | |
hi >>> 16 & 0xff, | |
hi >>> 8 & 0xff, | |
hi & 0xff, | |
lo >>> 24 , | |
lo >>> 16 & 0xff, | |
lo >>> 8 & 0xff, | |
lo & 0xff | |
]; | |
}; | |
/** | |
* Creates a Long from its byte representation. | |
* @param {!Array.<number>} bytes Byte representation | |
* @param {boolean=} unsigned Whether unsigned or not, defaults to signed | |
* @param {boolean=} le Whether little or big endian, defaults to big endian | |
* @returns {Long} The corresponding Long value | |
*/ | |
Long.fromBytes = function fromBytes(bytes, unsigned, le) { | |
return le ? Long.fromBytesLE(bytes, unsigned) : Long.fromBytesBE(bytes, unsigned); | |
}; | |
/** | |
* Creates a Long from its little endian byte representation. | |
* @param {!Array.<number>} bytes Little endian byte representation | |
* @param {boolean=} unsigned Whether unsigned or not, defaults to signed | |
* @returns {Long} The corresponding Long value | |
*/ | |
Long.fromBytesLE = function fromBytesLE(bytes, unsigned) { | |
return new Long( | |
bytes[0] | | |
bytes[1] << 8 | | |
bytes[2] << 16 | | |
bytes[3] << 24, | |
bytes[4] | | |
bytes[5] << 8 | | |
bytes[6] << 16 | | |
bytes[7] << 24, | |
unsigned | |
); | |
}; | |
/** | |
* Creates a Long from its big endian byte representation. | |
* @param {!Array.<number>} bytes Big endian byte representation | |
* @param {boolean=} unsigned Whether unsigned or not, defaults to signed | |
* @returns {Long} The corresponding Long value | |
*/ | |
Long.fromBytesBE = function fromBytesBE(bytes, unsigned) { | |
return new Long( | |
bytes[4] << 24 | | |
bytes[5] << 16 | | |
bytes[6] << 8 | | |
bytes[7], | |
bytes[0] << 24 | | |
bytes[1] << 16 | | |
bytes[2] << 8 | | |
bytes[3], | |
unsigned | |
); | |
}; | |
var S2 = | |
(function (exports) { | |
'use strict'; | |
// var S2 = exports.S2 = { L: {} }; | |
var S2 = { L: {} }; | |
S2.L.LatLng = function (/*Number*/ rawLat, /*Number*/ rawLng, /*Boolean*/ noWrap) { | |
var lat = parseFloat(rawLat, 10); | |
var lng = parseFloat(rawLng, 10); | |
if (isNaN(lat) || isNaN(lng)) { | |
throw new Error('Invalid LatLng object: (' + rawLat + ', ' + rawLng + ')'); | |
} | |
if (noWrap !== true) { | |
lat = Math.max(Math.min(lat, 90), -90); // clamp latitude into -90..90 | |
lng = (lng + 180) % 360 + ((lng < -180 || lng === 180) ? 180 : -180); // wrap longtitude into -180..180 | |
} | |
return { lat: lat, lng: lng }; | |
}; | |
S2.L.LatLng.DEG_TO_RAD = Math.PI / 180; | |
S2.L.LatLng.RAD_TO_DEG = 180 / Math.PI; | |
/* | |
S2.LatLngToXYZ = function(latLng) { | |
// http://stackoverflow.com/questions/8981943/lat-long-to-x-y-z-position-in-js-not-working | |
var lat = latLng.lat; | |
var lon = latLng.lng; | |
var DEG_TO_RAD = Math.PI / 180.0; | |
var phi = lat * DEG_TO_RAD; | |
var theta = lon * DEG_TO_RAD; | |
var cosLat = Math.cos(phi); | |
var sinLat = Math.sin(phi); | |
var cosLon = Math.cos(theta); | |
var sinLon = Math.sin(theta); | |
var rad = 500.0; | |
return [ | |
rad * cosLat * cosLon | |
, rad * cosLat * sinLon | |
, rad * sinLat | |
]; | |
}; | |
*/ | |
S2.LatLngToXYZ = function (latLng) { | |
var d2r = S2.L.LatLng.DEG_TO_RAD; | |
var phi = latLng.lat * d2r; | |
var theta = latLng.lng * d2r; | |
var cosphi = Math.cos(phi); | |
return [Math.cos(theta) * cosphi, Math.sin(theta) * cosphi, Math.sin(phi)]; | |
}; | |
S2.XYZToLatLng = function (xyz) { | |
var r2d = S2.L.LatLng.RAD_TO_DEG; | |
var lat = Math.atan2(xyz[2], Math.sqrt(xyz[0] * xyz[0] + xyz[1] * xyz[1])); | |
var lng = Math.atan2(xyz[1], xyz[0]); | |
return S2.L.LatLng(lat * r2d, lng * r2d); | |
}; | |
var largestAbsComponent = function (xyz) { | |
var temp = [Math.abs(xyz[0]), Math.abs(xyz[1]), Math.abs(xyz[2])]; | |
if (temp[0] > temp[1]) { | |
if (temp[0] > temp[2]) { | |
return 0; | |
} else { | |
return 2; | |
} | |
} else { | |
if (temp[1] > temp[2]) { | |
return 1; | |
} else { | |
return 2; | |
} | |
} | |
}; | |
var faceXYZToUV = function (face, xyz) { | |
var u, v; | |
switch (face) { | |
case 0: u = xyz[1] / xyz[0]; v = xyz[2] / xyz[0]; break; | |
case 1: u = -xyz[0] / xyz[1]; v = xyz[2] / xyz[1]; break; | |
case 2: u = -xyz[0] / xyz[2]; v = -xyz[1] / xyz[2]; break; | |
case 3: u = xyz[2] / xyz[0]; v = xyz[1] / xyz[0]; break; | |
case 4: u = xyz[2] / xyz[1]; v = -xyz[0] / xyz[1]; break; | |
case 5: u = -xyz[1] / xyz[2]; v = -xyz[0] / xyz[2]; break; | |
default: throw { error: 'Invalid face' }; | |
} | |
return [u, v]; | |
}; | |
S2.XYZToFaceUV = function (xyz) { | |
var face = largestAbsComponent(xyz); | |
if (xyz[face] < 0) { | |
face += 3; | |
} | |
var uv = faceXYZToUV(face, xyz); | |
return [face, uv]; | |
}; | |
S2.FaceUVToXYZ = function (face, uv) { | |
var u = uv[0]; | |
var v = uv[1]; | |
switch (face) { | |
case 0: return [1, u, v]; | |
case 1: return [-u, 1, v]; | |
case 2: return [-u, -v, 1]; | |
case 3: return [-1, -v, -u]; | |
case 4: return [v, -1, -u]; | |
case 5: return [v, u, -1]; | |
default: throw { error: 'Invalid face' }; | |
} | |
}; | |
var singleSTtoUV = function (st) { | |
if (st >= 0.5) { | |
return (1 / 3.0) * (4 * st * st - 1); | |
} else { | |
return (1 / 3.0) * (1 - (4 * (1 - st) * (1 - st))); | |
} | |
}; | |
S2.STToUV = function (st) { | |
return [singleSTtoUV(st[0]), singleSTtoUV(st[1])]; | |
}; | |
var singleUVtoST = function (uv) { | |
if (uv >= 0) { | |
return 0.5 * Math.sqrt(1 + 3 * uv); | |
} else { | |
return 1 - 0.5 * Math.sqrt(1 - 3 * uv); | |
} | |
}; | |
S2.UVToST = function (uv) { | |
return [singleUVtoST(uv[0]), singleUVtoST(uv[1])]; | |
}; | |
S2.STToIJ = function (st, order) { | |
var maxSize = (1 << order); | |
var singleSTtoIJ = function (st) { | |
var ij = Math.floor(st * maxSize); | |
return Math.max(0, Math.min(maxSize - 1, ij)); | |
}; | |
return [singleSTtoIJ(st[0]), singleSTtoIJ(st[1])]; | |
}; | |
S2.IJToST = function (ij, order, offsets) { | |
var maxSize = (1 << order); | |
return [ | |
(ij[0] + offsets[0]) / maxSize, | |
(ij[1] + offsets[1]) / maxSize | |
]; | |
}; | |
var rotateAndFlipQuadrant = function (n, point, rx, ry) { | |
var newX, newY; | |
if (ry == 0) { | |
if (rx == 1) { | |
point.x = n - 1 - point.x; | |
point.y = n - 1 - point.y | |
} | |
var x = point.x; | |
point.x = point.y | |
point.y = x; | |
} | |
} | |
// hilbert space-filling curve | |
// based on http://blog.notdot.net/2009/11/Damn-Cool-Algorithms-Spatial-indexing-with-Quadtrees-and-Hilbert-Curves | |
// note: rather then calculating the final integer hilbert position, we just return the list of quads | |
// this ensures no precision issues whth large orders (S3 cell IDs use up to 30), and is more | |
// convenient for pulling out the individual bits as needed later | |
var pointToHilbertQuadList = function (x, y, order, face) { | |
var hilbertMap = { | |
'a': [[0, 'd'], [1, 'a'], [3, 'b'], [2, 'a']], | |
'b': [[2, 'b'], [1, 'b'], [3, 'a'], [0, 'c']], | |
'c': [[2, 'c'], [3, 'd'], [1, 'c'], [0, 'b']], | |
'd': [[0, 'a'], [3, 'c'], [1, 'd'], [2, 'd']] | |
}; | |
if ('number' !== typeof face) { | |
console.warn(new Error("called pointToHilbertQuadList without face value, defaulting to '0'").stack); | |
} | |
var currentSquare = (face % 2) ? 'd' : 'a'; | |
var positions = []; | |
for (var i = order - 1; i >= 0; i--) { | |
var mask = 1 << i; | |
var quad_x = x & mask ? 1 : 0; | |
var quad_y = y & mask ? 1 : 0; | |
var t = hilbertMap[currentSquare][quad_x * 2 + quad_y]; | |
positions.push(t[0]); | |
currentSquare = t[1]; | |
} | |
return positions; | |
}; | |
// S2Cell class | |
S2.S2Cell = function () { }; | |
S2.S2Cell.FromHilbertQuadKey = function (hilbertQuadkey) { | |
var parts = hilbertQuadkey.split('/'); | |
var face = parseInt(parts[0]); | |
var position = parts[1]; | |
var maxLevel = position.length; | |
var point = { | |
x: 0, | |
y: 0 | |
}; | |
var i; | |
var level; | |
var bit; | |
var rx, ry; | |
var val; | |
for (i = maxLevel - 1; i >= 0; i--) { | |
level = maxLevel - i; | |
bit = position[i]; | |
rx = 0; | |
ry = 0; | |
if (bit === '1') { | |
ry = 1; | |
} | |
else if (bit === '2') { | |
rx = 1; | |
ry = 1; | |
} | |
else if (bit === '3') { | |
rx = 1; | |
} | |
val = Math.pow(2, level - 1); | |
rotateAndFlipQuadrant(val, point, rx, ry); | |
point.x += val * rx; | |
point.y += val * ry; | |
} | |
if (face % 2 === 1) { | |
var t = point.x; | |
point.x = point.y; | |
point.y = t; | |
} | |
return S2.S2Cell.FromFaceIJ(parseInt(face), [point.x, point.y], level); | |
}; | |
//static method to construct | |
S2.S2Cell.FromLatLng = function (latLng, level) { | |
if ((!latLng.lat && latLng.lat !== 0) || (!latLng.lng && latLng.lng !== 0)) { | |
throw new Error("Pass { lat: lat, lng: lng } to S2.S2Cell.FromLatLng"); | |
} | |
var xyz = S2.LatLngToXYZ(latLng); | |
var faceuv = S2.XYZToFaceUV(xyz); | |
var st = S2.UVToST(faceuv[1]); | |
var ij = S2.STToIJ(st, level); | |
return S2.S2Cell.FromFaceIJ(faceuv[0], ij, level); | |
}; | |
/* | |
S2.faceIjLevelToXyz = function (face, ij, level) { | |
var st = S2.IJToST(ij, level, [0.5, 0.5]); | |
var uv = S2.STToUV(st); | |
var xyz = S2.FaceUVToXYZ(face, uv); | |
return S2.XYZToLatLng(xyz); | |
return xyz; | |
}; | |
*/ | |
S2.S2Cell.FromFaceIJ = function (face, ij, level) { | |
var cell = new S2.S2Cell(); | |
cell.face = face; | |
cell.ij = ij; | |
cell.level = level; | |
return cell; | |
}; | |
S2.S2Cell.prototype.toString = function () { | |
return 'F' + this.face + 'ij[' + this.ij[0] + ',' + this.ij[1] + ']@' + this.level; | |
}; | |
S2.S2Cell.prototype.getLatLng = function () { | |
var st = S2.IJToST(this.ij, this.level, [0.5, 0.5]); | |
var uv = S2.STToUV(st); | |
var xyz = S2.FaceUVToXYZ(this.face, uv); | |
return S2.XYZToLatLng(xyz); | |
}; | |
S2.S2Cell.prototype.getCornerLatLngs = function () { | |
var result = []; | |
var offsets = [ | |
[0.0, 0.0], | |
[0.0, 1.0], | |
[1.0, 1.0], | |
[1.0, 0.0] | |
]; | |
for (var i = 0; i < 4; i++) { | |
var st = S2.IJToST(this.ij, this.level, offsets[i]); | |
var uv = S2.STToUV(st); | |
var xyz = S2.FaceUVToXYZ(this.face, uv); | |
result.push(S2.XYZToLatLng(xyz)); | |
} | |
return result; | |
}; | |
S2.S2Cell.prototype.getFaceAndQuads = function () { | |
var quads = pointToHilbertQuadList(this.ij[0], this.ij[1], this.level, this.face); | |
return [this.face, quads]; | |
}; | |
S2.S2Cell.prototype.toHilbertQuadkey = function () { | |
var quads = pointToHilbertQuadList(this.ij[0], this.ij[1], this.level, this.face); | |
return this.face.toString(10) + '/' + quads.join(''); | |
}; | |
S2.latLngToNeighborKeys = S2.S2Cell.latLngToNeighborKeys = function (lat, lng, level) { | |
return S2.S2Cell.FromLatLng({ lat: lat, lng: lng }, level).getNeighbors().map(function (cell) { | |
return cell.toHilbertQuadkey(); | |
}); | |
}; | |
S2.S2Cell.prototype.getNeighbors = function () { | |
var fromFaceIJWrap = function (face, ij, level) { | |
var maxSize = (1 << level); | |
if (ij[0] >= 0 && ij[1] >= 0 && ij[0] < maxSize && ij[1] < maxSize) { | |
// no wrapping out of bounds | |
return S2.S2Cell.FromFaceIJ(face, ij, level); | |
} else { | |
// the new i,j are out of range. | |
// with the assumption that they're only a little past the borders we can just take the points as | |
// just beyond the cube face, project to XYZ, then re-create FaceUV from the XYZ vector | |
var st = S2.IJToST(ij, level, [0.5, 0.5]); | |
var uv = S2.STToUV(st); | |
var xyz = S2.FaceUVToXYZ(face, uv); | |
var faceuv = S2.XYZToFaceUV(xyz); | |
face = faceuv[0]; | |
uv = faceuv[1]; | |
st = S2.UVToST(uv); | |
ij = S2.STToIJ(st, level); | |
return S2.S2Cell.FromFaceIJ(face, ij, level); | |
} | |
}; | |
var face = this.face; | |
var i = this.ij[0]; | |
var j = this.ij[1]; | |
var level = this.level; | |
return [ | |
fromFaceIJWrap(face, [i - 1, j], level), | |
fromFaceIJWrap(face, [i, j - 1], level), | |
fromFaceIJWrap(face, [i + 1, j], level), | |
fromFaceIJWrap(face, [i, j + 1], level) | |
]; | |
}; | |
// | |
// Functional Style | |
// | |
S2.FACE_BITS = 3; | |
S2.MAX_LEVEL = 30; | |
S2.POS_BITS = (2 * S2.MAX_LEVEL) + 1; // 61 (60 bits of data, 1 bit lsb marker) | |
S2.facePosLevelToId = S2.S2Cell.facePosLevelToId = S2.fromFacePosLevel = function (faceN, posS, levelN) { | |
var faceB; | |
var posB; | |
var bin; | |
if (!levelN) { | |
levelN = posS.length; | |
} | |
if (posS.length > levelN) { | |
posS = posS.substr(0, levelN); | |
} | |
// 3-bit face value | |
faceB = Long.fromString(faceN.toString(10), true, 10).toString(2); | |
while (faceB.length < S2.FACE_BITS) { | |
faceB = '0' + faceB; | |
} | |
// 60-bit position value | |
posB = Long.fromString(posS, true, 4).toString(2); | |
while (posB.length < (2 * levelN)) { | |
posB = '0' + posB; | |
} | |
bin = faceB + posB; | |
// 1-bit lsb marker | |
bin += '1'; | |
// n-bit padding to 64-bits | |
while (bin.length < (S2.FACE_BITS + S2.POS_BITS)) { | |
bin += '0'; | |
} | |
return Long.fromString(bin, true, 2).toString(10); | |
}; | |
S2.keyToId = S2.S2Cell.keyToId | |
= S2.toId = S2.toCellId = S2.fromKey | |
= function (key) { | |
var parts = key.split('/'); | |
return S2.fromFacePosLevel(parts[0], parts[1], parts[1].length); | |
}; | |
S2.idToKey = S2.S2Cell.idToKey | |
= S2.S2Cell.toKey = S2.toKey | |
= S2.fromId = S2.fromCellId | |
= S2.S2Cell.toHilbertQuadkey = S2.toHilbertQuadkey | |
= function (idS) { | |
var bin = Long.fromString(idS, true, 10).toString(2); | |
while (bin.length < (S2.FACE_BITS + S2.POS_BITS)) { | |
bin = '0' + bin; | |
} | |
// MUST come AFTER binstr has been left-padded with '0's | |
var lsbIndex = bin.lastIndexOf('1'); | |
// substr(start, len) | |
// substring(start, end) // includes start, does not include end | |
var faceB = bin.substring(0, 3); | |
// posB will always be a multiple of 2 (or it's invalid) | |
var posB = bin.substring(3, lsbIndex); | |
var levelN = posB.length / 2; | |
var faceS = Long.fromString(faceB, true, 2).toString(10); | |
var posS = Long.fromString(posB, true, 2).toString(4); | |
while (posS.length < levelN) { | |
posS = '0' + posS; | |
} | |
return faceS + '/' + posS; | |
}; | |
S2.keyToLatLng = S2.S2Cell.keyToLatLng = function (key) { | |
var cell2 = S2.S2Cell.FromHilbertQuadKey(key); | |
return cell2.getLatLng(); | |
}; | |
S2.idToLatLng = S2.S2Cell.idToLatLng = function (id) { | |
var key = S2.idToKey(id); | |
return S2.keyToLatLng(key); | |
}; | |
S2.S2Cell.latLngToKey = S2.latLngToKey | |
= S2.latLngToQuadkey = function (lat, lng, level) { | |
if (isNaN(level) || level < 1 || level > 30) { | |
throw new Error("'level' is not a number between 1 and 30 (but it should be)"); | |
} | |
// TODO | |
// | |
// S2.idToLatLng(id) | |
// S2.keyToLatLng(key) | |
// S2.nextFace(key) // prevent wrapping on nextKey | |
// S2.prevFace(key) // prevent wrapping on prevKey | |
// | |
// .toKeyArray(id) // face,quadtree | |
// .toKey(id) // hilbert | |
// .toPoint(id) // ij | |
// .toId(key) // uint64 (as string) | |
// .toLong(key) // long.js | |
// .toLatLng(id) // object? or array?, or string (with comma)? | |
// | |
// maybe S2.HQ.x, S2.GPS.x, S2.CI.x? | |
return S2.S2Cell.FromLatLng({ lat: lat, lng: lng }, level).toHilbertQuadkey(); | |
}; | |
S2.S2Cell.latLngToId = S2.latLngToId = function (lat, lng, level) { | |
return S2.keyToId(S2.S2Cell.latLngToKey(lat, lng, level)); | |
}; | |
S2.stepKey = function (key, num) { | |
var parts = key.split('/'); | |
var faceS = parts[0]; | |
var posS = parts[1]; | |
var level = parts[1].length; | |
var posL = Long.fromString(posS, true, 4); | |
// TODO handle wrapping (0 === pos + 1) | |
// (only on the 12 edges of the globe) | |
var otherL; | |
if (num > 0) { | |
otherL = posL.add(Math.abs(num)); | |
} | |
else if (num < 0) { | |
otherL = posL.subtract(Math.abs(num)); | |
} | |
var otherS = otherL.toString(4); | |
if ('0' === otherS) { | |
console.warning(new Error("face/position wrapping is not yet supported")); | |
} | |
while (otherS.length < level) { | |
otherS = '0' + otherS; | |
} | |
return faceS + '/' + otherS; | |
}; | |
S2.S2Cell.prevKey = S2.prevKey = function (key) { | |
return S2.stepKey(key, -1); | |
}; | |
S2.S2Cell.nextKey = S2.nextKey = function (key) { | |
return S2.stepKey(key, 1); | |
}; | |
return S2 | |
})({}); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment