计算xy点密度最高的中心点

Question

我有一个方形网格 (200 x 200)。我希望用户能够在此 space 中对对象的下一个期望位置进行投票。当用户投票时，我将 XY 位置添加到数组中。

目前为了找到 "winning" 位置，我只取 X 的平均值和 Y 的平均值，但我发现获胜的位置往往集中在该区域的中间（自然地这是一个平均值！）。

白色=投票，黄色="winning" XY点

我更喜欢它找到投票最密集的区域，然后选择中间的一个点。

即单个分散的选票不会像平均那样将获胜位置拉离密集区域太远。

这可能吗？

示例数组

[ { 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

这其实很简单 - 将所有 X 组合成 1 个变量，然后除以 X 的个数。同样适用于 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;

看到它在行动哈尔（笑在ID）：https://jsfiddle.net/harr55d2/

编辑：这不是正确答案，抱歉，误读了您的问题。

不过，您可以做的是占据这个平均位置，然后从那里计算到所有点的距离。你会从中得到一些数字。如果您然后计算距离的平均值，我认为您会接近您想要的点。

另一种方法是以 20x20 块为单位扫描 200x200 区域（或其他东西，也许圆圈效果最好）并计算其中的所有选票。得票最多者获胜。

编辑：另一种方法；

取每张选票与平均点的距离。那么就是某票的"score"或"weight"。然后您可以看到最接近平均数的选票被加权 "best"。如果你明白我的意思。

Answer 2

一个解决方案可以是为每个点计算从它到所有其他点的距离总和。总和最小的点应该是密度最高的区域的中心。

Answer 3

好吧，我不只是发布一个想法，而是发布实际代码。希望你能看看它是否适合你。

你的问题基本属于聚类分析范畴。您想要识别数据集中存在的不同数据组并形成一个集群。 https://en.wikipedia.org/wiki/Cluster_analysis

幸运的是，这个问题已经有一些方法可以解决，甚至还有一个 NPM 包可以让你执行一些众所周知的集群分析工具。

我选择了 DBSCAN 来解决你的点集，如果你觉得你需要别的东西，很幸运可以尝试另一种算法。 https://en.wikipedia.org/wiki/DBSCAN

我使用了 NPM 的密度聚类库。 https://github.com/LukaszKrawczyk/density-clustering

给予 DBSCAN 的任意参数是 20 邻域半径和 5最少要考虑的点数 a "cluster"

并且该代码是 NPM 包的 github 页面中给出的示例的修改版本。

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');
}

这个程序的输出将是：

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

计算xy点密度最高的中心点

Calculate the center point of the highest density of xy points

javascript

arrays

coordinate-systems