空间聚类算法

Question

给定一个二维平面上的点集合，我想找到 X 个点的集合，这些点彼此之间的距离在 Y 以内。例如：

8|
7|    a     b
6|
5|       c
4|
3|                    e
2|                  d          
1|
-------------------------
  1 2 3 4 5 6 7 8 9 0 1

a、b、c 和 d 是二维平面上的点。给定点数参数 3 (X) 和距离参数 3 (Y)，算法将 return [[a, b, c]]。一些例子：

algorithm(X = 3, Y = 3) returns [[a, b, c]]
algorithm(X = 2, Y = 3) returns [[a, b, c], [d, e]] -- [a, b, c] contains at least two points
algorithm(X = 4, Y = 3) returns [] -- no group of 4 points close enough
algorithm(X = 5, Y = 15) returns [[a, b, c, d, e]]

限制条件：

x 轴和 y 轴（上面的数字）都是 10,000 个单位长
图表上有 800 个点（a、b、c、d 等）
我认为这不重要，但我正在使用 JavaScript

我尝试过的事情：

我实际上关心的是输出接近多个输入点的新点，因此我尝试在网格上迭代并 'looking around' 它使用毕达哥拉斯找到给定距离外的每个点。考虑到总面积，这太慢了。 See the source here。您还可以在 real data test.
DBSCAN，这似乎有不同的目的 - 我知道我希望我的集群大小有多大。
我正在 currently 尝试相互比较点并建立紧密对，然后关闭三胞胎等，直到最后，但这似乎也有点低效.我将继续并尝试某种散列或字典来避免这些循环。

Answer 1

只有 800 个点，您可以通过比较每一对来构建图表，然后运行 Bron--Kerbosch to find maximal cliques. Here's a legit-seeming Javascript implementation of that algorithm: https://github.com/SeregPie/almete.BronKerbosch

空间聚类算法

Spacial clustering algorithm

algorithm

cluster-analysis