simple-clusterer

    1.1.2 • Public • Published

    Highly customisable, generic, single-level clusterer that works for user interfaces and small-medium data sets.

    This isn't well suited for crunching scientific data, but works well for clustering user-interface elements, for example coalescing items on a map or timeline where icons need to maintain a minimum distance before they overlap.

    Can create a clusterer to work on an array of any type T with positions of any type P, so long as simple Number distances can be computed between two positions

    Generates only single-depth clusters. For multiple depth, call recursively.

    Installing

    npm install --save simple-clusterer

    Testing

    npm test

    API

    Create a clusterer by calling:

    const myClusterer = simpleClusterer(position, distance, mergePositions, elementOrder, clusterOrder)

    Where the parameters are:

    position:          T => P              a function get the position of an item
    distance:          (P, <P>) -> Number    a function to compute the distance between two positions
    mergePositions:    [<P>] -> <P>       a function compute the midpoint (or other merge kind) between several positions. This is
                                                used to calculate the position of clusters of elements
    elementOrder:      <T> -> {*}              OPTIONAL - the order of elements inside a cluster.
    clusterOrder:      <Cluster<T>> -> {*}
    
    

    This can then be called like:

    myClusterer(items, minimumDistance)
    items:             [<T>]                    array of items to be clustered
    minimumDistance:   Number                   minimum distance two output clusters may be. No two clusters returned
                                                will be closer than this distance
    

    Performance

    Clustering random numbers, running on node 7.2.1 on a 2014 Macbook Pro. Performance is good for sizes up to about 500, and degrades quickly after 2000. That seems a sensible maximum to load into an interface.

    These results can be reproduced by running the tests.

    clustering 10 random numbers into 9 clusters took 0ms
    clustering 20 random numbers into 17 clusters took 1ms
    clustering 100 random numbers into 46 clusters took 6ms
    clustering 250 random numbers into 59 clusters took 10ms
    clustering 500 random numbers into 69 clusters took 30ms
    clustering 1000 random numbers into 67 clusters took 133ms
    clustering 2000 random numbers into 72 clusters took 725ms
    

    Usage Example

    const sumBy = require('lodash.sumby')
    const pythagorasXY = (p1, p2) => Math.sqrt(Math.pow(p2.x - p1.x, 2) + Math.pow(p2.y - p1.y, 2))
    const centreOfMass = ps => ({
        x: sumBy(ps, 'x')/ps.length,
        y: sumBy(ps, 'y')/ps.length
    })
    const simpleClusterer = require('./simple-clusterer.js')
    const clusterByLocation = simpleClusterer(
        place => place.location,
        pythagorasXY,
        centreOfMass,
        'name' // sort inside clusters alphabetically
    )
     
    const clusters = clusterByLocation([
        {name: 'house',         location:{x:1, y:4}},
        {name: 'office',        location:{x:2, y:6}},
        {name: 'tree',          location:{x:3, y:8}},
        {name: 'field',         location:{x:4, y:1}},
        {name: 'gate',          location:{x:9, y:8}},
        {name: 'road',          location:{x:7, y:7}},
        {name: 'path',          location:{x:5, y:5}},
        {name: 'factory',       location:{x:6, y:9}},
        {name: 'school',        location:{x:7, y:0}},
        {name: 'university',    location:{x:8, y:1}},
        {name: 'park',          location:{x:9, y:3}}
    ], 4)
     
    // returns four clusters like:
     
    [
        {
            "elements": [
                {
                    "name": "field",
                    "location": {"x": 4, "y": 1}
                }
            ],
            "position": {"x": 4, "y": 1}
        },
        {
            "elements": [
                {
                    "name": "house",
                    "location": {"x": 1, "y": 4}
                },
                {
                    "name": "office",
                    "location": {"x": 2, "y": 6}
                },
                {
                    "name": "path",
                    "location": {"x": 5, "y": 5}
                },
                {
                    "name": "tree",
                    "location": {"x": 3, "y": 8}
                }
            ],
            "position": {"x": 2.75, "y": 5.75}
        },
        {
            "elements": [
                {
                    "name": "factory",
                    "location": {"x": 6, "y": 9}
                },
                {
                    "name": "gate",
                    "location": {"x": 9, "y": 8}
                },
                {
                    "name": "road",
                    "location": {"x": 7, "y": 7}
                }
            ],
            "position": {"x": 7.333333333333333, "y": 8}
        },
        {
            "elements": [
                {
                    "name": "park",
                    "location": {"x": 9, "y": 3}
                },
                {
                    "name": "school",
                    "location": {"x": 7, "y": 0}
                },
                {
                    "name": "university",
                    "location": {"x": 8, "y": 1}
                }
            ],
            "position": {"x": 8, "y": 1.3333333333333333}
        }
    ]
     

    Install

    npm i simple-clusterer

    DownloadsWeekly Downloads

    0

    Version

    1.1.2

    License

    BSD-2-Clause

    Last publish

    Collaborators

    • jimhigson