Removing near identical values in a list of coordinates

user_625222 0
Viewed 73

I have a list of values similar to this:

[[100,100],[101,101],[101,103],[102,103],[104,101],[103,101],[542,121],[943,123]]

I'd like to reduce the near values to a single value - it can be an average, but I'm not tied to that specificity - while maintaining the unique values.

So from that example list, I'd like to get something like:

[[101,103],[542,121],[943,123]]

I've considered just dividing and rounding the values, getting rid of the repeating values, then multiplying them back to get to my scale, but that would give me a result of

[[100,105],[540,120],[945,125]]

and I'd like to maintain the uniqueness of the unique values.

javascript
3 Answers

Let's say "similar" means "within 20 of the same center value" -- i.e. the set of all points that are within 20 of their combined center of mass. (20 is arbitrary and configurable, of course.) Then you can reduce the list like so (assuming the initial array is called 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;
});

For your example data, result becomes this:

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

It's not exactly what the output you specified, but it does preserve unique values and give you the averages of the other groups of points.

user_24442100

I already mentioned this in Slack, but what about generating a Voronoi diagram, then finding all cells that are smaller than some given value in area, and removing (N-1) of the points that make up the cell?

There might be some problems with edge cases where the cell is REALLY long, despite having a tiny area though...

user_130890

One idea could be to group first points into buckets, then you could do whatever you want with buckets, e.g. average them...

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

Result:

[
  Point { x: 103, y: 102, threshold: 5 },
  Point { x: 542, y: 121, threshold: 5 },
  Point { x: 943, y: 123, threshold: 5 }
]

NB: Using class indroduced by ECMAScript 2015...

user_33117990
Related