Hierarchical Clustering in JavaScript

Question

I have some markers on google maps and I would like to identify clusters by point-to-point distance between them. However, I am having a bit of difficulty:

First I loop through all the markers and create an array which is:

for (var i = 0; i < MARKERS.length - 1; i++) {      
for (var j = i + 1; j < MARKERS.length; j++) {  
var distance_between = google.maps.geometry.spherical.computeDistanceBetween(point_i, point_j)
var valueToPush = {}
valueToPush.fromMarker = name_i
valueToPush.toMarker = name_j
valueToPush.distance = distance_between
cluster_array.push(valueToPush)
}
}

What I would then like to do is run a hierarchical clustering algorithm like this:

var cluster = .cluster(cluster_array, MAX, threshold)

Where if I specify 500 for threshold then I get a list like this

Cluster 0: Marker A, Marker Y, Marker C

Cluster 1: Marker B

Cluster 2: Marker D, Marker E

etc.

Where each cluster shows me the markers that are within 500 metres of each other.

Thanks very much

Answer 1

If it helps this is what I ended up doing:

function the_clusterer(cluster_array, num_radius) {
    console.log('Clustering distance array')
    for (var i = 0; i < cluster_array.length - 1; i++) {
        if (typeof(cluster_array[i]) != 'undefined') {
            var size_outer = 0,
                key_outer;
            for (key_outer in cluster_array[i]) {
                if (cluster_array[i].hasOwnProperty(key_outer));
                size_outer++;
            }
            for (var j = 0; j < size_outer; j++) {
                for (var k = i + 1; k < cluster_array.length; k++) {
                    if (typeof(cluster_array[i]) != 'undefined') {
                        var size_inner = 0,
                            key_inner;
                        for (key_inner in cluster_array[k]) {
                            if (cluster_array[k].hasOwnProperty(key_inner));
                            size_inner++;
                        }
                        var found_outer = 0
                        for (var l = 0; l < size_inner; l++) {
                            if (found_outer === 1) {
                                break;
                            }
                            if (cluster_array[k][l] == cluster_array[i][j]) {
                                found_outer++
                            }
                        }
                        if (found_outer > 0) {
                            for (var l = 0; l < size_inner; l++) {
                                var found_inner = 0
                                for (var m = 0; m < size_outer; m++) {
                                    if (cluster_array[i][m] == cluster_array[k][l]) {
                                        found_inner++
                                    }
                                }
                                if (found_inner == 0) {
                                    cluster_array[i][size_outer] = cluster_array[k][l]
                                    size_outer++
                                }
                            }
                            delete cluster_array[k];
                        }
                    }
                }
            }
        }
    }
    txtOutput.value += "Start Clusters: " + num_radius + "m.\n"
    var k = 0
    for (var i = 0; i < cluster_array.length - 1; i++) {
        var size_outer = 0,
            key_outer;
        for (key_outer in cluster_array[i]) {
            if (cluster_array[i].hasOwnProperty(key_outer));
            size_outer++;
        }
        if (size_outer > 0) {
            k++
            var temp_line = "Cluster " + k + ":"
            for (var j = 0; j < size_outer; j++) {
                temp_line = temp_line + " Marker " + cluster_array[i][j]
            }
            txtOutput.value += temp_line + ".\n"
        }
    }
}