Calculate the center point of the highest density of xy points

Question

I have a square grid (200 x 200). I would like users to be able to vote on their next desired position of an object in this space. When a user votes I add the XY position to an array.

Currently to find the "winning" position I just take an average of X and an average of Y, but what I've found is the winning position tends to gravitate around the middle of the area (naturally as it's an average!).

White = votes, Yellow = "winning" XY point

What I'd prefer is if it found the densest area of votes, and chose a point in the middle of that.

I.e single scattered votes don't pull the winning position too far from the dense area like an average does.

Is that possible?

Example array

[ { x: 39, y: 28 },
  { x: 69, y: 33 },
  { x: 51, y: 51 },
  { x: 14, y: 63 },
  { x: 75, y: 140 },
  { x: 171, y: 68 },
  { x: 140, y: 53 },
  { x: 173, y: 150 },
  { x: 123, y: 179 },
  { x: 103, y: 150 },
  { x: 145, y: 119 },
  { x: 92, y: 85 },
  { x: 58, y: 49 },
  { x: 28, y: 65 },
  { x: 41, y: 39 },
  { x: 46, y: 41 },
  { x: 49, y: 51 },
  { x: 43, y: 55 },
  { x: 35, y: 48 },
  { x: 29, y: 31 },
  { x: 68, y: 22 },
  { x: 58, y: 39 } ]

Answer 1

A solution can be to compute for every point the sum of distances from it to all other points. The point with the smallest sum should be the center of the area with the highest density.

Answer 2

Well, I'm not posting just an idea but I'm posting actual code. Hope you can see if it works for you.

Your problem basically falls into the realm of cluster analysis. You want to identify the different groups of data present in your dataset and which form a cluster. https://en.wikipedia.org/wiki/Cluster_analysis

Lucky for you, this problem has already a few method to be solved, and there's even an NPM package that allows you to execute some of the well know cluster analysis tools.

I have chosen DBSCAN for solving your set of points, feel lucky to give another algorithm a try if you feel you need something else. https://en.wikipedia.org/wiki/DBSCAN

I have used the density-clustering library from NPM. https://github.com/LukaszKrawczyk/density-clustering

The arbitrary parameters given to DBSCAN were 20 for the neighbourhood radius and 5 for the minimum number of point to be considered a "cluster"

And the code is a modified version of the example given in the github page of the NPM package.

var sample = [ { x: 39, y: 28 },
  { x: 69, y: 33 },
  { x: 51, y: 51 },
  { x: 14, y: 63 },
  { x: 75, y: 140 },
  { x: 171, y: 68 },
  { x: 140, y: 53 },
  { x: 173, y: 150 },
  { x: 123, y: 179 },
  { x: 103, y: 150 },
  { x: 145, y: 119 },
  { x: 92, y: 85 },
  { x: 58, y: 49 },
  { x: 28, y: 65 },
  { x: 41, y: 39 },
  { x: 46, y: 41 },
  { x: 49, y: 51 },
  { x: 43, y: 55 },
  { x: 35, y: 48 },
  { x: 29, y: 31 },
  { x: 68, y: 22 },
  { x: 58, y: 39 } ];


/* Transform your dataset to the format expected by the library */
var dataset = [];

for(var i=0; i<sample.length; i++){
   dataset.push([sample[i].x, sample[i].y]);
}

var clustering = require('density-clustering');
var dbscan = new clustering.DBSCAN();
/* parameters: 
    20 - neighborhood radius
    5 - number of points in neighborhood to form a cluster
*/
var clusters = dbscan.run(dataset, 20, 5);

if(clusters.length > 0){

    /* Find the biggest cluster */
    var biggestCluster = clusters[0];

    for(i=1;i<clusters.length;i++){

        if(cluster[i].length > biggestCluster.length){
            biggestCluster = cluster[i];    
        }
    }

    /* The output of the library contains the indexes of the points in the cluster, not the coordinates, so we need to get the point from the dataset */
    var clusterPoints = [];
    var sumx = 0;
    var sumy = 0;

    for(i=0;i<biggestCluster.length;i++){
       var point = dataset[biggestCluster[i]];
       clusterPoints.push(point);

       /* It's also a good opportunity to cumulate x and y so we can get the average */
       sumx+=point[0];
       sumy+=point[1];
    }

    console.log('Cluster:', clusterPoints);    
    console.log('Center:', sumx/clusterPoints.length, sumy / clusterPoints.length);
}
else{
    console.log('No clusters');
}

The output from this program will be:

Cluster: [ [ 51, 51 ], [ 58, 49 ], [ 41, 39 ], [ 46, 41 ], [ 49, 51 ], [ 43, 55 ],  [ 35, 48 ],  [ 58, 39 ], [ 69, 33 ],  [ 39, 28 ], [ 29, 31 ], [ 28, 65 ], [ 68, 22 ] ]

Center: 47.23076923076923 42.46153846153846