# Google Maps Supercluster Pattern

## Rendering 80,000+ Markers Without Freezing the Browser

This document explains how to efficiently render large datasets (50K-500K points) on Google Maps using the **Supercluster viewport rendering pattern**. This approach reduced our map load time from 10+ seconds with 2GB memory usage to under 1 second with ~25MB memory.

---

## Table of Contents

- [The Problem](#the-problem)
- [The Solution](#the-solution)
- [Architecture Overview](#architecture-overview)
- [Implementation Guide](#implementation-guide)
- [Real-World Example: APS Territory Map](#real-world-example-aps-territory-map)
- [Pros and Cons](#pros-and-cons)
- [Configuration Options](#configuration-options)
- [Common Pitfalls](#common-pitfalls)
- [Migration Checklist](#migration-checklist)

---

## The Problem

### Why Traditional Marker Rendering Fails at Scale

The naive approach to showing markers on Google Maps:

```javascript
// DON'T DO THIS with large datasets
addresses.forEach(addr => {
    const marker = new google.maps.Marker({
        position: { lat: addr.latitude, lng: addr.longitude },
        map: map
    });
    markers.push(marker);
});
```

**Why this fails at 80,000 points:**

| Issue | Impact |
|-------|--------|
| **DOM Object Overhead** | Each `google.maps.Marker` creates HTML elements, event listeners, and rendering layers (~20-25KB per marker) |
| **Synchronous Execution** | The `forEach` loop blocks the main thread entirely |
| **Memory Explosion** | 80,000 × 25KB = **2GB of RAM** before anything displays |
| **UI Freeze** | Browser is unresponsive for 5-15 seconds |

Even with `MarkerClusterer`, you still create all 80,000 Marker objects upfront—clustering just hides them visually but doesn't solve the memory/creation problem.

---

## The Solution

### Separate Data Storage from Rendering

The key insight: **Users never see 80,000 markers at once.**

At any zoom level, the viewport shows either:
- **Zoomed out**: Clusters (50-200 visible)
- **Zoomed in**: A small geographic area (100-1000 points)

So we:
1. Store raw coordinates as lightweight JavaScript objects
2. Build a spatial index for fast viewport queries
3. Only create Marker objects for what's currently visible
4. Re-render when the user pans or zooms

```javascript
// DO THIS instead
const rawData = addresses;  // Just store the data (~100 bytes each)
const index = new Supercluster({ radius: 60, maxZoom: 16 });
index.load(toGeoJSON(rawData));  // Build spatial index once

// On every pan/zoom, render only visible clusters
map.addListener('idle', () => {
    const clusters = index.getClusters(getViewportBbox(), map.getZoom());
    renderMarkers(clusters);  // Only ~100-200 markers
});
```

---

## Architecture Overview

### Three-Layer Data Architecture

```
┌─────────────────────────────────────────────────────────────┐
│                     RAW DATA LAYER                          │
│  [{lat: 35.1, lng: -89.9, id: 1}, ...]                     │
│  Memory: ~8MB for 80K points                                │
│  Purpose: Source of truth, never modified                   │
└─────────────────────────────────────────────────────────────┘
                              │
                              ▼
┌─────────────────────────────────────────────────────────────┐
│                   SPATIAL INDEX LAYER                       │
│  Supercluster R-tree index                                  │
│  Memory: ~15MB                                              │
│  Purpose: O(log n) viewport queries                         │
└─────────────────────────────────────────────────────────────┘
                              │
                              ▼
┌─────────────────────────────────────────────────────────────┐
│                  VISIBLE MARKERS LAYER                      │
│  google.maps.Marker objects (only ~100-200)                │
│  Memory: ~2-5MB                                             │
│  Purpose: What the user actually sees                       │
└─────────────────────────────────────────────────────────────┘
```

**Total memory: ~25MB** vs **~2GB** with traditional approach.

### Data Flow

```
Page Load
    │
    ▼
Fetch addresses from API ──────────────────► Store in rawData[]
    │
    ▼
Convert to GeoJSON features
    │
    ▼
Load into Supercluster index ──────────────► index.load(features)
    │
    ▼
Attach 'idle' listener to map
    │
    ▼
User pans/zooms ───► 'idle' fires ───► getClusters() ───► Render ~100 markers
```

---

## Implementation Guide

### Step 1: Add Supercluster Library

```html
<!-- Add to your HTML head or before your script -->
<script src="https://unpkg.com/supercluster@8.0.1/dist/supercluster.min.js"></script>
```

Or via npm:
```bash
npm install supercluster
```

### Step 2: Define Variables

```javascript
// Replace your old marker array with these three variables
let clusterIndex = null;        // Supercluster spatial index
let rawData = [];               // Raw coordinate data (lightweight)
let visibleMarkers = [];        // Currently displayed markers (small array)
```

### Step 3: Build the Cluster Index

```javascript
function buildClusterIndex(addresses) {
    // Convert to GeoJSON features (required by Supercluster)
    const features = addresses
        .filter(addr => addr.latitude && addr.longitude)
        .map(addr => ({
            type: 'Feature',
            properties: {
                id: addr.id,
                // Add any properties you need for info windows, etc.
                name: addr.name,
                customField: addr.customField
            },
            geometry: {
                type: 'Point',
                coordinates: [addr.longitude, addr.latitude]  // Note: [lng, lat] order!
            }
        }));

    // Create and load the index
    clusterIndex = new Supercluster({
        radius: 60,      // Cluster radius in pixels
        maxZoom: 16,     // Stop clustering at this zoom level
        minZoom: 0,      // Start clustering at this zoom level
        minPoints: 2     // Minimum points to form a cluster
    });

    clusterIndex.load(features);
    console.log(`Built index with ${features.length} points`);
}
```

### Step 4: Render Visible Clusters

```javascript
function renderVisibleClusters() {
    if (!clusterIndex) return;

    // Clear existing markers
    visibleMarkers.forEach(m => m.setMap(null));
    visibleMarkers = [];

    // Get current viewport bounds
    const bounds = map.getBounds();
    if (!bounds) return;

    const zoom = map.getZoom();

    // Supercluster uses [west, south, east, north] bbox format
    const bbox = [
        bounds.getSouthWest().lng(),
        bounds.getSouthWest().lat(),
        bounds.getNorthEast().lng(),
        bounds.getNorthEast().lat()
    ];

    // Get clusters for current viewport
    const clusters = clusterIndex.getClusters(bbox, zoom);

    // Create markers for each cluster/point
    clusters.forEach(cluster => {
        const [lng, lat] = cluster.geometry.coordinates;
        const isCluster = cluster.properties.cluster;

        let marker;
        if (isCluster) {
            // It's a cluster - show count
            const count = cluster.properties.point_count;
            marker = createClusterMarker(lat, lng, count, cluster.properties.cluster_id);
        } else {
            // It's an individual point
            marker = createPointMarker(lat, lng, cluster.properties);
        }

        visibleMarkers.push(marker);
    });

    console.log(`Rendered ${visibleMarkers.length} markers at zoom ${zoom}`);
}

function createClusterMarker(lat, lng, count, clusterId) {
    // Custom SVG for cluster appearance
    const svg = `<svg fill="#4285F4" xmlns="http://www.w3.org/2000/svg" viewBox="0 0 240 240">
        <circle cx="120" cy="120" opacity="0.9" r="70" />
        <circle cx="120" cy="120" opacity="0.3" r="90" />
        <circle cx="120" cy="120" opacity="0.2" r="110" />
    </svg>`;

    const marker = new google.maps.Marker({
        position: { lat, lng },
        map: map,
        icon: {
            url: `data:image/svg+xml;base64,${btoa(svg)}`,
            scaledSize: new google.maps.Size(45, 45),
            anchor: new google.maps.Point(22, 22)
        },
        label: {
            text: count >= 1000 ? Math.round(count/1000) + 'k' : String(count),
            color: 'white',
            fontSize: '11px',
            fontWeight: 'bold'
        },
        zIndex: 1000 + count
    });

    // Click to zoom into cluster
    marker.addListener('click', () => {
        const expansionZoom = Math.min(
            clusterIndex.getClusterExpansionZoom(clusterId),
            18
        );
        map.setZoom(expansionZoom);
        map.panTo({ lat, lng });
    });

    return marker;
}

function createPointMarker(lat, lng, properties) {
    const marker = new google.maps.Marker({
        position: { lat, lng },
        map: map,
        icon: {
            path: google.maps.SymbolPath.CIRCLE,
            scale: 6,
            fillColor: '#4285F4',
            fillOpacity: 0.9,
            strokeColor: '#FFFFFF',
            strokeWeight: 1
        },
        zIndex: 100
    });

    // Add info window with properties
    const infoWindow = new google.maps.InfoWindow({
        content: `<div><strong>${properties.name || 'Point'}</strong></div>`
    });
    marker.addListener('click', () => infoWindow.open(map, marker));

    return marker;
}
```

### Step 5: Wire Up the Data Loading

```javascript
async function loadData() {
    try {
        const response = await fetch('/api/your-data-endpoint');
        const data = await response.json();

        // Store raw data
        rawData = data.items;

        // Build spatial index
        buildClusterIndex(rawData);

        // Set up viewport-based rendering
        google.maps.event.addListener(map, 'idle', renderVisibleClusters);

        // Initial render
        renderVisibleClusters();

    } catch (error) {
        console.error('Failed to load data:', error);
    }
}

// Call after map is initialized
google.maps.event.addListenerOnce(map, 'idle', loadData);
```

### Step 6: Cleanup Function

```javascript
function clearMarkers() {
    visibleMarkers.forEach(marker => marker.setMap(null));
    visibleMarkers = [];
    clusterIndex = null;
    rawData = [];
    google.maps.event.clearListeners(map, 'idle');
}
```

---

## Real-World Example: APS Territory Map

### Before (MarkerClusterer)

```javascript
// Old implementation - created 80,000 Marker objects
async function loadAllAddresses() {
    const response = await fetch('/api/addresses/in-bounds?all=true');
    const data = await response.json();

    // This loop blocked the UI for 5-10 seconds
    data.addresses.forEach(addr => {
        const marker = new google.maps.Marker({
            position: { lat: addr.latitude, lng: addr.longitude },
            map: null,
            icon: cachedIcon
        });
        addressMarkers.push(marker);  // 80,000 DOM objects!
    });

    // MarkerClusterer still had to process all 80K markers
    addressClusterer = new markerClusterer.MarkerClusterer({
        map: map,
        markers: addressMarkers
    });
}
```

**Result:** 2GB memory, 10-second freeze, unresponsive UI

### After (Supercluster)

```javascript
// New implementation - only creates ~100-200 markers at a time
async function loadAllAddresses() {
    const response = await fetch('/api/addresses/in-bounds?all=true');
    const data = await response.json();

    // Store lightweight data (~8MB)
    addressRawData = data.addresses;

    // Build spatial index (~50ms)
    buildClusterIndex(addressRawData);

    // Render only visible clusters
    google.maps.event.addListener(map, 'idle', renderVisibleClusters);
    renderVisibleClusters();
}
```

**Result:** 25MB memory, <1 second load, fully responsive UI

### Performance Comparison

| Metric | Before (MarkerClusterer) | After (Supercluster) |
|--------|--------------------------|----------------------|
| Memory usage | ~2GB | ~25MB |
| Initial load freeze | 5-10 seconds | 0 seconds |
| Time to interactive | 10-15 seconds | <1 second |
| Pan/zoom responsiveness | Laggy | Instant |
| Markers created | 80,000 | ~100-200 |

---

## Pros and Cons

### Advantages

| Pro | Explanation |
|-----|-------------|
| **Massive memory reduction** | 100x less memory (2GB → 25MB) |
| **No UI freezing** | Main thread never blocked |
| **Instant interactivity** | Page is responsive immediately |
| **Smooth pan/zoom** | Only re-renders ~100 markers per viewport change |
| **Scales to millions** | Same performance with 500K points |
| **Click-to-zoom clusters** | Built-in UX pattern users understand |
| **Works offline** | Index is client-side, no server round-trips on pan/zoom |

### Disadvantages

| Con | Mitigation |
|-----|------------|
| **Extra library dependency** | Supercluster is small (~15KB gzipped) and well-maintained |
| **GeoJSON conversion required** | One-time cost at load, very fast |
| **Markers recreated on pan/zoom** | Only ~100-200 markers, takes ~10ms |
| **No marker object persistence** | Store state in rawData properties, not on markers |
| **Learning curve** | This guide provides copy-paste implementation |
| **Cluster click requires special handling** | Use `getClusterExpansionZoom()` API |

### When NOT to Use This Pattern

- **< 1,000 points**: Traditional markers work fine
- **Static, non-moving map**: Pre-render once, no need for viewport updates
- **Markers with complex persistent state**: May need hybrid approach
- **Real-time updates to individual markers**: Consider data binding libraries

---

## Configuration Options

### Supercluster Options

```javascript
const index = new Supercluster({
    // Cluster radius in pixels (default: 40)
    // Higher = fewer, larger clusters
    radius: 60,

    // Zoom range for clustering
    minZoom: 0,    // Start clustering at world view
    maxZoom: 16,   // Stop clustering at street level (show individual points)

    // Minimum points to form a cluster (default: 2)
    minPoints: 2,

    // Extent of the tile (default: 512)
    extent: 512,

    // Size of the tile index (default: 64)
    nodeSize: 64,

    // Custom reduce function for aggregating properties
    reduce: (accumulated, props) => {
        accumulated.sum = (accumulated.sum || 0) + props.value;
    },

    // Custom map function for point properties
    map: (props) => ({ value: props.value })
});
```

### Tuning for Your Dataset

| Dataset Size | Recommended `radius` | Recommended `maxZoom` |
|--------------|---------------------|----------------------|
| 1K - 10K | 40 | 14 |
| 10K - 50K | 50 | 15 |
| 50K - 200K | 60 | 16 |
| 200K - 1M | 80 | 17 |

---

## Common Pitfalls

### 1. Coordinate Order

```javascript
// WRONG - GeoJSON uses [longitude, latitude]
coordinates: [addr.latitude, addr.longitude]

// CORRECT
coordinates: [addr.longitude, addr.latitude]
```

### 2. Forgetting to Clear Old Markers

```javascript
function renderVisibleClusters() {
    // MUST clear old markers first, or they accumulate!
    visibleMarkers.forEach(m => m.setMap(null));
    visibleMarkers = [];

    // ... rest of rendering
}
```

### 3. Not Removing the Idle Listener

```javascript
function clearMarkers() {
    visibleMarkers.forEach(m => m.setMap(null));
    visibleMarkers = [];

    // IMPORTANT: Remove the listener or it keeps firing
    google.maps.event.clearListeners(map, 'idle');
}
```

### 4. Calling getClusters Before Index is Ready

```javascript
// WRONG - index might be null
map.addListener('idle', renderVisibleClusters);

// CORRECT - check for index
function renderVisibleClusters() {
    if (!clusterIndex) return;  // Guard clause
    // ...
}
```

### 5. Using Wrong Bbox Format

```javascript
// Supercluster bbox format: [west, south, east, north]
// NOT [south, west, north, east]

const bbox = [
    bounds.getSouthWest().lng(),  // west
    bounds.getSouthWest().lat(),  // south
    bounds.getNorthEast().lng(),  // east
    bounds.getNorthEast().lat()   // north
];
```

---

## Migration Checklist

Use this checklist when migrating from MarkerClusterer to Supercluster:

- [ ] Add Supercluster library to HTML or package.json
- [ ] Replace marker array with three variables: `clusterIndex`, `rawData`, `visibleMarkers`
- [ ] Create `buildClusterIndex()` function with GeoJSON conversion
- [ ] Create `renderVisibleClusters()` function with bbox query
- [ ] Create cluster marker renderer with click-to-zoom
- [ ] Create individual point marker renderer
- [ ] Update data loading to build index instead of creating markers
- [ ] Add `map.addListener('idle', renderVisibleClusters)`
- [ ] Update clear/cleanup function to remove idle listener
- [ ] Test at various zoom levels to verify all points appear
- [ ] Remove old MarkerClusterer library import
- [ ] Remove old marker array and clusterer variables

---

## References

- [Supercluster GitHub](https://github.com/mapbox/supercluster) - Official repository
- [Supercluster npm](https://www.npmjs.com/package/supercluster) - Package page
- [GeoJSON Specification](https://geojson.org/) - GeoJSON format reference
- [Google Maps JavaScript API](https://developers.google.com/maps/documentation/javascript) - Marker and event documentation

---

## Version History

| Version | Date | Changes |
|---------|------|---------|
| 1.0 | 2025-01-15 | Initial documentation based on APS implementation |