You're Invited:Meet the Socket Team at BlackHat and DEF CON in Las Vegas, Aug 4-6.RSVP →
Socket
Book a DemoInstallSign in
Socket
Book a DemoInstallSign in

supercluster

Package Overview
Dependencies
Maintainers
29
Versions
26
Alerts
File Explorer

Advanced tools

License
Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

supercluster - npm Package Compare versions

Comparing version

7.1.5
to
8.0.0

1027

dist/supercluster.js

@@ -7,190 +7,330 @@ (function (global, factory) {

function sortKD(ids, coords, nodeSize, left, right, depth) {
if (right - left <= nodeSize) { return; }
const ARRAY_TYPES = [
Int8Array, Uint8Array, Uint8ClampedArray, Int16Array, Uint16Array,
Int32Array, Uint32Array, Float32Array, Float64Array
];
var m = (left + right) >> 1;
/** @typedef {Int8ArrayConstructor | Uint8ArrayConstructor | Uint8ClampedArrayConstructor | Int16ArrayConstructor | Uint16ArrayConstructor | Int32ArrayConstructor | Uint32ArrayConstructor | Float32ArrayConstructor | Float64ArrayConstructor} TypedArrayConstructor */
select(ids, coords, m, left, right, depth % 2);
const VERSION = 1; // serialized format version
const HEADER_SIZE = 8;
sortKD(ids, coords, nodeSize, left, m - 1, depth + 1);
sortKD(ids, coords, nodeSize, m + 1, right, depth + 1);
}
class KDBush {
function select(ids, coords, k, left, right, inc) {
while (right > left) {
if (right - left > 600) {
var n = right - left + 1;
var m = k - left + 1;
var z = Math.log(n);
var s = 0.5 * Math.exp(2 * z / 3);
var sd = 0.5 * Math.sqrt(z * s * (n - s) / n) * (m - n / 2 < 0 ? -1 : 1);
var newLeft = Math.max(left, Math.floor(k - m * s / n + sd));
var newRight = Math.min(right, Math.floor(k + (n - m) * s / n + sd));
select(ids, coords, k, newLeft, newRight, inc);
/**
* Creates an index from raw `ArrayBuffer` data.
* @param {ArrayBuffer} data
*/
static from(data) {
if (!(data instanceof ArrayBuffer)) {
throw new Error('Data must be an instance of ArrayBuffer.');
}
const [magic, versionAndType] = new Uint8Array(data, 0, 2);
if (magic !== 0xdb) {
throw new Error('Data does not appear to be in a KDBush format.');
}
const version = versionAndType >> 4;
if (version !== VERSION) {
throw new Error(`Got v${version} data when expected v${VERSION}.`);
}
const ArrayType = ARRAY_TYPES[versionAndType & 0x0f];
if (!ArrayType) {
throw new Error('Unrecognized array type.');
}
const [nodeSize] = new Uint16Array(data, 2, 1);
const [numItems] = new Uint32Array(data, 4, 1);
var t = coords[2 * k + inc];
var i = left;
var j = right;
return new KDBush(numItems, nodeSize, ArrayType, data);
}
swapItem(ids, coords, left, k);
if (coords[2 * right + inc] > t) { swapItem(ids, coords, left, right); }
/**
* Creates an index that will hold a given number of items.
* @param {number} numItems
* @param {number} [nodeSize=64] Size of the KD-tree node (64 by default).
* @param {TypedArrayConstructor} [ArrayType=Float64Array] The array type used for coordinates storage (`Float64Array` by default).
* @param {ArrayBuffer} [data] (For internal use only)
*/
constructor(numItems, nodeSize = 64, ArrayType = Float64Array, data) {
if (isNaN(numItems) || numItems <= 0) throw new Error(`Unpexpected numItems value: ${numItems}.`);
while (i < j) {
swapItem(ids, coords, i, j);
i++;
j--;
while (coords[2 * i + inc] < t) { i++; }
while (coords[2 * j + inc] > t) { j--; }
this.numItems = +numItems;
this.nodeSize = Math.min(Math.max(+nodeSize, 2), 65535);
this.ArrayType = ArrayType;
this.IndexArrayType = numItems < 65536 ? Uint16Array : Uint32Array;
const arrayTypeIndex = ARRAY_TYPES.indexOf(this.ArrayType);
const coordsByteSize = numItems * 2 * this.ArrayType.BYTES_PER_ELEMENT;
const idsByteSize = numItems * this.IndexArrayType.BYTES_PER_ELEMENT;
const padCoords = (8 - idsByteSize % 8) % 8;
if (arrayTypeIndex < 0) {
throw new Error(`Unexpected typed array class: ${ArrayType}.`);
}
if (coords[2 * left + inc] === t) { swapItem(ids, coords, left, j); }
else {
j++;
swapItem(ids, coords, j, right);
if (data && (data instanceof ArrayBuffer)) { // reconstruct an index from a buffer
this.data = data;
this.ids = new this.IndexArrayType(this.data, HEADER_SIZE, numItems);
this.coords = new this.ArrayType(this.data, HEADER_SIZE + idsByteSize + padCoords, numItems * 2);
this._pos = numItems * 2;
this._finished = true;
} else { // initialize a new index
this.data = new ArrayBuffer(HEADER_SIZE + coordsByteSize + idsByteSize + padCoords);
this.ids = new this.IndexArrayType(this.data, HEADER_SIZE, numItems);
this.coords = new this.ArrayType(this.data, HEADER_SIZE + idsByteSize + padCoords, numItems * 2);
this._pos = 0;
this._finished = false;
// set header
new Uint8Array(this.data, 0, 2).set([0xdb, (VERSION << 4) + arrayTypeIndex]);
new Uint16Array(this.data, 2, 1)[0] = nodeSize;
new Uint32Array(this.data, 4, 1)[0] = numItems;
}
}
if (j <= k) { left = j + 1; }
if (k <= j) { right = j - 1; }
/**
* Add a point to the index.
* @param {number} x
* @param {number} y
* @returns {number} An incremental index associated with the added item (starting from `0`).
*/
add(x, y) {
const index = this._pos >> 1;
this.ids[index] = index;
this.coords[this._pos++] = x;
this.coords[this._pos++] = y;
return index;
}
}
function swapItem(ids, coords, i, j) {
swap(ids, i, j);
swap(coords, 2 * i, 2 * j);
swap(coords, 2 * i + 1, 2 * j + 1);
}
/**
* Perform indexing of the added points.
*/
finish() {
const numAdded = this._pos >> 1;
if (numAdded !== this.numItems) {
throw new Error(`Added ${numAdded} items when expected ${this.numItems}.`);
}
// kd-sort both arrays for efficient search
sort(this.ids, this.coords, this.nodeSize, 0, this.numItems - 1, 0);
function swap(arr, i, j) {
var tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
this._finished = true;
return this;
}
function range(ids, coords, minX, minY, maxX, maxY, nodeSize) {
var stack = [0, ids.length - 1, 0];
var result = [];
var x, y;
/**
* Search the index for items within a given bounding box.
* @param {number} minX
* @param {number} minY
* @param {number} maxX
* @param {number} maxY
* @returns {number[]} An array of indices correponding to the found items.
*/
range(minX, minY, maxX, maxY) {
if (!this._finished) throw new Error('Data not yet indexed - call index.finish().');
while (stack.length) {
var axis = stack.pop();
var right = stack.pop();
var left = stack.pop();
const {ids, coords, nodeSize} = this;
const stack = [0, ids.length - 1, 0];
const result = [];
if (right - left <= nodeSize) {
for (var i = left; i <= right; i++) {
x = coords[2 * i];
y = coords[2 * i + 1];
if (x >= minX && x <= maxX && y >= minY && y <= maxY) { result.push(ids[i]); }
// recursively search for items in range in the kd-sorted arrays
while (stack.length) {
const axis = stack.pop() || 0;
const right = stack.pop() || 0;
const left = stack.pop() || 0;
// if we reached "tree node", search linearly
if (right - left <= nodeSize) {
for (let i = left; i <= right; i++) {
const x = coords[2 * i];
const y = coords[2 * i + 1];
if (x >= minX && x <= maxX && y >= minY && y <= maxY) result.push(ids[i]);
}
continue;
}
continue;
}
var m = Math.floor((left + right) / 2);
// otherwise find the middle index
const m = (left + right) >> 1;
x = coords[2 * m];
y = coords[2 * m + 1];
// include the middle item if it's in range
const x = coords[2 * m];
const y = coords[2 * m + 1];
if (x >= minX && x <= maxX && y >= minY && y <= maxY) result.push(ids[m]);
if (x >= minX && x <= maxX && y >= minY && y <= maxY) { result.push(ids[m]); }
// queue search in halves that intersect the query
if (axis === 0 ? minX <= x : minY <= y) {
stack.push(left);
stack.push(m - 1);
stack.push(1 - axis);
}
if (axis === 0 ? maxX >= x : maxY >= y) {
stack.push(m + 1);
stack.push(right);
stack.push(1 - axis);
}
}
var nextAxis = (axis + 1) % 2;
if (axis === 0 ? minX <= x : minY <= y) {
stack.push(left);
stack.push(m - 1);
stack.push(nextAxis);
}
if (axis === 0 ? maxX >= x : maxY >= y) {
stack.push(m + 1);
stack.push(right);
stack.push(nextAxis);
}
return result;
}
return result;
}
/**
* Search the index for items within a given radius.
* @param {number} qx
* @param {number} qy
* @param {number} r Query radius.
* @returns {number[]} An array of indices correponding to the found items.
*/
within(qx, qy, r) {
if (!this._finished) throw new Error('Data not yet indexed - call index.finish().');
function within(ids, coords, qx, qy, r, nodeSize) {
var stack = [0, ids.length - 1, 0];
var result = [];
var r2 = r * r;
const {ids, coords, nodeSize} = this;
const stack = [0, ids.length - 1, 0];
const result = [];
const r2 = r * r;
while (stack.length) {
var axis = stack.pop();
var right = stack.pop();
var left = stack.pop();
// recursively search for items within radius in the kd-sorted arrays
while (stack.length) {
const axis = stack.pop() || 0;
const right = stack.pop() || 0;
const left = stack.pop() || 0;
if (right - left <= nodeSize) {
for (var i = left; i <= right; i++) {
if (sqDist(coords[2 * i], coords[2 * i + 1], qx, qy) <= r2) { result.push(ids[i]); }
// if we reached "tree node", search linearly
if (right - left <= nodeSize) {
for (let i = left; i <= right; i++) {
if (sqDist(coords[2 * i], coords[2 * i + 1], qx, qy) <= r2) result.push(ids[i]);
}
continue;
}
continue;
}
var m = Math.floor((left + right) / 2);
// otherwise find the middle index
const m = (left + right) >> 1;
var x = coords[2 * m];
var y = coords[2 * m + 1];
// include the middle item if it's in range
const x = coords[2 * m];
const y = coords[2 * m + 1];
if (sqDist(x, y, qx, qy) <= r2) result.push(ids[m]);
if (sqDist(x, y, qx, qy) <= r2) { result.push(ids[m]); }
// queue search in halves that intersect the query
if (axis === 0 ? qx - r <= x : qy - r <= y) {
stack.push(left);
stack.push(m - 1);
stack.push(1 - axis);
}
if (axis === 0 ? qx + r >= x : qy + r >= y) {
stack.push(m + 1);
stack.push(right);
stack.push(1 - axis);
}
}
var nextAxis = (axis + 1) % 2;
if (axis === 0 ? qx - r <= x : qy - r <= y) {
stack.push(left);
stack.push(m - 1);
stack.push(nextAxis);
}
if (axis === 0 ? qx + r >= x : qy + r >= y) {
stack.push(m + 1);
stack.push(right);
stack.push(nextAxis);
}
return result;
}
return result;
}
function sqDist(ax, ay, bx, by) {
var dx = ax - bx;
var dy = ay - by;
return dx * dx + dy * dy;
/**
* @param {Uint16Array | Uint32Array} ids
* @param {InstanceType<TypedArrayConstructor>} coords
* @param {number} nodeSize
* @param {number} left
* @param {number} right
* @param {number} axis
*/
function sort(ids, coords, nodeSize, left, right, axis) {
if (right - left <= nodeSize) return;
const m = (left + right) >> 1; // middle index
// sort ids and coords around the middle index so that the halves lie
// either left/right or top/bottom correspondingly (taking turns)
select(ids, coords, m, left, right, axis);
// recursively kd-sort first half and second half on the opposite axis
sort(ids, coords, nodeSize, left, m - 1, 1 - axis);
sort(ids, coords, nodeSize, m + 1, right, 1 - axis);
}
var defaultGetX = function (p) { return p[0]; };
var defaultGetY = function (p) { return p[1]; };
/**
* Custom Floyd-Rivest selection algorithm: sort ids and coords so that
* [left..k-1] items are smaller than k-th item (on either x or y axis)
* @param {Uint16Array | Uint32Array} ids
* @param {InstanceType<TypedArrayConstructor>} coords
* @param {number} k
* @param {number} left
* @param {number} right
* @param {number} axis
*/
function select(ids, coords, k, left, right, axis) {
var KDBush = function KDBush(points, getX, getY, nodeSize, ArrayType) {
if ( getX === void 0 ) getX = defaultGetX;
if ( getY === void 0 ) getY = defaultGetY;
if ( nodeSize === void 0 ) nodeSize = 64;
if ( ArrayType === void 0 ) ArrayType = Float64Array;
while (right > left) {
if (right - left > 600) {
const n = right - left + 1;
const m = k - left + 1;
const z = Math.log(n);
const s = 0.5 * Math.exp(2 * z / 3);
const sd = 0.5 * Math.sqrt(z * s * (n - s) / n) * (m - n / 2 < 0 ? -1 : 1);
const newLeft = Math.max(left, Math.floor(k - m * s / n + sd));
const newRight = Math.min(right, Math.floor(k + (n - m) * s / n + sd));
select(ids, coords, k, newLeft, newRight, axis);
}
this.nodeSize = nodeSize;
this.points = points;
const t = coords[2 * k + axis];
let i = left;
let j = right;
var IndexArrayType = points.length < 65536 ? Uint16Array : Uint32Array;
swapItem(ids, coords, left, k);
if (coords[2 * right + axis] > t) swapItem(ids, coords, left, right);
var ids = this.ids = new IndexArrayType(points.length);
var coords = this.coords = new ArrayType(points.length * 2);
while (i < j) {
swapItem(ids, coords, i, j);
i++;
j--;
while (coords[2 * i + axis] < t) i++;
while (coords[2 * j + axis] > t) j--;
}
for (var i = 0; i < points.length; i++) {
ids[i] = i;
coords[2 * i] = getX(points[i]);
coords[2 * i + 1] = getY(points[i]);
if (coords[2 * left + axis] === t) swapItem(ids, coords, left, j);
else {
j++;
swapItem(ids, coords, j, right);
}
if (j <= k) left = j + 1;
if (k <= j) right = j - 1;
}
}
sortKD(ids, coords, nodeSize, 0, ids.length - 1, 0);
};
/**
* @param {Uint16Array | Uint32Array} ids
* @param {InstanceType<TypedArrayConstructor>} coords
* @param {number} i
* @param {number} j
*/
function swapItem(ids, coords, i, j) {
swap(ids, i, j);
swap(coords, 2 * i, 2 * j);
swap(coords, 2 * i + 1, 2 * j + 1);
}
KDBush.prototype.range = function range$1 (minX, minY, maxX, maxY) {
return range(this.ids, this.coords, minX, minY, maxX, maxY, this.nodeSize);
};
/**
* @param {InstanceType<TypedArrayConstructor>} arr
* @param {number} i
* @param {number} j
*/
function swap(arr, i, j) {
const tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
KDBush.prototype.within = function within$1 (x, y, r) {
return within(this.ids, this.coords, x, y, r, this.nodeSize);
};
/**
* @param {number} ax
* @param {number} ay
* @param {number} bx
* @param {number} by
*/
function sqDist(ax, ay, bx, by) {
const dx = ax - bx;
const dy = ay - by;
return dx * dx + dy * dy;
}
var defaultOptions = {
const defaultOptions = {
minZoom: 0, // min zoom to generate clusters on

@@ -211,377 +351,370 @@ maxZoom: 16, // max zoom level to cluster the points on

// properties to use for individual points when running the reducer
map: function (props) { return props; } // props => ({sum: props.my_value})
map: props => props // props => ({sum: props.my_value})
};
var fround = Math.fround || (function (tmp) { return (function (x) { tmp[0] = +x; return tmp[0]; }); })(new Float32Array(1));
const fround = Math.fround || (tmp => ((x) => { tmp[0] = +x; return tmp[0]; }))(new Float32Array(1));
var Supercluster = function Supercluster(options) {
this.options = extend(Object.create(defaultOptions), options);
this.trees = new Array(this.options.maxZoom + 1);
};
const OFFSET_ZOOM = 2;
const OFFSET_ID = 3;
const OFFSET_PARENT = 4;
const OFFSET_NUM = 5;
const OFFSET_PROP = 6;
Supercluster.prototype.load = function load (points) {
var ref = this.options;
var log = ref.log;
var minZoom = ref.minZoom;
var maxZoom = ref.maxZoom;
var nodeSize = ref.nodeSize;
class Supercluster {
constructor(options) {
this.options = Object.assign(Object.create(defaultOptions), options);
this.trees = new Array(this.options.maxZoom + 1);
this.stride = this.options.reduce ? 7 : 6;
this.clusterProps = [];
}
if (log) { console.time('total time'); }
load(points) {
const {log, minZoom, maxZoom} = this.options;
var timerId = "prepare " + (points.length) + " points";
if (log) { console.time(timerId); }
if (log) console.time('total time');
this.points = points;
const timerId = `prepare ${ points.length } points`;
if (log) console.time(timerId);
// generate a cluster object for each point and index input points into a KD-tree
var clusters = [];
for (var i = 0; i < points.length; i++) {
if (!points[i].geometry) { continue; }
clusters.push(createPointCluster(points[i], i));
}
this.trees[maxZoom + 1] = new KDBush(clusters, getX, getY, nodeSize, Float32Array);
this.points = points;
if (log) { console.timeEnd(timerId); }
// generate a cluster object for each point and index input points into a KD-tree
const data = [];
// cluster points on max zoom, then cluster the results on previous zoom, etc.;
// results in a cluster hierarchy across zoom levels
for (var z = maxZoom; z >= minZoom; z--) {
var now = +Date.now();
for (let i = 0; i < points.length; i++) {
const p = points[i];
if (!p.geometry) continue;
// create a new set of clusters for the zoom and index them with a KD-tree
clusters = this._cluster(clusters, z);
this.trees[z] = new KDBush(clusters, getX, getY, nodeSize, Float32Array);
const [lng, lat] = p.geometry.coordinates;
const x = fround(lngX(lng));
const y = fround(latY(lat));
// store internal point/cluster data in flat numeric arrays for performance
data.push(
x, y, // projected point coordinates
Infinity, // the last zoom the point was processed at
i, // index of the source feature in the original input array
-1, // parent cluster id
1 // number of points in a cluster
);
if (this.options.reduce) data.push(0); // noop
}
let tree = this.trees[maxZoom + 1] = this._createTree(data);
if (log) { console.log('z%d: %d clusters in %dms', z, clusters.length, +Date.now() - now); }
}
if (log) console.timeEnd(timerId);
if (log) { console.timeEnd('total time'); }
// cluster points on max zoom, then cluster the results on previous zoom, etc.;
// results in a cluster hierarchy across zoom levels
for (let z = maxZoom; z >= minZoom; z--) {
const now = +Date.now();
return this;
};
// create a new set of clusters for the zoom and index them with a KD-tree
tree = this.trees[z] = this._createTree(this._cluster(tree, z));
Supercluster.prototype.getClusters = function getClusters (bbox, zoom) {
var minLng = ((bbox[0] + 180) % 360 + 360) % 360 - 180;
var minLat = Math.max(-90, Math.min(90, bbox[1]));
var maxLng = bbox[2] === 180 ? 180 : ((bbox[2] + 180) % 360 + 360) % 360 - 180;
var maxLat = Math.max(-90, Math.min(90, bbox[3]));
if (log) console.log('z%d: %d clusters in %dms', z, tree.numItems, +Date.now() - now);
}
if (bbox[2] - bbox[0] >= 360) {
minLng = -180;
maxLng = 180;
} else if (minLng > maxLng) {
var easternHem = this.getClusters([minLng, minLat, 180, maxLat], zoom);
var westernHem = this.getClusters([-180, minLat, maxLng, maxLat], zoom);
return easternHem.concat(westernHem);
if (log) console.timeEnd('total time');
return this;
}
var tree = this.trees[this._limitZoom(zoom)];
var ids = tree.range(lngX(minLng), latY(maxLat), lngX(maxLng), latY(minLat));
var clusters = [];
for (var i = 0, list = ids; i < list.length; i += 1) {
var id = list[i];
getClusters(bbox, zoom) {
let minLng = ((bbox[0] + 180) % 360 + 360) % 360 - 180;
const minLat = Math.max(-90, Math.min(90, bbox[1]));
let maxLng = bbox[2] === 180 ? 180 : ((bbox[2] + 180) % 360 + 360) % 360 - 180;
const maxLat = Math.max(-90, Math.min(90, bbox[3]));
var c = tree.points[id];
clusters.push(c.numPoints ? getClusterJSON(c) : this.points[c.index]);
if (bbox[2] - bbox[0] >= 360) {
minLng = -180;
maxLng = 180;
} else if (minLng > maxLng) {
const easternHem = this.getClusters([minLng, minLat, 180, maxLat], zoom);
const westernHem = this.getClusters([-180, minLat, maxLng, maxLat], zoom);
return easternHem.concat(westernHem);
}
const tree = this.trees[this._limitZoom(zoom)];
const ids = tree.range(lngX(minLng), latY(maxLat), lngX(maxLng), latY(minLat));
const data = tree.data;
const clusters = [];
for (const id of ids) {
const k = this.stride * id;
clusters.push(data[k + OFFSET_NUM] > 1 ? getClusterJSON(data, k, this.clusterProps) : this.points[data[k + OFFSET_ID]]);
}
return clusters;
}
return clusters;
};
Supercluster.prototype.getChildren = function getChildren (clusterId) {
var originId = this._getOriginId(clusterId);
var originZoom = this._getOriginZoom(clusterId);
var errorMsg = 'No cluster with the specified id.';
getChildren(clusterId) {
const originId = this._getOriginId(clusterId);
const originZoom = this._getOriginZoom(clusterId);
const errorMsg = 'No cluster with the specified id.';
var index = this.trees[originZoom];
if (!index) { throw new Error(errorMsg); }
const tree = this.trees[originZoom];
if (!tree) throw new Error(errorMsg);
var origin = index.points[originId];
if (!origin) { throw new Error(errorMsg); }
const data = tree.data;
if (originId * this.stride >= data.length) throw new Error(errorMsg);
var r = this.options.radius / (this.options.extent * Math.pow(2, originZoom - 1));
var ids = index.within(origin.x, origin.y, r);
var children = [];
for (var i = 0, list = ids; i < list.length; i += 1) {
var id = list[i];
var c = index.points[id];
if (c.parentId === clusterId) {
children.push(c.numPoints ? getClusterJSON(c) : this.points[c.index]);
const r = this.options.radius / (this.options.extent * Math.pow(2, originZoom - 1));
const x = data[originId * this.stride];
const y = data[originId * this.stride + 1];
const ids = tree.within(x, y, r);
const children = [];
for (const id of ids) {
const k = id * this.stride;
if (data[k + OFFSET_PARENT] === clusterId) {
children.push(data[k + OFFSET_NUM] > 1 ? getClusterJSON(data, k, this.clusterProps) : this.points[data[k + OFFSET_ID]]);
}
}
}
if (children.length === 0) { throw new Error(errorMsg); }
if (children.length === 0) throw new Error(errorMsg);
return children;
};
return children;
}
Supercluster.prototype.getLeaves = function getLeaves (clusterId, limit, offset) {
limit = limit || 10;
offset = offset || 0;
getLeaves(clusterId, limit, offset) {
limit = limit || 10;
offset = offset || 0;
var leaves = [];
this._appendLeaves(leaves, clusterId, limit, offset, 0);
const leaves = [];
this._appendLeaves(leaves, clusterId, limit, offset, 0);
return leaves;
};
return leaves;
}
Supercluster.prototype.getTile = function getTile (z, x, y) {
var tree = this.trees[this._limitZoom(z)];
var z2 = Math.pow(2, z);
var ref = this.options;
var extent = ref.extent;
var radius = ref.radius;
var p = radius / extent;
var top = (y - p) / z2;
var bottom = (y + 1 + p) / z2;
getTile(z, x, y) {
const tree = this.trees[this._limitZoom(z)];
const z2 = Math.pow(2, z);
const {extent, radius} = this.options;
const p = radius / extent;
const top = (y - p) / z2;
const bottom = (y + 1 + p) / z2;
var tile = {
features: []
};
const tile = {
features: []
};
this._addTileFeatures(
tree.range((x - p) / z2, top, (x + 1 + p) / z2, bottom),
tree.points, x, y, z2, tile);
if (x === 0) {
this._addTileFeatures(
tree.range(1 - p / z2, top, 1, bottom),
tree.points, z2, y, z2, tile);
}
if (x === z2 - 1) {
this._addTileFeatures(
tree.range(0, top, p / z2, bottom),
tree.points, -1, y, z2, tile);
}
tree.range((x - p) / z2, top, (x + 1 + p) / z2, bottom),
tree.data, x, y, z2, tile);
return tile.features.length ? tile : null;
};
if (x === 0) {
this._addTileFeatures(
tree.range(1 - p / z2, top, 1, bottom),
tree.data, z2, y, z2, tile);
}
if (x === z2 - 1) {
this._addTileFeatures(
tree.range(0, top, p / z2, bottom),
tree.data, -1, y, z2, tile);
}
Supercluster.prototype.getClusterExpansionZoom = function getClusterExpansionZoom (clusterId) {
var expansionZoom = this._getOriginZoom(clusterId) - 1;
while (expansionZoom <= this.options.maxZoom) {
var children = this.getChildren(clusterId);
expansionZoom++;
if (children.length !== 1) { break; }
clusterId = children[0].properties.cluster_id;
return tile.features.length ? tile : null;
}
return expansionZoom;
};
Supercluster.prototype._appendLeaves = function _appendLeaves (result, clusterId, limit, offset, skipped) {
var children = this.getChildren(clusterId);
getClusterExpansionZoom(clusterId) {
let expansionZoom = this._getOriginZoom(clusterId) - 1;
while (expansionZoom <= this.options.maxZoom) {
const children = this.getChildren(clusterId);
expansionZoom++;
if (children.length !== 1) break;
clusterId = children[0].properties.cluster_id;
}
return expansionZoom;
}
for (var i = 0, list = children; i < list.length; i += 1) {
var child = list[i];
_appendLeaves(result, clusterId, limit, offset, skipped) {
const children = this.getChildren(clusterId);
var props = child.properties;
for (const child of children) {
const props = child.properties;
if (props && props.cluster) {
if (skipped + props.point_count <= offset) {
// skip the whole cluster
skipped += props.point_count;
if (props && props.cluster) {
if (skipped + props.point_count <= offset) {
// skip the whole cluster
skipped += props.point_count;
} else {
// enter the cluster
skipped = this._appendLeaves(result, props.cluster_id, limit, offset, skipped);
// exit the cluster
}
} else if (skipped < offset) {
// skip a single point
skipped++;
} else {
// enter the cluster
skipped = this._appendLeaves(result, props.cluster_id, limit, offset, skipped);
// exit the cluster
// add a single point
result.push(child);
}
} else if (skipped < offset) {
// skip a single point
skipped++;
} else {
// add a single point
result.push(child);
if (result.length === limit) break;
}
if (result.length === limit) { break; }
return skipped;
}
return skipped;
};
_createTree(data) {
const tree = new KDBush(data.length / this.stride | 0, this.options.nodeSize, Float32Array);
for (let i = 0; i < data.length; i += this.stride) tree.add(data[i], data[i + 1]);
tree.finish();
tree.data = data;
return tree;
}
Supercluster.prototype._addTileFeatures = function _addTileFeatures (ids, points, x, y, z2, tile) {
for (var i$1 = 0, list = ids; i$1 < list.length; i$1 += 1) {
var i = list[i$1];
_addTileFeatures(ids, data, x, y, z2, tile) {
for (const i of ids) {
const k = i * this.stride;
const isCluster = data[k + OFFSET_NUM] > 1;
var c = points[i];
var isCluster = c.numPoints;
let tags, px, py;
if (isCluster) {
tags = getClusterProperties(data, k, this.clusterProps);
px = data[k];
py = data[k + 1];
} else {
const p = this.points[data[k + OFFSET_ID]];
tags = p.properties;
const [lng, lat] = p.geometry.coordinates;
px = lngX(lng);
py = latY(lat);
}
var tags = (void 0), px = (void 0), py = (void 0);
if (isCluster) {
tags = getClusterProperties(c);
px = c.x;
py = c.y;
} else {
var p = this.points[c.index];
tags = p.properties;
px = lngX(p.geometry.coordinates[0]);
py = latY(p.geometry.coordinates[1]);
}
const f = {
type: 1,
geometry: [[
Math.round(this.options.extent * (px * z2 - x)),
Math.round(this.options.extent * (py * z2 - y))
]],
tags
};
var f = {
type: 1,
geometry: [[
Math.round(this.options.extent * (px * z2 - x)),
Math.round(this.options.extent * (py * z2 - y))
]],
tags: tags
};
// assign id
let id;
if (isCluster || this.options.generateId) {
// optionally generate id for points
id = data[k + OFFSET_ID];
} else {
// keep id if already assigned
id = this.points[data[k + OFFSET_ID]].id;
}
// assign id
var id = (void 0);
if (isCluster) {
id = c.id;
} else if (this.options.generateId) {
// optionally generate id
id = c.index;
} else if (this.points[c.index].id) {
// keep id if already assigned
id = this.points[c.index].id;
if (id !== undefined) f.id = id;
tile.features.push(f);
}
}
if (id !== undefined) { f.id = id; }
tile.features.push(f);
_limitZoom(z) {
return Math.max(this.options.minZoom, Math.min(Math.floor(+z), this.options.maxZoom + 1));
}
};
Supercluster.prototype._limitZoom = function _limitZoom (z) {
return Math.max(this.options.minZoom, Math.min(Math.floor(+z), this.options.maxZoom + 1));
};
_cluster(tree, zoom) {
const {radius, extent, reduce, minPoints} = this.options;
const r = radius / (extent * Math.pow(2, zoom));
const data = tree.data;
const nextData = [];
const stride = this.stride;
Supercluster.prototype._cluster = function _cluster (points, zoom) {
var clusters = [];
var ref = this.options;
var radius = ref.radius;
var extent = ref.extent;
var reduce = ref.reduce;
var minPoints = ref.minPoints;
var r = radius / (extent * Math.pow(2, zoom));
// loop through each point
for (let i = 0; i < data.length; i += stride) {
// if we've already visited the point at this zoom level, skip it
if (data[i + OFFSET_ZOOM] <= zoom) continue;
data[i + OFFSET_ZOOM] = zoom;
// loop through each point
for (var i = 0; i < points.length; i++) {
var p = points[i];
// if we've already visited the point at this zoom level, skip it
if (p.zoom <= zoom) { continue; }
p.zoom = zoom;
// find all nearby points
const x = data[i];
const y = data[i + 1];
const neighborIds = tree.within(data[i], data[i + 1], r);
// find all nearby points
var tree = this.trees[zoom + 1];
var neighborIds = tree.within(p.x, p.y, r);
const numPointsOrigin = data[i + OFFSET_NUM];
let numPoints = numPointsOrigin;
var numPointsOrigin = p.numPoints || 1;
var numPoints = numPointsOrigin;
// count the number of points in a potential cluster
for (const neighborId of neighborIds) {
const k = neighborId * stride;
// filter out neighbors that are already processed
if (data[k + OFFSET_ZOOM] > zoom) numPoints += data[k + OFFSET_NUM];
}
// count the number of points in a potential cluster
for (var i$1 = 0, list = neighborIds; i$1 < list.length; i$1 += 1) {
var neighborId = list[i$1];
// if there were neighbors to merge, and there are enough points to form a cluster
if (numPoints > numPointsOrigin && numPoints >= minPoints) {
let wx = x * numPointsOrigin;
let wy = y * numPointsOrigin;
var b = tree.points[neighborId];
// filter out neighbors that are already processed
if (b.zoom > zoom) { numPoints += b.numPoints || 1; }
}
let clusterProperties;
let clusterPropIndex = -1;
// if there were neighbors to merge, and there are enough points to form a cluster
if (numPoints > numPointsOrigin && numPoints >= minPoints) {
var wx = p.x * numPointsOrigin;
var wy = p.y * numPointsOrigin;
// encode both zoom and point index on which the cluster originated -- offset by total length of features
const id = ((i / stride | 0) << 5) + (zoom + 1) + this.points.length;
var clusterProperties = reduce && numPointsOrigin > 1 ? this._map(p, true) : null;
for (const neighborId of neighborIds) {
const k = neighborId * stride;
// encode both zoom and point index on which the cluster originated -- offset by total length of features
var id = (i << 5) + (zoom + 1) + this.points.length;
if (data[k + OFFSET_ZOOM] <= zoom) continue;
data[k + OFFSET_ZOOM] = zoom; // save the zoom (so it doesn't get processed twice)
for (var i$2 = 0, list$1 = neighborIds; i$2 < list$1.length; i$2 += 1) {
var neighborId$1 = list$1[i$2];
const numPoints2 = data[k + OFFSET_NUM];
wx += data[k] * numPoints2; // accumulate coordinates for calculating weighted center
wy += data[k + 1] * numPoints2;
var b$1 = tree.points[neighborId$1];
data[k + OFFSET_PARENT] = id;
if (b$1.zoom <= zoom) { continue; }
b$1.zoom = zoom; // save the zoom (so it doesn't get processed twice)
var numPoints2 = b$1.numPoints || 1;
wx += b$1.x * numPoints2; // accumulate coordinates for calculating weighted center
wy += b$1.y * numPoints2;
b$1.parentId = id;
if (reduce) {
if (!clusterProperties) { clusterProperties = this._map(p, true); }
reduce(clusterProperties, this._map(b$1));
if (reduce) {
if (!clusterProperties) {
clusterProperties = this._map(data, i, true);
clusterPropIndex = this.clusterProps.length;
this.clusterProps.push(clusterProperties);
}
reduce(clusterProperties, this._map(data, k));
}
}
}
p.parentId = id;
clusters.push(createCluster(wx / numPoints, wy / numPoints, id, numPoints, clusterProperties));
data[i + OFFSET_PARENT] = id;
nextData.push(wx / numPoints, wy / numPoints, Infinity, id, -1, numPoints);
if (reduce) nextData.push(clusterPropIndex);
} else { // left points as unclustered
clusters.push(p);
} else { // left points as unclustered
for (let j = 0; j < stride; j++) nextData.push(data[i + j]);
if (numPoints > 1) {
for (var i$3 = 0, list$2 = neighborIds; i$3 < list$2.length; i$3 += 1) {
var neighborId$2 = list$2[i$3];
var b$2 = tree.points[neighborId$2];
if (b$2.zoom <= zoom) { continue; }
b$2.zoom = zoom;
clusters.push(b$2);
if (numPoints > 1) {
for (const neighborId of neighborIds) {
const k = neighborId * stride;
if (data[k + OFFSET_ZOOM] <= zoom) continue;
data[k + OFFSET_ZOOM] = zoom;
for (let j = 0; j < stride; j++) nextData.push(data[k + j]);
}
}
}
}
return nextData;
}
return clusters;
};
// get index of the point from which the cluster originated
_getOriginId(clusterId) {
return (clusterId - this.points.length) >> 5;
}
// get index of the point from which the cluster originated
Supercluster.prototype._getOriginId = function _getOriginId (clusterId) {
return (clusterId - this.points.length) >> 5;
};
// get zoom of the point from which the cluster originated
_getOriginZoom(clusterId) {
return (clusterId - this.points.length) % 32;
}
// get zoom of the point from which the cluster originated
Supercluster.prototype._getOriginZoom = function _getOriginZoom (clusterId) {
return (clusterId - this.points.length) % 32;
};
Supercluster.prototype._map = function _map (point, clone) {
if (point.numPoints) {
return clone ? extend({}, point.properties) : point.properties;
_map(data, i, clone) {
if (data[i + OFFSET_NUM] > 1) {
const props = this.clusterProps[data[i + OFFSET_PROP]];
return clone ? Object.assign({}, props) : props;
}
const original = this.points[data[i + OFFSET_ID]].properties;
const result = this.options.map(original);
return clone && result === original ? Object.assign({}, result) : result;
}
var original = this.points[point.index].properties;
var result = this.options.map(original);
return clone && result === original ? extend({}, result) : result;
};
function createCluster(x, y, id, numPoints, properties) {
return {
x: fround(x), // weighted cluster center; round for consistency with Float32Array index
y: fround(y),
zoom: Infinity, // the last zoom the cluster was processed at
id: id, // encodes index of the first child of the cluster and its zoom level
parentId: -1, // parent cluster id
numPoints: numPoints,
properties: properties
};
}
function createPointCluster(p, id) {
var ref = p.geometry.coordinates;
var x = ref[0];
var y = ref[1];
function getClusterJSON(data, i, clusterProps) {
return {
x: fround(lngX(x)), // projected point coordinates
y: fround(latY(y)),
zoom: Infinity, // the last zoom the point was processed at
index: id, // index of the source feature in the original input array,
parentId: -1 // parent cluster id
};
}
function getClusterJSON(cluster) {
return {
type: 'Feature',
id: cluster.id,
properties: getClusterProperties(cluster),
id: data[i + OFFSET_ID],
properties: getClusterProperties(data, i, clusterProps),
geometry: {
type: 'Point',
coordinates: [xLng(cluster.x), yLat(cluster.y)]
coordinates: [xLng(data[i]), yLat(data[i + 1])]
}

@@ -591,10 +724,12 @@ };

function getClusterProperties(cluster) {
var count = cluster.numPoints;
var abbrev =
count >= 10000 ? ((Math.round(count / 1000)) + "k") :
count >= 1000 ? ((Math.round(count / 100) / 10) + "k") : count;
return extend(extend({}, cluster.properties), {
function getClusterProperties(data, i, clusterProps) {
const count = data[i + OFFSET_NUM];
const abbrev =
count >= 10000 ? `${Math.round(count / 1000) }k` :
count >= 1000 ? `${Math.round(count / 100) / 10 }k` : count;
const propIndex = data[i + OFFSET_PROP];
const properties = propIndex === -1 ? {} : Object.assign({}, clusterProps[propIndex]);
return Object.assign(properties, {
cluster: true,
cluster_id: cluster.id,
cluster_id: data[i + OFFSET_ID],
point_count: count,

@@ -610,4 +745,4 @@ point_count_abbreviated: abbrev

function latY(lat) {
var sin = Math.sin(lat * Math.PI / 180);
var y = (0.5 - 0.25 * Math.log((1 + sin) / (1 - sin)) / Math.PI);
const sin = Math.sin(lat * Math.PI / 180);
const y = (0.5 - 0.25 * Math.log((1 + sin) / (1 - sin)) / Math.PI);
return y < 0 ? 0 : y > 1 ? 1 : y;

@@ -621,20 +756,8 @@ }

function yLat(y) {
var y2 = (180 - y * 360) * Math.PI / 180;
const y2 = (180 - y * 360) * Math.PI / 180;
return 360 * Math.atan(Math.exp(y2)) / Math.PI - 90;
}
function extend(dest, src) {
for (var id in src) { dest[id] = src[id]; }
return dest;
}
function getX(p) {
return p.x;
}
function getY(p) {
return p.y;
}
return Supercluster;
}));

2

dist/supercluster.min.js

@@ -1,1 +0,1 @@

!function(t,o){"object"==typeof exports&&"undefined"!=typeof module?module.exports=o():"function"==typeof define&&define.amd?define(o):(t="undefined"!=typeof globalThis?globalThis:t||self).Supercluster=o()}(this,(function(){"use strict";function t(e,n,r,i,s,a){if(!(s-i<=r)){var p=i+s>>1;o(e,n,p,i,s,a%2),t(e,n,r,i,p-1,a+1),t(e,n,r,p+1,s,a+1)}}function o(t,n,r,i,s,a){for(;s>i;){if(s-i>600){var p=s-i+1,h=r-i+1,u=Math.log(p),f=.5*Math.exp(2*u/3),d=.5*Math.sqrt(u*f*(p-f)/p)*(h-p/2<0?-1:1);o(t,n,r,Math.max(i,Math.floor(r-h*f/p+d)),Math.min(s,Math.floor(r+(p-h)*f/p+d)),a)}var l=n[2*r+a],m=i,c=s;for(e(t,n,i,r),n[2*s+a]>l&&e(t,n,i,s);m<c;){for(e(t,n,m,c),m++,c--;n[2*m+a]<l;)m++;for(;n[2*c+a]>l;)c--}n[2*i+a]===l?e(t,n,i,c):e(t,n,++c,s),c<=r&&(i=c+1),r<=c&&(s=c-1)}}function e(t,o,e,r){n(t,e,r),n(o,2*e,2*r),n(o,2*e+1,2*r+1)}function n(t,o,e){var n=t[o];t[o]=t[e],t[e]=n}function r(t,o,e,n){var r=t-e,i=o-n;return r*r+i*i}var i=function(t){return t[0]},s=function(t){return t[1]},a=function(o,e,n,r,a){void 0===e&&(e=i),void 0===n&&(n=s),void 0===r&&(r=64),void 0===a&&(a=Float64Array),this.nodeSize=r,this.points=o;for(var p=o.length<65536?Uint16Array:Uint32Array,h=this.ids=new p(o.length),u=this.coords=new a(2*o.length),f=0;f<o.length;f++)h[f]=f,u[2*f]=e(o[f]),u[2*f+1]=n(o[f]);t(h,u,r,0,h.length-1,0)};a.prototype.range=function(t,o,e,n){return function(t,o,e,n,r,i,s){for(var a,p,h=[0,t.length-1,0],u=[];h.length;){var f=h.pop(),d=h.pop(),l=h.pop();if(d-l<=s)for(var m=l;m<=d;m++)a=o[2*m],p=o[2*m+1],a>=e&&a<=r&&p>=n&&p<=i&&u.push(t[m]);else{var c=Math.floor((l+d)/2);a=o[2*c],p=o[2*c+1],a>=e&&a<=r&&p>=n&&p<=i&&u.push(t[c]);var v=(f+1)%2;(0===f?e<=a:n<=p)&&(h.push(l),h.push(c-1),h.push(v)),(0===f?r>=a:i>=p)&&(h.push(c+1),h.push(d),h.push(v))}}return u}(this.ids,this.coords,t,o,e,n,this.nodeSize)},a.prototype.within=function(t,o,e){return function(t,o,e,n,i,s){for(var a=[0,t.length-1,0],p=[],h=i*i;a.length;){var u=a.pop(),f=a.pop(),d=a.pop();if(f-d<=s)for(var l=d;l<=f;l++)r(o[2*l],o[2*l+1],e,n)<=h&&p.push(t[l]);else{var m=Math.floor((d+f)/2),c=o[2*m],v=o[2*m+1];r(c,v,e,n)<=h&&p.push(t[m]);var g=(u+1)%2;(0===u?e-i<=c:n-i<=v)&&(a.push(d),a.push(m-1),a.push(g)),(0===u?e+i>=c:n+i>=v)&&(a.push(m+1),a.push(f),a.push(g))}}return p}(this.ids,this.coords,t,o,e,this.nodeSize)};var p,h={minZoom:0,maxZoom:16,minPoints:2,radius:40,extent:512,nodeSize:64,log:!1,generateId:!1,reduce:null,map:function(t){return t}},u=Math.fround||(p=new Float32Array(1),function(t){return p[0]=+t,p[0]}),f=function(t){this.options=y(Object.create(h),t),this.trees=new Array(this.options.maxZoom+1)};function d(t,o,e,n,r){return{x:u(t),y:u(o),zoom:1/0,id:e,parentId:-1,numPoints:n,properties:r}}function l(t,o){var e=t.geometry.coordinates,n=e[0],r=e[1];return{x:u(v(n)),y:u(g(r)),zoom:1/0,index:o,parentId:-1}}function m(t){return{type:"Feature",id:t.id,properties:c(t),geometry:{type:"Point",coordinates:[(n=t.x,360*(n-.5)),(o=t.y,e=(180-360*o)*Math.PI/180,360*Math.atan(Math.exp(e))/Math.PI-90)]}};var o,e,n}function c(t){var o=t.numPoints,e=o>=1e4?Math.round(o/1e3)+"k":o>=1e3?Math.round(o/100)/10+"k":o;return y(y({},t.properties),{cluster:!0,cluster_id:t.id,point_count:o,point_count_abbreviated:e})}function v(t){return t/360+.5}function g(t){var o=Math.sin(t*Math.PI/180),e=.5-.25*Math.log((1+o)/(1-o))/Math.PI;return e<0?0:e>1?1:e}function y(t,o){for(var e in o)t[e]=o[e];return t}function x(t){return t.x}function M(t){return t.y}return f.prototype.load=function(t){var o=this.options,e=o.log,n=o.minZoom,r=o.maxZoom,i=o.nodeSize;e&&console.time("total time");var s="prepare "+t.length+" points";e&&console.time(s),this.points=t;for(var p=[],h=0;h<t.length;h++)t[h].geometry&&p.push(l(t[h],h));this.trees[r+1]=new a(p,x,M,i,Float32Array),e&&console.timeEnd(s);for(var u=r;u>=n;u--){var f=+Date.now();p=this._cluster(p,u),this.trees[u]=new a(p,x,M,i,Float32Array),e&&console.log("z%d: %d clusters in %dms",u,p.length,+Date.now()-f)}return e&&console.timeEnd("total time"),this},f.prototype.getClusters=function(t,o){var e=((t[0]+180)%360+360)%360-180,n=Math.max(-90,Math.min(90,t[1])),r=180===t[2]?180:((t[2]+180)%360+360)%360-180,i=Math.max(-90,Math.min(90,t[3]));if(t[2]-t[0]>=360)e=-180,r=180;else if(e>r){var s=this.getClusters([e,n,180,i],o),a=this.getClusters([-180,n,r,i],o);return s.concat(a)}for(var p=this.trees[this._limitZoom(o)],h=[],u=0,f=p.range(v(e),g(i),v(r),g(n));u<f.length;u+=1){var d=f[u],l=p.points[d];h.push(l.numPoints?m(l):this.points[l.index])}return h},f.prototype.getChildren=function(t){var o=this._getOriginId(t),e=this._getOriginZoom(t),n="No cluster with the specified id.",r=this.trees[e];if(!r)throw new Error(n);var i=r.points[o];if(!i)throw new Error(n);for(var s=this.options.radius/(this.options.extent*Math.pow(2,e-1)),a=[],p=0,h=r.within(i.x,i.y,s);p<h.length;p+=1){var u=h[p],f=r.points[u];f.parentId===t&&a.push(f.numPoints?m(f):this.points[f.index])}if(0===a.length)throw new Error(n);return a},f.prototype.getLeaves=function(t,o,e){o=o||10,e=e||0;var n=[];return this._appendLeaves(n,t,o,e,0),n},f.prototype.getTile=function(t,o,e){var n=this.trees[this._limitZoom(t)],r=Math.pow(2,t),i=this.options,s=i.extent,a=i.radius/s,p=(e-a)/r,h=(e+1+a)/r,u={features:[]};return this._addTileFeatures(n.range((o-a)/r,p,(o+1+a)/r,h),n.points,o,e,r,u),0===o&&this._addTileFeatures(n.range(1-a/r,p,1,h),n.points,r,e,r,u),o===r-1&&this._addTileFeatures(n.range(0,p,a/r,h),n.points,-1,e,r,u),u.features.length?u:null},f.prototype.getClusterExpansionZoom=function(t){for(var o=this._getOriginZoom(t)-1;o<=this.options.maxZoom;){var e=this.getChildren(t);if(o++,1!==e.length)break;t=e[0].properties.cluster_id}return o},f.prototype._appendLeaves=function(t,o,e,n,r){for(var i=0,s=this.getChildren(o);i<s.length;i+=1){var a=s[i],p=a.properties;if(p&&p.cluster?r+p.point_count<=n?r+=p.point_count:r=this._appendLeaves(t,p.cluster_id,e,n,r):r<n?r++:t.push(a),t.length===e)break}return r},f.prototype._addTileFeatures=function(t,o,e,n,r,i){for(var s=0,a=t;s<a.length;s+=1){var p=o[a[s]],h=p.numPoints,u=void 0,f=void 0,d=void 0;if(h)u=c(p),f=p.x,d=p.y;else{var l=this.points[p.index];u=l.properties,f=v(l.geometry.coordinates[0]),d=g(l.geometry.coordinates[1])}var m={type:1,geometry:[[Math.round(this.options.extent*(f*r-e)),Math.round(this.options.extent*(d*r-n))]],tags:u},y=void 0;h?y=p.id:this.options.generateId?y=p.index:this.points[p.index].id&&(y=this.points[p.index].id),void 0!==y&&(m.id=y),i.features.push(m)}},f.prototype._limitZoom=function(t){return Math.max(this.options.minZoom,Math.min(Math.floor(+t),this.options.maxZoom+1))},f.prototype._cluster=function(t,o){for(var e=[],n=this.options,r=n.radius,i=n.extent,s=n.reduce,a=n.minPoints,p=r/(i*Math.pow(2,o)),h=0;h<t.length;h++){var u=t[h];if(!(u.zoom<=o)){u.zoom=o;for(var f=this.trees[o+1],l=f.within(u.x,u.y,p),m=u.numPoints||1,c=m,v=0,g=l;v<g.length;v+=1){var y=g[v],x=f.points[y];x.zoom>o&&(c+=x.numPoints||1)}if(c>m&&c>=a){for(var M=u.x*m,_=u.y*m,w=s&&m>1?this._map(u,!0):null,P=(h<<5)+(o+1)+this.points.length,z=0,Z=l;z<Z.length;z+=1){var I=Z[z],F=f.points[I];if(!(F.zoom<=o)){F.zoom=o;var b=F.numPoints||1;M+=F.x*b,_+=F.y*b,F.parentId=P,s&&(w||(w=this._map(u,!0)),s(w,this._map(F)))}}u.parentId=P,e.push(d(M/c,_/c,P,c,w))}else if(e.push(u),c>1)for(var A=0,C=l;A<C.length;A+=1){var T=C[A],E=f.points[T];E.zoom<=o||(E.zoom=o,e.push(E))}}}return e},f.prototype._getOriginId=function(t){return t-this.points.length>>5},f.prototype._getOriginZoom=function(t){return(t-this.points.length)%32},f.prototype._map=function(t,o){if(t.numPoints)return o?y({},t.properties):t.properties;var e=this.points[t.index].properties,n=this.options.map(e);return o&&n===e?y({},n):n},f}));
!function(t,e){"object"==typeof exports&&"undefined"!=typeof module?module.exports=e():"function"==typeof define&&define.amd?define(e):(t="undefined"!=typeof globalThis?globalThis:t||self).Supercluster=e()}(this,(function(){"use strict";const t=[Int8Array,Uint8Array,Uint8ClampedArray,Int16Array,Uint16Array,Int32Array,Uint32Array,Float32Array,Float64Array];class e{static from(s){if(!(s instanceof ArrayBuffer))throw new Error("Data must be an instance of ArrayBuffer.");const[n,i]=new Uint8Array(s,0,2);if(219!==n)throw new Error("Data does not appear to be in a KDBush format.");const o=i>>4;if(1!==o)throw new Error(`Got v${o} data when expected v1.`);const r=t[15&i];if(!r)throw new Error("Unrecognized array type.");const[h]=new Uint16Array(s,2,1),[a]=new Uint32Array(s,4,1);return new e(a,h,r,s)}constructor(e,s=64,n=Float64Array,i){if(isNaN(e)||e<=0)throw new Error(`Unpexpected numItems value: ${e}.`);this.numItems=+e,this.nodeSize=Math.min(Math.max(+s,2),65535),this.ArrayType=n,this.IndexArrayType=e<65536?Uint16Array:Uint32Array;const o=t.indexOf(this.ArrayType),r=2*e*this.ArrayType.BYTES_PER_ELEMENT,h=e*this.IndexArrayType.BYTES_PER_ELEMENT,a=(8-h%8)%8;if(o<0)throw new Error(`Unexpected typed array class: ${n}.`);i&&i instanceof ArrayBuffer?(this.data=i,this.ids=new this.IndexArrayType(this.data,8,e),this.coords=new this.ArrayType(this.data,8+h+a,2*e),this._pos=2*e,this._finished=!0):(this.data=new ArrayBuffer(8+r+h+a),this.ids=new this.IndexArrayType(this.data,8,e),this.coords=new this.ArrayType(this.data,8+h+a,2*e),this._pos=0,this._finished=!1,new Uint8Array(this.data,0,2).set([219,16+o]),new Uint16Array(this.data,2,1)[0]=s,new Uint32Array(this.data,4,1)[0]=e)}add(t,e){const s=this._pos>>1;return this.ids[s]=s,this.coords[this._pos++]=t,this.coords[this._pos++]=e,s}finish(){const t=this._pos>>1;if(t!==this.numItems)throw new Error(`Added ${t} items when expected ${this.numItems}.`);return s(this.ids,this.coords,this.nodeSize,0,this.numItems-1,0),this._finished=!0,this}range(t,e,s,n){if(!this._finished)throw new Error("Data not yet indexed - call index.finish().");const{ids:i,coords:o,nodeSize:r}=this,h=[0,i.length-1,0],a=[];for(;h.length;){const c=h.pop()||0,p=h.pop()||0,u=h.pop()||0;if(p-u<=r){for(let r=u;r<=p;r++){const h=o[2*r],c=o[2*r+1];h>=t&&h<=s&&c>=e&&c<=n&&a.push(i[r])}continue}const d=u+p>>1,f=o[2*d],l=o[2*d+1];f>=t&&f<=s&&l>=e&&l<=n&&a.push(i[d]),(0===c?t<=f:e<=l)&&(h.push(u),h.push(d-1),h.push(1-c)),(0===c?s>=f:n>=l)&&(h.push(d+1),h.push(p),h.push(1-c))}return a}within(t,e,s){if(!this._finished)throw new Error("Data not yet indexed - call index.finish().");const{ids:n,coords:i,nodeSize:o}=this,h=[0,n.length-1,0],a=[],c=s*s;for(;h.length;){const p=h.pop()||0,u=h.pop()||0,d=h.pop()||0;if(u-d<=o){for(let s=d;s<=u;s++)r(i[2*s],i[2*s+1],t,e)<=c&&a.push(n[s]);continue}const f=d+u>>1,l=i[2*f],m=i[2*f+1];r(l,m,t,e)<=c&&a.push(n[f]),(0===p?t-s<=l:e-s<=m)&&(h.push(d),h.push(f-1),h.push(1-p)),(0===p?t+s>=l:e+s>=m)&&(h.push(f+1),h.push(u),h.push(1-p))}return a}}function s(t,e,i,o,r,h){if(r-o<=i)return;const a=o+r>>1;n(t,e,a,o,r,h),s(t,e,i,o,a-1,1-h),s(t,e,i,a+1,r,1-h)}function n(t,e,s,o,r,h){for(;r>o;){if(r-o>600){const i=r-o+1,a=s-o+1,c=Math.log(i),p=.5*Math.exp(2*c/3),u=.5*Math.sqrt(c*p*(i-p)/i)*(a-i/2<0?-1:1);n(t,e,s,Math.max(o,Math.floor(s-a*p/i+u)),Math.min(r,Math.floor(s+(i-a)*p/i+u)),h)}const a=e[2*s+h];let c=o,p=r;for(i(t,e,o,s),e[2*r+h]>a&&i(t,e,o,r);c<p;){for(i(t,e,c,p),c++,p--;e[2*c+h]<a;)c++;for(;e[2*p+h]>a;)p--}e[2*o+h]===a?i(t,e,o,p):(p++,i(t,e,p,r)),p<=s&&(o=p+1),s<=p&&(r=p-1)}}function i(t,e,s,n){o(t,s,n),o(e,2*s,2*n),o(e,2*s+1,2*n+1)}function o(t,e,s){const n=t[e];t[e]=t[s],t[s]=n}function r(t,e,s,n){const i=t-s,o=e-n;return i*i+o*o}const h={minZoom:0,maxZoom:16,minPoints:2,radius:40,extent:512,nodeSize:64,log:!1,generateId:!1,reduce:null,map:t=>t},a=Math.fround||(c=new Float32Array(1),t=>(c[0]=+t,c[0]));var c;const p=3,u=5,d=6;function f(t,e,s){return{type:"Feature",id:t[e+p],properties:l(t,e,s),geometry:{type:"Point",coordinates:[(n=t[e],360*(n-.5)),y(t[e+1])]}};var n}function l(t,e,s){const n=t[e+u],i=n>=1e4?`${Math.round(n/1e3)}k`:n>=1e3?Math.round(n/100)/10+"k":n,o=t[e+d],r=-1===o?{}:Object.assign({},s[o]);return Object.assign(r,{cluster:!0,cluster_id:t[e+p],point_count:n,point_count_abbreviated:i})}function m(t){return t/360+.5}function g(t){const e=Math.sin(t*Math.PI/180),s=.5-.25*Math.log((1+e)/(1-e))/Math.PI;return s<0?0:s>1?1:s}function y(t){const e=(180-360*t)*Math.PI/180;return 360*Math.atan(Math.exp(e))/Math.PI-90}return class{constructor(t){this.options=Object.assign(Object.create(h),t),this.trees=new Array(this.options.maxZoom+1),this.stride=this.options.reduce?7:6,this.clusterProps=[]}load(t){const{log:e,minZoom:s,maxZoom:n}=this.options;e&&console.time("total time");const i=`prepare ${t.length} points`;e&&console.time(i),this.points=t;const o=[];for(let e=0;e<t.length;e++){const s=t[e];if(!s.geometry)continue;const[n,i]=s.geometry.coordinates,r=a(m(n)),h=a(g(i));o.push(r,h,1/0,e,-1,1),this.options.reduce&&o.push(0)}let r=this.trees[n+1]=this._createTree(o);e&&console.timeEnd(i);for(let t=n;t>=s;t--){const s=+Date.now();r=this.trees[t]=this._createTree(this._cluster(r,t)),e&&console.log("z%d: %d clusters in %dms",t,r.numItems,+Date.now()-s)}return e&&console.timeEnd("total time"),this}getClusters(t,e){let s=((t[0]+180)%360+360)%360-180;const n=Math.max(-90,Math.min(90,t[1]));let i=180===t[2]?180:((t[2]+180)%360+360)%360-180;const o=Math.max(-90,Math.min(90,t[3]));if(t[2]-t[0]>=360)s=-180,i=180;else if(s>i){const t=this.getClusters([s,n,180,o],e),r=this.getClusters([-180,n,i,o],e);return t.concat(r)}const r=this.trees[this._limitZoom(e)],h=r.range(m(s),g(o),m(i),g(n)),a=r.data,c=[];for(const t of h){const e=this.stride*t;c.push(a[e+u]>1?f(a,e,this.clusterProps):this.points[a[e+p]])}return c}getChildren(t){const e=this._getOriginId(t),s=this._getOriginZoom(t),n="No cluster with the specified id.",i=this.trees[s];if(!i)throw new Error(n);const o=i.data;if(e*this.stride>=o.length)throw new Error(n);const r=this.options.radius/(this.options.extent*Math.pow(2,s-1)),h=o[e*this.stride],a=o[e*this.stride+1],c=i.within(h,a,r),d=[];for(const e of c){const s=e*this.stride;o[s+4]===t&&d.push(o[s+u]>1?f(o,s,this.clusterProps):this.points[o[s+p]])}if(0===d.length)throw new Error(n);return d}getLeaves(t,e,s){e=e||10,s=s||0;const n=[];return this._appendLeaves(n,t,e,s,0),n}getTile(t,e,s){const n=this.trees[this._limitZoom(t)],i=Math.pow(2,t),{extent:o,radius:r}=this.options,h=r/o,a=(s-h)/i,c=(s+1+h)/i,p={features:[]};return this._addTileFeatures(n.range((e-h)/i,a,(e+1+h)/i,c),n.data,e,s,i,p),0===e&&this._addTileFeatures(n.range(1-h/i,a,1,c),n.data,i,s,i,p),e===i-1&&this._addTileFeatures(n.range(0,a,h/i,c),n.data,-1,s,i,p),p.features.length?p:null}getClusterExpansionZoom(t){let e=this._getOriginZoom(t)-1;for(;e<=this.options.maxZoom;){const s=this.getChildren(t);if(e++,1!==s.length)break;t=s[0].properties.cluster_id}return e}_appendLeaves(t,e,s,n,i){const o=this.getChildren(e);for(const e of o){const o=e.properties;if(o&&o.cluster?i+o.point_count<=n?i+=o.point_count:i=this._appendLeaves(t,o.cluster_id,s,n,i):i<n?i++:t.push(e),t.length===s)break}return i}_createTree(t){const s=new e(t.length/this.stride|0,this.options.nodeSize,Float32Array);for(let e=0;e<t.length;e+=this.stride)s.add(t[e],t[e+1]);return s.finish(),s.data=t,s}_addTileFeatures(t,e,s,n,i,o){for(const r of t){const t=r*this.stride,h=e[t+u]>1;let a,c,d;if(h)a=l(e,t,this.clusterProps),c=e[t],d=e[t+1];else{const s=this.points[e[t+p]];a=s.properties;const[n,i]=s.geometry.coordinates;c=m(n),d=g(i)}const f={type:1,geometry:[[Math.round(this.options.extent*(c*i-s)),Math.round(this.options.extent*(d*i-n))]],tags:a};let y;y=h||this.options.generateId?e[t+p]:this.points[e[t+p]].id,void 0!==y&&(f.id=y),o.features.push(f)}}_limitZoom(t){return Math.max(this.options.minZoom,Math.min(Math.floor(+t),this.options.maxZoom+1))}_cluster(t,e){const{radius:s,extent:n,reduce:i,minPoints:o}=this.options,r=s/(n*Math.pow(2,e)),h=t.data,a=[],c=this.stride;for(let s=0;s<h.length;s+=c){if(h[s+2]<=e)continue;h[s+2]=e;const n=h[s],p=h[s+1],d=t.within(h[s],h[s+1],r),f=h[s+u];let l=f;for(const t of d){const s=t*c;h[s+2]>e&&(l+=h[s+u])}if(l>f&&l>=o){let t,o=n*f,r=p*f,m=-1;const g=((s/c|0)<<5)+(e+1)+this.points.length;for(const n of d){const a=n*c;if(h[a+2]<=e)continue;h[a+2]=e;const p=h[a+u];o+=h[a]*p,r+=h[a+1]*p,h[a+4]=g,i&&(t||(t=this._map(h,s,!0),m=this.clusterProps.length,this.clusterProps.push(t)),i(t,this._map(h,a)))}h[s+4]=g,a.push(o/l,r/l,1/0,g,-1,l),i&&a.push(m)}else{for(let t=0;t<c;t++)a.push(h[s+t]);if(l>1)for(const t of d){const s=t*c;if(!(h[s+2]<=e)){h[s+2]=e;for(let t=0;t<c;t++)a.push(h[s+t])}}}}return a}_getOriginId(t){return t-this.points.length>>5}_getOriginZoom(t){return(t-this.points.length)%32}_map(t,e,s){if(t[e+u]>1){const n=this.clusterProps[t[e+d]];return s?Object.assign({},n):n}const n=this.points[t[e+p]].properties,i=this.options.map(n);return s&&i===n?Object.assign({},i):i}}}));

243

index.js

@@ -25,10 +25,18 @@

const OFFSET_ZOOM = 2;
const OFFSET_ID = 3;
const OFFSET_PARENT = 4;
const OFFSET_NUM = 5;
const OFFSET_PROP = 6;
export default class Supercluster {
constructor(options) {
this.options = extend(Object.create(defaultOptions), options);
this.options = Object.assign(Object.create(defaultOptions), options);
this.trees = new Array(this.options.maxZoom + 1);
this.stride = this.options.reduce ? 7 : 6;
this.clusterProps = [];
}
load(points) {
const {log, minZoom, maxZoom, nodeSize} = this.options;
const {log, minZoom, maxZoom} = this.options;

@@ -43,8 +51,22 @@ if (log) console.time('total time');

// generate a cluster object for each point and index input points into a KD-tree
let clusters = [];
const data = [];
for (let i = 0; i < points.length; i++) {
if (!points[i].geometry) continue;
clusters.push(createPointCluster(points[i], i));
const p = points[i];
if (!p.geometry) continue;
const [lng, lat] = p.geometry.coordinates;
const x = fround(lngX(lng));
const y = fround(latY(lat));
// store internal point/cluster data in flat numeric arrays for performance
data.push(
x, y, // projected point coordinates
Infinity, // the last zoom the point was processed at
i, // index of the source feature in the original input array
-1, // parent cluster id
1 // number of points in a cluster
);
if (this.options.reduce) data.push(0); // noop
}
this.trees[maxZoom + 1] = new KDBush(clusters, getX, getY, nodeSize, Float32Array);
let tree = this.trees[maxZoom + 1] = this._createTree(data);

@@ -59,6 +81,5 @@ if (log) console.timeEnd(timerId);

// create a new set of clusters for the zoom and index them with a KD-tree
clusters = this._cluster(clusters, z);
this.trees[z] = new KDBush(clusters, getX, getY, nodeSize, Float32Array);
tree = this.trees[z] = this._createTree(this._cluster(tree, z));
if (log) console.log('z%d: %d clusters in %dms', z, clusters.length, +Date.now() - now);
if (log) console.log('z%d: %d clusters in %dms', z, tree.numItems, +Date.now() - now);
}

@@ -88,6 +109,7 @@

const ids = tree.range(lngX(minLng), latY(maxLat), lngX(maxLng), latY(minLat));
const data = tree.data;
const clusters = [];
for (const id of ids) {
const c = tree.points[id];
clusters.push(c.numPoints ? getClusterJSON(c) : this.points[c.index]);
const k = this.stride * id;
clusters.push(data[k + OFFSET_NUM] > 1 ? getClusterJSON(data, k, this.clusterProps) : this.points[data[k + OFFSET_ID]]);
}

@@ -102,15 +124,17 @@ return clusters;

const index = this.trees[originZoom];
if (!index) throw new Error(errorMsg);
const tree = this.trees[originZoom];
if (!tree) throw new Error(errorMsg);
const origin = index.points[originId];
if (!origin) throw new Error(errorMsg);
const data = tree.data;
if (originId * this.stride >= data.length) throw new Error(errorMsg);
const r = this.options.radius / (this.options.extent * Math.pow(2, originZoom - 1));
const ids = index.within(origin.x, origin.y, r);
const x = data[originId * this.stride];
const y = data[originId * this.stride + 1];
const ids = tree.within(x, y, r);
const children = [];
for (const id of ids) {
const c = index.points[id];
if (c.parentId === clusterId) {
children.push(c.numPoints ? getClusterJSON(c) : this.points[c.index]);
const k = id * this.stride;
if (data[k + OFFSET_PARENT] === clusterId) {
children.push(data[k + OFFSET_NUM] > 1 ? getClusterJSON(data, k, this.clusterProps) : this.points[data[k + OFFSET_ID]]);
}

@@ -148,3 +172,3 @@ }

tree.range((x - p) / z2, top, (x + 1 + p) / z2, bottom),
tree.points, x, y, z2, tile);
tree.data, x, y, z2, tile);

@@ -154,3 +178,3 @@ if (x === 0) {

tree.range(1 - p / z2, top, 1, bottom),
tree.points, z2, y, z2, tile);
tree.data, z2, y, z2, tile);
}

@@ -160,3 +184,3 @@ if (x === z2 - 1) {

tree.range(0, top, p / z2, bottom),
tree.points, -1, y, z2, tile);
tree.data, -1, y, z2, tile);
}

@@ -206,17 +230,26 @@

_addTileFeatures(ids, points, x, y, z2, tile) {
_createTree(data) {
const tree = new KDBush(data.length / this.stride | 0, this.options.nodeSize, Float32Array);
for (let i = 0; i < data.length; i += this.stride) tree.add(data[i], data[i + 1]);
tree.finish();
tree.data = data;
return tree;
}
_addTileFeatures(ids, data, x, y, z2, tile) {
for (const i of ids) {
const c = points[i];
const isCluster = c.numPoints;
const k = i * this.stride;
const isCluster = data[k + OFFSET_NUM] > 1;
let tags, px, py;
if (isCluster) {
tags = getClusterProperties(c);
px = c.x;
py = c.y;
tags = getClusterProperties(data, k, this.clusterProps);
px = data[k];
py = data[k + 1];
} else {
const p = this.points[c.index];
const p = this.points[data[k + OFFSET_ID]];
tags = p.properties;
px = lngX(p.geometry.coordinates[0]);
py = latY(p.geometry.coordinates[1]);
const [lng, lat] = p.geometry.coordinates;
px = lngX(lng);
py = latY(lat);
}

@@ -235,10 +268,8 @@

let id;
if (isCluster) {
id = c.id;
} else if (this.options.generateId) {
// optionally generate id
id = c.index;
} else if (this.points[c.index].id) {
if (isCluster || this.options.generateId) {
// optionally generate id for points
id = data[k + OFFSET_ID];
} else {
// keep id if already assigned
id = this.points[c.index].id;
id = this.points[data[k + OFFSET_ID]].id;
}

@@ -256,19 +287,21 @@

_cluster(points, zoom) {
const clusters = [];
_cluster(tree, zoom) {
const {radius, extent, reduce, minPoints} = this.options;
const r = radius / (extent * Math.pow(2, zoom));
const data = tree.data;
const nextData = [];
const stride = this.stride;
// loop through each point
for (let i = 0; i < points.length; i++) {
const p = points[i];
for (let i = 0; i < data.length; i += stride) {
// if we've already visited the point at this zoom level, skip it
if (p.zoom <= zoom) continue;
p.zoom = zoom;
if (data[i + OFFSET_ZOOM] <= zoom) continue;
data[i + OFFSET_ZOOM] = zoom;
// find all nearby points
const tree = this.trees[zoom + 1];
const neighborIds = tree.within(p.x, p.y, r);
const x = data[i];
const y = data[i + 1];
const neighborIds = tree.within(data[i], data[i + 1], r);
const numPointsOrigin = p.numPoints || 1;
const numPointsOrigin = data[i + OFFSET_NUM];
let numPoints = numPointsOrigin;

@@ -278,5 +311,5 @@

for (const neighborId of neighborIds) {
const b = tree.points[neighborId];
const k = neighborId * stride;
// filter out neighbors that are already processed
if (b.zoom > zoom) numPoints += b.numPoints || 1;
if (data[k + OFFSET_ZOOM] > zoom) numPoints += data[k + OFFSET_NUM];
}

@@ -286,40 +319,46 @@

if (numPoints > numPointsOrigin && numPoints >= minPoints) {
let wx = p.x * numPointsOrigin;
let wy = p.y * numPointsOrigin;
let wx = x * numPointsOrigin;
let wy = y * numPointsOrigin;
let clusterProperties = reduce && numPointsOrigin > 1 ? this._map(p, true) : null;
let clusterProperties;
let clusterPropIndex = -1;
// encode both zoom and point index on which the cluster originated -- offset by total length of features
const id = (i << 5) + (zoom + 1) + this.points.length;
const id = ((i / stride | 0) << 5) + (zoom + 1) + this.points.length;
for (const neighborId of neighborIds) {
const b = tree.points[neighborId];
const k = neighborId * stride;
if (b.zoom <= zoom) continue;
b.zoom = zoom; // save the zoom (so it doesn't get processed twice)
if (data[k + OFFSET_ZOOM] <= zoom) continue;
data[k + OFFSET_ZOOM] = zoom; // save the zoom (so it doesn't get processed twice)
const numPoints2 = b.numPoints || 1;
wx += b.x * numPoints2; // accumulate coordinates for calculating weighted center
wy += b.y * numPoints2;
const numPoints2 = data[k + OFFSET_NUM];
wx += data[k] * numPoints2; // accumulate coordinates for calculating weighted center
wy += data[k + 1] * numPoints2;
b.parentId = id;
data[k + OFFSET_PARENT] = id;
if (reduce) {
if (!clusterProperties) clusterProperties = this._map(p, true);
reduce(clusterProperties, this._map(b));
if (!clusterProperties) {
clusterProperties = this._map(data, i, true);
clusterPropIndex = this.clusterProps.length;
this.clusterProps.push(clusterProperties);
}
reduce(clusterProperties, this._map(data, k));
}
}
p.parentId = id;
clusters.push(createCluster(wx / numPoints, wy / numPoints, id, numPoints, clusterProperties));
data[i + OFFSET_PARENT] = id;
nextData.push(wx / numPoints, wy / numPoints, Infinity, id, -1, numPoints);
if (reduce) nextData.push(clusterPropIndex);
} else { // left points as unclustered
clusters.push(p);
for (let j = 0; j < stride; j++) nextData.push(data[i + j]);
if (numPoints > 1) {
for (const neighborId of neighborIds) {
const b = tree.points[neighborId];
if (b.zoom <= zoom) continue;
b.zoom = zoom;
clusters.push(b);
const k = neighborId * stride;
if (data[k + OFFSET_ZOOM] <= zoom) continue;
data[k + OFFSET_ZOOM] = zoom;
for (let j = 0; j < stride; j++) nextData.push(data[k + j]);
}

@@ -330,3 +369,3 @@ }

return clusters;
return nextData;
}

@@ -344,43 +383,21 @@

_map(point, clone) {
if (point.numPoints) {
return clone ? extend({}, point.properties) : point.properties;
_map(data, i, clone) {
if (data[i + OFFSET_NUM] > 1) {
const props = this.clusterProps[data[i + OFFSET_PROP]];
return clone ? Object.assign({}, props) : props;
}
const original = this.points[point.index].properties;
const original = this.points[data[i + OFFSET_ID]].properties;
const result = this.options.map(original);
return clone && result === original ? extend({}, result) : result;
return clone && result === original ? Object.assign({}, result) : result;
}
}
function createCluster(x, y, id, numPoints, properties) {
function getClusterJSON(data, i, clusterProps) {
return {
x: fround(x), // weighted cluster center; round for consistency with Float32Array index
y: fround(y),
zoom: Infinity, // the last zoom the cluster was processed at
id, // encodes index of the first child of the cluster and its zoom level
parentId: -1, // parent cluster id
numPoints,
properties
};
}
function createPointCluster(p, id) {
const [x, y] = p.geometry.coordinates;
return {
x: fround(lngX(x)), // projected point coordinates
y: fround(latY(y)),
zoom: Infinity, // the last zoom the point was processed at
index: id, // index of the source feature in the original input array,
parentId: -1 // parent cluster id
};
}
function getClusterJSON(cluster) {
return {
type: 'Feature',
id: cluster.id,
properties: getClusterProperties(cluster),
id: data[i + OFFSET_ID],
properties: getClusterProperties(data, i, clusterProps),
geometry: {
type: 'Point',
coordinates: [xLng(cluster.x), yLat(cluster.y)]
coordinates: [xLng(data[i]), yLat(data[i + 1])]
}

@@ -390,10 +407,12 @@ };

function getClusterProperties(cluster) {
const count = cluster.numPoints;
function getClusterProperties(data, i, clusterProps) {
const count = data[i + OFFSET_NUM];
const abbrev =
count >= 10000 ? `${Math.round(count / 1000) }k` :
count >= 1000 ? `${Math.round(count / 100) / 10 }k` : count;
return extend(extend({}, cluster.properties), {
const propIndex = data[i + OFFSET_PROP];
const properties = propIndex === -1 ? {} : Object.assign({}, clusterProps[propIndex]);
return Object.assign(properties, {
cluster: true,
cluster_id: cluster.id,
cluster_id: data[i + OFFSET_ID],
point_count: count,

@@ -422,13 +441,1 @@ point_count_abbreviated: abbrev

}
function extend(dest, src) {
for (const id in src) dest[id] = src[id];
return dest;
}
function getX(p) {
return p.x;
}
function getY(p) {
return p.y;
}

29

package.json
{
"name": "supercluster",
"version": "7.1.5",
"version": "8.0.0",
"description": "A very fast geospatial point clustering library.",
"main": "dist/supercluster.js",
"type": "module",
"exports": "./index.js",
"module": "index.js",
"jsdelivr": "dist/supercluster.min.js",
"unpkg": "dist/supercluster.min.js",
"sideEffects": false,
"scripts": {
"pretest": "eslint index.js bench.js test/test.js demo/index.js demo/worker.js",
"test": "tape -r esm test/test.js",
"test": "node test/test.js",
"cov": "c8 npm run test",
"bench": "node --expose-gc -r esm bench.js",
"bench": "node --expose-gc bench.js",
"build": "mkdirp dist && rollup -c",

@@ -34,18 +37,18 @@ "prepublishOnly": "npm run test && npm run build"

"dependencies": {
"kdbush": "^3.0.0"
"kdbush": "^4.0.1"
},
"devDependencies": {
"@rollup/plugin-buble": "^0.21.3",
"@rollup/plugin-node-resolve": "^13.1.3",
"c8": "^7.11.0",
"eslint": "^8.12.0",
"@rollup/plugin-node-resolve": "^15.0.2",
"@rollup/plugin-terser": "^0.4.1",
"c8": "^7.13.0",
"eslint": "^8.39.0",
"eslint-config-mourner": "^3.0.0",
"esm": "^3.2.25",
"mkdirp": "^1.0.4",
"rollup": "^2.70.1",
"rollup-plugin-terser": "^7.0.2",
"tape": "^5.5.2"
"mkdirp": "^3.0.1",
"rollup": "^3.21.0"
},
"eslintConfig": {
"extends": "mourner",
"parserOptions": {
"ecmaVersion": 2020
},
"rules": {

@@ -52,0 +55,0 @@ "camelcase": 0

2

README.md

@@ -1,2 +0,2 @@

# supercluster [![Simply Awesome](https://img.shields.io/badge/simply-awesome-brightgreen.svg)](https://github.com/mourner/projects) [![Build Status](https://travis-ci.org/mapbox/supercluster.svg?branch=main)](https://travis-ci.org/mapbox/supercluster)
# supercluster [![Simply Awesome](https://img.shields.io/badge/simply-awesome-brightgreen.svg)](https://github.com/mourner/projects) [![Build Status](https://travis-ci.com/mapbox/supercluster.svg?branch=main)](https://travis-ci.com/mapbox/supercluster)

@@ -3,0 +3,0 @@ A very fast JavaScript library for geospatial point clustering for browsers and Node.