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 } ]
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 } ]
- @Igor don't just troll the guy if you didn't get the question... for the rest of us is pretty clear what he wants... of curse I up-voted this question. – Adrian Salazar Commented Oct 29, 2015 at 14:00
3 Answers
Reset to default 4A solution can be to pute 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.
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/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/wiki/DBSCAN
I have used the density-clustering library from NPM. https://github./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
That is actually really easy - bine all X's into 1 variable, and devide it by the number of X's. Same goes for y:
var totalX = 0, totalY = 0, avgX, avgY;
var coords = [ { 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 } ]
for (var i = 0; i <= coords.length; i++) {
totalX += coords[i].x;
totalY += coords[i].y;
}
avgX = totalX / coords.length;
avgY = totalY / coords.length;
See it in action harrr (lol at ID): https://jsfiddle/harr55d2/
EDIT: This is not the right answer, sorry, misread your question.
What you could do though, is take this avarage place and from there calculate the distances to all points from there. You'll get some numbers from that. If you then calculate an avarage on the distance i think you'll get close to the point that you want to be.
Another method is to scan the 200x200 area in blocks of 20x20 (or something, maybe circles works best) and count all votes in there. The one with the most votes wins.
EDIT: Another method;
Take the distance for each vote from the avarage point. Then that is the "score" or "weight" for a certain vote. You can then see that the votes closest to the avarage are being weighted the "best". If you catch my drift.