Grouped clustering

README.md

Point clustering with the constraint that points should only be clustered within borders.

1. Use supercluster to cluster the points within each boundary.
2. Use a force simulation to avoid collisions between points along the borders.

four-corners.geo.json

{
  "type": "FeatureCollection",
  "features": [
    {
      "type": "Feature",
      "properties": {
        "state": "AZ"
      },
      "geometry": {
        "type": "MultiPolygon",
        "coordinates": [
          [
            [
              [-109.04510906774894, 36.999071622023536],
              [-109.04582692010679, 36.00233852188019],
              [-109.04582692010679, 34.959732924026],
              [-109.04618584628572, 34.57927051034227],
              [-109.04690369864358, 33.778220676194955],
              [-109.0472626248225, 33.208950499684974],
              [-109.0472626248225, 32.7775663906501],
              [-109.04762155100143, 32.42637858030643],
              [-109.0501340342539, 31.332099278941904],
              [-110.45999606507594, 31.332582712758526],
              [-111.07483660957648, 31.332099278941904],
              [-111.36664359304346, 31.426046583972656],
              [-113.33355905355893, 32.03882580397887],
              [-114.8137706154505, 32.4940593146339],
              [-114.80946350130337, 32.61679778918809],
              [-114.7193730303929, 32.7186948947589],
              [-114.52698859848847, 32.757101025746316],
              [-114.46274081246068, 32.90793237653326],
              [-114.51514403458391, 33.026534806211885],
              [-114.6727126271325, 33.04050067202549],
              [-114.70645168795156, 33.08814576039729],
              [-114.67701974127961, 33.27018544979079],
              [-114.73121759429746, 33.30241437089911],
              [-114.72368014454001, 33.40651378607899],
              [-114.6260522238721, 33.43680897192081],
              [-114.52447611523598, 33.55224222435711],
              [-114.49683879945867, 33.696788935527934],
              [-114.53488497442484, 33.92572170513404],
              [-114.43618027522015, 34.027779955310386],
              [-114.43259101343088, 34.087886893177405],
              [-114.25528148104135, 34.173400963851485],
              [-114.13827154671142, 34.303229801049504],
              [-114.34070591162579, 34.45148283814778],
              [-114.43618027522015, 34.5967815574778],
              [-114.47350859782847, 34.71393368570654],
              [-114.63287182127169, 34.86943823005419],
              [-114.63394859980848, 35.00109337278168],
              [-114.64686994224982, 35.1018624661137],
              [-114.56934188760177, 35.162291693191804],
              [-114.59554349866337, 35.32655176110721],
              [-114.67701974127961, 35.51294235485034],
              [-114.704298130878, 35.851346026487704],
              [-114.75598350064337, 36.08570399781371],
              [-114.63035933801922, 36.1422120394903],
              [-114.37013785829774, 36.142641758438415],
              [-114.23338698412685, 36.012812921240396],
              [-114.15334644622632, 36.023179890863574],
              [-114.04387396165383, 36.19334859431551],
              [-114.05033463287451, 36.84313735872777],
              [-114.05069355905343, 37.00041449373638],
              [-112.89925837705825, 37.000360778867865],
              [-112.54033219813208, 37.00068306807895],
              [-111.41258614394602, 37.00148879110665],
              [-110.75072627000614, 37.0032076668991],
              [-110.00057055605043, 36.99794360978474],
              [-109.04510906774894, 36.999071622023536]
            ]
          ]
        ]
      }
    },
    {
      "type": "Feature",
      "properties": {
        "state": "CO"
      },
      "geometry": {
        "type": "MultiPolygon",
        "coordinates": [
          [
            [
              [-104.94330069498056, 40.99819729774955],
              [-104.05352269742257, 41.00136647499187],
              [-103.57435624855611, 41.00174247907147],
              [-103.38233074283062, 41.00227962775661],
              [-102.65335167343154, 41.00233334262512],
              [-102.62104831732819, 41.00244077236215],
              [-102.05250924990912, 41.00233334262512],
              [-102.05143247137234, 40.74960488626736],
              [-102.05143247137234, 40.697555178677426],
              [-102.05143247137234, 40.43999238415343],
              [-102.05143247137234, 40.34921425636499],
              [-102.05179139755127, 40.00307564366162],
              [-102.04963784047771, 39.574054988841354],
              [-102.04963784047771, 39.56820006817334],
              [-102.04712535722523, 39.13316334807952],
              [-102.04640750486737, 39.04700469898328],
              [-102.04533072633059, 38.69753576443205],
              [-102.04497180015167, 38.61513715613178],
              [-102.04461287397274, 38.26872996908584],
              [-102.04497180015167, 38.2623916146012],
              [-102.04210039072026, 37.738510501985445],
              [-102.04174146454133, 37.64429462261212],
              [-102.04174146454133, 37.38920271203976],
              [-102.04210039072026, 36.993538990566606],
              [-103.00222791934779, 37.000092204525295],
              [-103.08621664521651, 37.00025334913084],
              [-104.00793907269895, 36.99622473399229],
              [-105.155067140547, 36.99525786635905],
              [-105.2207506312905, 36.99515043662202],
              [-105.71822231528219, 36.9958487299127],
              [-106.00679896313883, 36.99531158122756],
              [-106.47627440517428, 36.99375385004066],
              [-107.42096810810799, 36.99998477478827],
              [-107.4816266323465, 36.99998477478827],
              [-108.37930100584087, 36.99950134097165],
              [-109.04510906774894, 36.999071622023536],
              [-109.0433144368543, 37.48465403338891],
              [-109.04151980595968, 37.88117719275828],
              [-109.04223765831753, 38.153028142306965],
              [-109.0598250410849, 38.499972478038046],
              [-109.05085188661175, 39.36666188150931],
              [-109.05121081279069, 39.497672445814636],
              [-109.05121081279069, 39.66048221228017],
              [-109.05085188661175, 40.22266202614632],
              [-109.04833940335928, 40.65361641623308],
              [-109.0501340342539, 41.00066818170119],
              [-107.91843979209966, 41.00201105341404],
              [-107.31795629475617, 41.00292420617877],
              [-106.85888971190958, 41.0026556318362],
              [-106.32014151734138, 40.99911045051428],
              [-106.19056916674904, 40.99792872340698],
              [-105.27710204138191, 40.99825101261806],
              [-104.94330069498056, 40.99819729774955]
            ]
          ]
        ]
      }
    },
    {
      "type": "Feature",
      "properties": {
        "state": "NM"
      },
      "geometry": {
        "type": "MultiPolygon",
        "coordinates": [
          [
            [
              [-105.2207506312905, 36.99515043662202],
              [-105.155067140547, 36.99525786635905],
              [-104.00793907269895, 36.99622473399229],
              [-103.08621664521651, 37.00025334913084],
              [-103.00222791934779, 37.000092204525295],
              [-103.00258684552671, 36.50038278274078],
              [-103.0420687252086, 36.50043649760929],
              [-103.04099194667181, 36.05524766736635],
              [-103.04135087285074, 35.73935052563629],
              [-103.04170979902966, 35.622359542013086],
              [-103.04242765138753, 35.18313306217519],
              [-103.04278657756645, 34.95409286283205],
              [-103.04278657756645, 34.74734433392217],
              [-103.04386335610323, 34.312737332776464],
              [-103.04386335610323, 34.30258522262734],
              [-103.04745261789249, 33.82511375640756],
              [-103.05247758439745, 33.570612709388854],
              [-103.05678469854456, 33.388411875389814],
              [-103.06468107448094, 32.95906893135846],
              [-103.06468107448094, 32.52220590573517],
              [-103.06432214830201, 32.08706175590432],
              [-103.06432214830201, 32.00052710272848],
              [-103.32633825891813, 32.00036595812294],
              [-103.72295168663156, 32.0002048135174],
              [-103.98030175692162, 32.00009738378037],
              [-104.02444967692955, 32.00004366891186],
              [-104.8478263313862, 32.00052710272848],
              [-104.91817586245573, 32.00047338785997],
              [-105.99782580866568, 32.00229969338944],
              [-106.37721077979064, 32.00127911088767],
              [-106.61840917202905, 32.000419672991455],
              [-106.63599655479642, 31.866186216575294],
              [-106.52795977493965, 31.783895038012048],
              [-107.29677965019953, 31.783626463669478],
              [-108.20845214467201, 31.783680178537992],
              [-108.20845214467201, 31.333388435786233],
              [-109.0501340342539, 31.332099278941904],
              [-109.04762155100143, 32.42637858030643],
              [-109.0472626248225, 32.7775663906501],
              [-109.0472626248225, 33.208950499684974],
              [-109.04690369864358, 33.778220676194955],
              [-109.04618584628572, 34.57927051034227],
              [-109.04582692010679, 34.959732924026],
              [-109.04582692010679, 36.00233852188019],
              [-109.04510906774894, 36.999071622023536],
              [-108.37930100584087, 36.99950134097165],
              [-107.4816266323465, 36.99998477478827],
              [-107.42096810810799, 36.99998477478827],
              [-106.47627440517428, 36.99375385004066],
              [-106.00679896313883, 36.99531158122756],
              [-105.71822231528219, 36.9958487299127],
              [-105.2207506312905, 36.99515043662202]
            ]
          ]
        ]
      }
    },
    {
      "type": "Feature",
      "properties": {
        "state": "UT"
      },
      "geometry": {
        "type": "MultiPolygon",
        "coordinates": [
          [
            [
              [-111.04684036762023, 42.0015373267201],
              [-111.04576358908346, 41.57982189401771],
              [-111.04648144144132, 41.25173147713501],
              [-111.04684036762023, 40.99792872340698],
              [-110.04830773784761, 40.99766014906441],
              [-110.00057055605043, 40.99766014906441],
              [-109.0501340342539, 41.00066818170119],
              [-109.04833940335928, 40.65361641623308],
              [-109.05085188661175, 40.22266202614632],
              [-109.05121081279069, 39.66048221228017],
              [-109.05121081279069, 39.497672445814636],
              [-109.05085188661175, 39.36666188150931],
              [-109.0598250410849, 38.499972478038046],
              [-109.04223765831753, 38.153028142306965],
              [-109.04151980595968, 37.88117719275828],
              [-109.0433144368543, 37.48465403338891],
              [-109.04510906774894, 36.999071622023536],
              [-110.00057055605043, 36.99794360978474],
              [-110.75072627000614, 37.0032076668991],
              [-111.41258614394602, 37.00148879110665],
              [-112.54033219813208, 37.00068306807895],
              [-112.89925837705825, 37.000360778867865],
              [-114.05069355905343, 37.00041449373638],
              [-114.05248818994806, 37.60481419425443],
              [-114.04997570669558, 38.148569808220316],
              [-114.04997570669558, 38.57291726947987],
              [-114.04997570669558, 38.67733897387083],
              [-114.04782214962202, 39.542739220497765],
              [-114.04710429726417, 39.906012876257066],
              [-114.04674537108525, 40.11695116491102],
              [-114.04207933075921, 40.999969888410504],
              [-114.04172040458027, 41.99364124104856],
              [-113.0015523380522, 41.998207004872235],
              [-112.16597219351206, 41.997562426450074],
              [-112.1103386357785, 41.99750871158156],
              [-111.50806050754038, 41.99944244684805],
              [-111.04684036762023, 42.0015373267201]
            ]
          ]
        ]
      }
    }
  ]
}

