npm package discovery and stats viewer.

Discover Tips

  • General search

    [free text search, go nuts!]

  • Package details

    pkg:[package-name]

  • User packages

    @[username]

Sponsor

Optimize Toolset

I’ve always been into building performant and accessible sites, but lately I’ve been taking it extremely seriously. So much so that I’ve been building a tool to help me optimize and monitor the sites that I build to make sure that I’m making an attempt to offer the best experience to those who visit them. If you’re into performant, accessible and SEO friendly sites, you might like it too! You can check it out at Optimize Toolset.

About

Hi, 👋, I’m Ryan Hefner  and I built this site for me, and you! The goal of this site was to provide an easy way for me to check the stats on my npm packages, both for prioritizing issues and updates, and to give me a little kick in the pants to keep up on stuff.

As I was building it, I realized that I was actually using the tool to build the tool, and figured I might as well put this out there and hopefully others will find it to be a fast and useful way to search and browse npm packages as I have.

If you’re interested in other things I’m working on, follow me on Twitter or check out the open source projects I’ve been publishing on GitHub.

I am also working on a Twitter bot for this site to tweet the most popular, newest, random packages from npm. Please follow that account now and it will start sending out packages soon–ish.

Open Software & Tools

This site wouldn’t be possible without the immense generosity and tireless efforts from the people who make contributions to the world and share their work via open source initiatives. Thank you 🙏

© 2024 – Pkg Stats / Ryan Hefner

wasm-marker-clusterer

v1.1.1

Published

A WebAssembly alternative to the popular MarkerClustererPlus library for Google Maps

Downloads

8

Readme

wasm-marker-clusterer

Build Status

wasm-marker-clusterer is a faster (and more bare-bones) alternative to the popular MarkerClustererPlus (MCP) library for Google Maps. It is compiled from Rust into WebAssembly. This library is used to cluster geographic markers (lat/lng pairs) into labelled clusters of markers, to simplify a map view.

10-50% faster than the Javascript implementation.

See the demo here to create a graph of your own speed-up results.

Graph showing 8x speedup for wasm-marker-clusterer compared to javascript MarkerClustererPlus Why "(per cluster)" on the axises?

Comparison

Unlike MCP, this library can be used independent from Google Maps, as it only handles data, not the UI.

Here's a quick summary of the differences: | Does it...?| MCP | Wasm | |------- |---- |--- | | Cluster map points? | Yes | Yes | | Work with any map system? | No, only Google Maps | Yes, any map system | | Use a restrictive marker renderer? | Yup, you have to overwrite the library's prototypes if really want to customize your markers. | No, is not tied to any renderer. You can define interactive and beautiful markers| | Run in the main thread, blocking rendering? | Yup, and it'll slow down your whole app if you have lots of markers. | No, runs in a Web Worker so your app remains responsive while it calculates.

Installation

This package has a peer-dependency on the Webpack plugin GoogleChromeLabs/worker-plugin which is used to load the WASM module in a web worker.

npm install wasm-marker-clusterer
npm install -D worker-plugin

Then add worker-plugin to your webpack.config.js:

+ const WorkerPlugin = require('worker-plugin');

module.exports = {
  <...>
  plugins: [
+    new WorkerPlugin()
  ]
  <...>
}

If you're not using Webpack, it should be possible to still use this library without worker-plugin, but you'll have to manually ensure the worker can be found and loaded. If you figure this out, let me know!

Usage

import { WasmMarkerClusterer } from "wasm-marker-clusterer";

let clusterer = new WasmMarkerClusterer();

// See `Configuration` section below for all configurable parameters
await clusterer.configure({ gridSize: 60 });

await clusterer.addMarkers([
  { lat: 43.6358644, lng: -79.4673894 },
  { lat: 43.893691,  lng: -78.9528484 },
]);

let zoom = 8;
// Takes a geographic bounds object, and the zoom level, and returns clusters that are within it.
let clusters = await clusterer.clusterMarkersInBounds({
  north: 43.9,
  south: 43.5,
  east: -78.9,
  west: -79.5
}, zoom);

You can also check out the source code of the demo page to see a fully functioning code example.

Configuration

All configurable parameters defined in the interface file.

API

All the custom Typescript types in this API are defined in the interface file.

export declare class WasmMarkerClusterer {
  /**
   * Merges any passed config parameters into existing config.
   * Clears cached clusters if `averageCenter` or `gridSize` is modified.
   */
  configure: (config: IConfig) => Promise<void>;

  /**
   * Calculates clusters for the markers within the given bounds.
   * @returns Newly calculated clusters merged with any previously calculated clusters
   */
  clusterMarkersInBounds: (bounds: IBounds, zoom: number) => Promise<ICluster[]>;

  /**
   * Add an array of lat/lng markers so that they can be clustered.
   */
  addMarkers: (markers: IMarker[]) => Promise<void>;

  /**
   * Clears all added markers and calculated clusters.
   */
  clear: () => Promise<void>;

  /**
   * Clears only calculated clusters.
   */
  clearClusters: () => Promise<void>;
}

Implementation

This library is mostly a Rust port of the original MarkerClusterPlus library, with some tweaks to remove dependencies on the Google Maps Javascript API, and without any of the GUI code.

The library has a few levels of abstraction to make it easy to work with, without having any knowledge of Rust or WebAssembly.

  • At the core is Rust code, compiled to Wasm.
  • The resulting Wasm module (and wasm-bindgen glue code) is loaded inside a Web Worker using worker-plugin
  • A Typescript wrapper class loads the Web Worker, and uses comlink to simplify the calls to the Web Worker into Promises. It also manages some state to minimize how much data needs to be serialized between the Wasm/JS boundary.

Here's a high-level summary of how the clustering algorithm works in this library and MCP:

for all the markers:
  if (the marker is not already in a cluster) AND (the marker is within the requested map bounds):
    // Add to the closest cluster:
    for all existing clusters:
      calculate the distance to this marker and choose the closest cluster
    if the closest cluster is less than GRID_SIZE pixels away:
      add the marker to this cluster
    else:
      create a new cluster with this marker as the center

Why "(per cluster)" on the graph axes?

If you look at the axis labels on the graph at the top of this readme, you'll notice they are:

  • Cluster Time (per cluster)
  • New Markers Clustered (per cluster)

The clustering algorithm has a complexity of O(n*c) where n is number of markers, and c is the number of clusters.

Because of this, it will take longer to cluster the same number of markers into 10 clusters than it will for 1 cluster.

Also note that the majority of the CPU time is spent finding a cluster for a marker that has not already been clustered. That's why the x-axis is labeled New Markers Clustered.

Therefore in order to accurately fit a straight line to this data, the cluster time (how long it took to cluster the markers) and the number of new markers clustered must both be divided by c the number of clusters.