Source: util/clustering.js

/*
 * Using methods adapted from leaflet to cluster an array of positions
 * hierarchically given an array of length scales (zoom levels).
 */

var $ = require('jquery');

/**
 * This class manages a group of nearby points that are clustered as a
 * single object for display purposes.  The class constructor is private
 * and only meant to be created by the ClusterGroup object.
 *
 * This is a tree-like data structure.  Each node in the tree is a
 * cluster containing child clusters and unclustered points.
 *
 * @class
 * @alias geo.util.ClusterTree
 *
 * @param {geo.util.ClusterGroup} group The source cluster group
 * @param {number} zoom The zoom level of the current node
 * @param {object[]} children An array of ClusterTrees or point objects
 */
function ClusterTree(group, zoom, children) {
  this._group = group;
  this._zoom = zoom;
  this._points = [];     // Unclustered points
  this._clusters = [];   // Child clusters
  this._count = 0;       // Total number of points
  this._parent = null;
  this._coord = null;    // The cached coordinates
  var that = this;

  // add the children provided in the constructor call
  (children || []).forEach(function (c) {
    that._add(c);
  });
}

/**
 * Add a point or cluster as a child to the current cluster.
 * @param {object} pt A ClusterTree or point object
 * @private
 */
ClusterTree.prototype._add = function (pt) {
  var inc = 1;

  if (pt instanceof ClusterTree) {
    // add a child cluster
    this._clusters.push(pt);
    inc = pt._count;
  } else {
    this._points.push(pt);
  }
  pt._parent = this;

  // increment the counter
  this._increment(inc);
};

/**
 * Increment the child counter for this and the parent.
 * @param {number} inc The value to increment by
 * @private
 */
ClusterTree.prototype._increment = function (inc) {
  this._coord = null;
  this._count += inc;
  if (this._parent) {
    this._parent._increment(inc);
  }
};

/**
 * Return the total number of child points contained in the cluster.
 * @returns {number} Total points contained
 */
ClusterTree.prototype.count = function () {
  return this._count;
};

/**
 * Recursively call a function on all points contained in the cluster.
 * Calls the function with `this` as the current ClusterTree object, and
 * arguments to arguments the point object and the zoom level:
 * `func.call(this, point, zoom)`.
 *
 * @param {function} func The function to call.
 */
ClusterTree.prototype.each = function (func) {
  var i;
  for (i = 0; i < this._points.length; i += 1) {
    func.call(this, this._points[i], this._zoom);
  }
  for (i = 0; i < this._clusters.length; i += 1) {
    this._clusters[i].each.call(
      this._clusters[i],
      func
    );
  }
};

/**
 * Get the coordinates of the cluster (the mean position of all the points
 * contained).  This is lazily calculated and cached.
 *
 * @returns {geo.geoPosition} The 2-d coordinates of the center.
 */
ClusterTree.prototype.coords = function () {
  var i, center = {x: 0, y: 0};
  if (this._coord) {
    return this._coord;
  }
  // first add up the points at the node
  for (i = 0; i < this._points.length; i += 1) {
    center.x += this._points[i].x;
    center.y += this._points[i].y;
  }

  // add up the contribution from the clusters
  for (i = 0; i < this._clusters.length; i += 1) {
    center.x += this._clusters[i].coords().x * this._clusters[i].count();
    center.y += this._clusters[i].coords().y * this._clusters[i].count();
  }

  return {
    x: center.x / this.count(),
    y: center.y / this.count()
  };
};

/**
 * This class manages clustering of an array of positions hierarchically.
 * The algorithm and code was adapted from the Leaflet marker cluster
 * plugin by David Leaver: https://github.com/Leaflet/Leaflet.markercluster .
 *
 * @class
 * @alias geo.util.ClusterGroup
 * @param {object} opts An options object
 * @param {number} maxZoom The maximimum zoom level to calculate.
 * @param {number} radius Size of clustering at zoom 0 in point gcs.
 */
function C(opts) {

  var DistanceGrid = require('./distanceGrid');

  // store the options
  this._opts = $.extend({
    maxZoom: 18,
    radius: 5
  }, opts);

  // generate the initial datastructures
  this._clusters = {}; // clusters at each zoom level
  this._points = {};   // unclustered points at each zoom level

  var zoom, scl;
  for (zoom = this._opts.maxZoom; zoom >= 0; zoom -= 1) {
    scl = this._opts.radius * Math.pow(2, -zoom);
    this._clusters[zoom] = new DistanceGrid(scl);
    this._points[zoom] = new DistanceGrid(scl);
  }
  this._topClusterLevel = new ClusterTree(this, -1);
}

/**
 * Add a position to the cluster group.
 * @protected
 * @param {geo.geoPosition} point A point to add to the cluster.
 */
C.prototype.addPoint = function (point) {
  var zoom, closest, parent, newCluster, lastParent, z;
  /*
   * start at the maximum zoom level and search for nearby
   *
   * 1.  existing clusters
   * 2.  unclustered points
   *
   * otherwise add the point as a new unclustered point
   */
  for (zoom = this._opts.maxZoom; zoom >= 0; zoom -= 1) {

    // find near cluster
    closest = this._clusters[zoom].getNearObject(point);
    if (closest) {
      // add the point to the cluster and return
      closest._add(point);
      return;
    }

    // find near point
    closest = this._points[zoom].getNearObject(point);
    if (closest) {
      parent = closest._parent;
      if (parent) {
        // remove the point from the parent
        for (z = parent._points.length - 1; z >= 0; z -= 1) {
          if (parent._points[z] === closest) {
            parent._points.splice(z, 1);
            parent._increment(-1);
            break;
          }
        }
      }

      if (!parent) {
        $.noop();
      }
      // create a new cluster with these two points
      newCluster = new ClusterTree(this, zoom, [closest, point]);
      this._clusters[zoom].addObject(newCluster, newCluster.coords());

      // create intermediate parent clusters that don't exist
      lastParent = newCluster;
      for (z = zoom - 1; z > parent._zoom; z -= 1) {
        lastParent = new ClusterTree(this, z, [lastParent]);
        this._clusters[z].addObject(lastParent, lastParent.coords());
      }
      parent._add(lastParent);

      // remove closest from this zoom level and any above (replace with newCluster)
      for (z = zoom; z >= 0; z -= 1) {
        if (!this._points[z].removeObject(closest, closest)) {
          break;
        }
      }

      return;
    }

    // add an unclustered point
    this._points[zoom].addObject(point, point);
  }

  // otherwise add to the top
  this._topClusterLevel._add(point);
};

/**
 * Return the unclustered points contained at a given zoom level.
 * @param {number} zoom The zoom level.
 * @returns {object[]} The array of unclustered points.
 */
C.prototype.points = function (zoom) {
  zoom = Math.min(Math.max(Math.floor(zoom), 0), this._opts.maxZoom - 1);
  return this._points[Math.floor(zoom)].contents();
};

/**
 * Return the clusters contained at a given zoom level.
 * @param {number} zoom The zoom level.
 * @returns {geo.util.ClusterTree[]} The array of clusters.
 */
C.prototype.clusters = function (zoom) {
  zoom = Math.min(Math.max(Math.floor(zoom), 0), this._opts.maxZoom - 1);
  return this._clusters[Math.floor(zoom)].contents();
};

module.exports = C;