index.html

<!DOCTYPE html>
<meta charset="utf-8">
<style>
    path {
        fill: #f4f4f4;
        stroke: #666;
        stroke-width: 1px;
    }

    circle {
        stroke: none;
    }

    text {
        fill: #444;
        font-size: 12px;
        font-family: sans-serif;
        text-anchor: middle;
    }
</style>

<body>
    <script src="//d3js.org/d3.v5.min.js"></script>
    <script src="https://unpkg.com/supercluster@4.1.1/dist/supercluster.min.js"></script>
    <script>
        const width = 480,
            height = 500;

        const color = d3
            .scaleOrdinal()
            .range(["#ef9a9a", "#9fa8da", "#ffe082", "#80cbc4"]);

        const projection = d3.geoMercator();

        const path = d3.geoPath().projection(projection);

        const svg = d3
            .select("body")
            .append("svg")
            .attr("width", width * 2)
            .attr("height", height);

        Promise.all([
            d3.json("four-corners.geo.json"),
            d3.json("random-points.geo.json")
        ]).then(([states, points]) => {
            projection.fitExtent([[10, 10], [width - 10, height - 10]], states);

            const left = svg.append("g");
            const right = svg.append("g").attr("transform", "translate(" + width + ")");

            // Draw background
            [left, right].forEach(g =>
                g
                    .selectAll("path")
                    .data(states.features)
                    .enter()
                    .append("path")
                    .attr("d", path)
            );

            // Original points on left
            left
                .selectAll("circle")
                .data(points.features)
                .enter()
                .append("circle")
                .attr("r", 2)
                .attr(
                    "transform",
                    d => "translate(" + projection(d.geometry.coordinates) + ")"
                )
                .attr("fill", d => color(d.properties.state));

            // Get a flat list of clusters within each state
            // Each one is GeoJSON plus x, y, and r properties
            const clusters = getClusters(points.features);

            // Draw the clusters
            const clustered = right
                .selectAll("g")
                .data(clusters)
                .enter()
                .append("g")
                .attr("transform", d => "translate(" + d.x + " " + d.y + ")");

            clustered
                .append("circle")
                .attr("r", d => d.r)
                .attr("fill", d => color(d.properties.state));

            // Label the clusters
            clustered
                .append("text")
                .text(d => d.properties.point_count || 1)
                .attr("dy", "0.35em");

            // Clusters on the border might overlap, nudge them apart with a collision force
            d3.forceSimulation(clusters)
                .force(
                    "collide",
                    d3
                        .forceCollide()
                        .strength(0.8)
                        .radius(d => d.r)
                )
                .on("tick", () =>
                    clustered.attr("transform", d => "translate(" + d.x + " " + d.y + ")")
                );
        });

        function getClusters(points) {
            const allClusters = [];

            // Group points by state
            const byState = d3
                .nest()
                .key(d => d.properties.state)
                .entries(points);

            // Cluster each group individually
            byState.forEach(entry => {
                const index = supercluster({
                    radius: 50,
                    maxZoom: 5
                });
                index.load(entry.values);
                index.getClusters([-180, -90, 180, 90], 5).forEach(cluster => {
                    // Add x, y, r, and state properties to each cluster
                    const [x, y] = projection(cluster.geometry.coordinates);
                    cluster.properties.state = entry.key;
                    cluster.x = x;
                    cluster.y = y;
                    cluster.r = cluster.properties.point_count ? 14 : 10;
                    allClusters.push(cluster);
                });
            });

            return allClusters;
        }
    </script>

preview.png

random-points.geo.json

thumbnail.png