删除坐标列表中接近相同的值

Question

我有一个与此类似的值列表：[[100,100],[101,101],[101,103],[102,103],[104,101],[103,101],[542,121],[943,123]]我想将接近的值减少到一个单一的值——它可以是一个平均值，但我不依赖于那个特殊性——同时保持独特的值。因此，从该示例列表中，我想得到类似的信息：[[101,103],[542,121],[943,123]]我已经考虑过对值进行除法和四舍五入，去除重复值，然后将它们相乘以达到我的规模，但这会给我的结果[[100,105],[540,120],[945,125]]我想保持唯一值的唯一性。

Answer 1

假设“相似”意味着“在相同中心值的 20 之内”——即所有点的集合，这些点在它们的组合质心的 20 之内。（当然，20 是任意且可配置的。）然后您可以像这样减少列表（假设调用了初始数组data）：

const threshold = 20;

const thresholdSq = threshold ** 2;

const groups = data.reduce((map, pair) => {

    let mini = Infinity, match = null;

    map.forEach(list => {

        const avg = list.reduce((sum, point) => {

            sum[0] += point[0];

            sum[1] += point[1];

            return sum;

        }, [].concat(pair));

        avg[0] /= 1 + list.length;

        avg[1] /= 1 + list.length;

        const distSquared = (avg[0] - pair[0]) ** 2 + (avg[1] - pair[1]) ** 2;

        if (distSquared < mini && distSquared <= thresholdSq) {

            mini = distSquared;

            match = list;

        }

    });

    if (match) {

        match.push(pair);

    } else {

        map.push([pair]);

    }

    return map;

}, []);

const result = groups.map(list => {

    const sum = list.reduce((acc, v) => {

        acc[0] += v[0];

        acc[1] += v[1];

        return acc;

    }, [0,0]);

    sum[0] /= list.length;

    sum[1] /= list.length;

    return sum;

});

对于您的示例数据，结果变为：

[[101.83333333333333, 101.5], [542, 121], [943, 123]]

这并不完全是您指定的输出，但它确实保留了唯一值并为您提供了其他点组的平均值。

Answer 2

一个想法可能是将第一个点分组到桶中，然后你可以对桶做任何你想做的事情，例如平均它们......

class Point {

  constructor(x, y) {

    this.x = x;

    this.y = y;

    this.threshold = 5;

  }

  isSimilar(other) {

    return Math.abs(this.x - other.x) < this.threshold && Math.abs(this.y - other.y) < this.threshold;

  }

  avg(other) {

      return new Point(Math.round((this.x + other.x) / 2), Math.round((this.y + other.y)/2));

  }

}

var list = [new Point(100,100),

    new Point(101,101),

    new Point(101,103),

    new Point(102,103),

    new Point(104,101),

    new Point(103,101),

    new Point(542,121),

    new Point(943,123)];

var buckets = []

// Group similar points into buckets

list.map(function (p) {

    var bucket = buckets.find(function(b) { return b[0].isSimilar(p); });

    if(bucket == undefined) {

        buckets.push([p]);

    } else {

        bucket.push(p);

    }

});

// Here you could for example average each bucket

var avg = buckets.map(function(b) {

    return b.reduce(function(a, b) { return a.avg(b); });

});

console.log(avg);

结果：

[

  Point { x: 103, y: 102, threshold: 5 },

  Point { x: 542, y: 121, threshold: 5 },

  Point { x: 943, y: 123, threshold: 5 }

]

注意：使用classECMAScript 2015 引入的...

Answer 3

我已经在 Slack 中提到了这一点，但是如何生成 Voronoi 图，然后找到所有面积小于某个给定值的单元格，并删除 (N-1) 个组成单元格的点？

尽管有一个很小的区域，但单元真的很长的边缘情况可能会出现一些问题......