JS - 基于密度的精细点数

Question

假设我有一个如下数组(每个小数组[x, y]):

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

假设我需要将阵列缩小到4分.(这是一个小例子,我的实际阵列有几千个点)我怎样才能根据密度对阵列进行细化,以便从点距离较近的区域中移除更多的点,从较低密度的区域移除较少的点？

在这种情况下(将上面的数组从8项减少到4项)我希望返回的数组看起来如下所示:

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

关于如何处理这个问题的想法是生成一个字典,将点映射到它与另一个点的最小距离(例如,靠近另一个点的点将具有较小的最小距离)然后根据递增的最小距离对字典进行排序,然后删除字典中的每个n'tn项.

这种方法的问题是我不知道如何有效地为每个点生成距离最近的其他点值的距离.

有没有一种有效的方法来生成这些值,或者是否有另一种方法来处理这种基于密度的细化问题？

谢谢!

Answer 1

看来您想要解决 P 中心问题或 P 中值问题。

\n\n

\n\n

\n
中心p问题，也称为最小-最大多中心问题或设施位置问题，是运筹学研究中的一个著名问题。通俗地说，这是在城市中放置消防站以使到达城市中任意地点的最大时间最小化的问题。
\n

\n\n

\n\n

\n
中p值问题简单地表述为：给定一个图或网络\n G = (V, E)，找到Vp \xe2\x8a\x86 V这样的\n |Vp| = p，其中p\n可以是可变的或固定的[...]，并且距顶点的最短距离\n的总和到{V\\Vp}最近的顶点Vp被最小化。
\n

\n\n

一般来说，这两个问题都是 NP 完全问题，因此没有（已知）方法可以在多项式时间内解决它们。但您可以尝试各种启发法。

\n