JS - Thin number of points based on density

Question

Let's say I have an array as follows (each small array is [x, y] ):

 var myPoints = [[25, 28], [26, 26], [70, 40], [50, 50], [300, 300], [285, 350], [1000, 1000]]; 

Let's say I need to trim the array to 4 points. (this is a small example, my acutal array has thousands of points). How could I thin out an array based on density, so more points are removed from areas with points closer to each other, and fewer points are removed from areas with lower density?

In this case (with decreasing the specified array from 8 to 4 elements), I expect the returned array to look something like this:

 var thinnedPoints = [[25, 28], [70, 40], [300, 300], [1000, 1000]]; 

My idea of ​​how to approach this would be to create a dictionary that displays the minimum distance to another point on it (for example, a point close to another point would have a minimum minimum distance), and then sort the dictionary based on the bottom minimum then delete each element of the n'tn dictionary.

The problem with this approach is that I do not know how to efficiently generate the distance to the nearest other point value for each point.

Is there an efficient way to generate these values, or maybe there is another way to approach this problem based on density based on density?

Thanks!

Answer 1

It seems you want to solve the problem of the P-center or the P-median.

From the approximation results for the p -Center problem from Stefan Buettcher,

The p -Center problem, also known as the Multicenter Min-Max problem or the object location problem, is a known problem from exploration operations. Informally, the problem of placing fire stations in cities is to minimize the maximum time to reach any point in the city.

Of Solutions to the p -Median Problem: An Annotated Bibliography of J. Reese,

The p -median problem is simply indicated as: for a graph or network G = (V, E) , find Vp ⊆ V such that |Vp| = p |Vp| = p , where p can either be variable or fixed [...], and the sum of the shortest distances from the vertices in {V\Vp} to their nearest vertex in Vp is minimized.

Both problems are completely NP-complete, so there is no (known) way to solve them in polynomial time. But there are various heuristics that you could try.

Answer 2

A very simple and effective solution that works especially well on large sets is to simply select points at random. This implicitly removes fewer points from regions containing fewer points than anywhere else, which is similar to what you want if you only want to scale the density linearly. It should produce the same results as your approach, without the need to calculate distances.

If the data are not sorted in any way (i.e. already random), you can also delete every second point or only the first or second half.

If you want to adjust the distribution of non-linearity non-linearly, you can divide the set into several areas (for example, squares) that are small enough so that the density is approximately the same in each of them, and then drop every n-th part of the points for the region. If you choose the region size appropriately, this approach can also provide better (and more consistent) results than purely random ones for small datasets.

Answer 3

You can use the for..of loop, for , .map() , Math.min() , .filter() .

Scroll through each element of the array, assign x , y to separate the array variables; subtract the difference between each element in arrays x or y ; map original array, start by removing the first or second element of the matched pair, where the two elements have the smallest numerical difference between any other number in the array; that is, two numbers are separated by the least number of digits. Continue to delete elements as the distance between the numbers increases to n , here, 3 , the elements are deleted from the original array.

For example, a mapping x may return either

  [[25, 28], [70, 40], [300, 300], [1000, 1000]]; 

or

  [[26,26], [50,50], [285,350], [1000,1000]] 

since the range between the numbers is the same in the direction

  [1, 1, 20, 20, 15, 15, 700] 

 var myPoints = [ [25, 28], [26, 26], [70, 40], [50, 50], [300, 300], [285, 350], [1000, 1000] ]; var [x, y] = [ [], [] ]; var [xx, yy] = [ [], [] ]; for (let z of myPoints) { [x, y] = [ [...x, z[0]], [...y, z[1]] ]; } var stop = 3; for (var i = 0; i < x.length; i++) { var prop = x[i]; if (typeof xx[i] !== "object") { xx[i] = { index: i, diff: [], value: prop }; } for (var len = 0; len < x.length; len++) { var key = x[len]; xx[i].diff.push( prop > key ? prop - key : key > prop ? key - prop : Infinity ) } } var range = xx.map(prop => Math.min.apply(Math, prop.diff)); var temp = range.slice(0); for (var i = 0; i < stop; i++) { var curr = Math.min.apply(Math, temp); var index = temp.indexOf(curr); temp[index] = Infinity; var pair = Math.min.apply(Math, temp); var next = temp.indexOf(pair); temp[next] = Infinity; x[next] = void 0; }; var res = myPoints.map((prop, index) => x[index] === undefined ? null : prop).filter(Boolean); console.log(res); 

use as function

 var myPoints = [ [25, 28], [26, 26], [70, 40], [50, 50], [300, 300], [285, 350], [1000, 1000] ]; var filter = (arr, xy, n) => { var [x, y] = [ [], [] ]; var [xx, yy] = [ [], [] ]; for (let z of arr) { [x, y] = [ [...x, z[0]], [...y, z[1]] ]; } var XY = { "x": [x, xx], "y": [y, yy] }; var item = XY[xy]; var stop = n; for (var i = 0; i < item[0].length; i++) { var prop = item[0][i]; if (!item[1][i]) { item[1][i] = { index: i, diff: [], value: prop }; } for (var len = 0; len < item[0].length; len++) { var key = item[0][len]; item[1][i].diff.push( prop > key ? prop - key : key > prop ? key - prop : Infinity ) } } var range = item[1].map(prop => Math.min.apply(Math, prop.diff)); var temp = range.slice(0); for (var i = 0; i < stop; i++) { var curr = Math.min.apply(Math, temp); var index = temp.indexOf(curr); temp[index] = Infinity; var pair = Math.min.apply(Math, temp); var next = temp.indexOf(pair); temp[next] = Infinity; item[0][next] = void 0; }; return arr.map((prop, index) => item[0][index] === undefined ? null : prop).filter(Boolean); } console.log(filter(myPoints, "x", 3));