algorithm - 空间聚类算法

Question

给定二维平面上的点集合，我想找到彼此在 Y 范围内的 X 点集合。例如:

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)，算法将返回 [[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

---

我尝试过的事情:

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

Answer 1

只有 800 个点，您可以通过比较每一对来构建图形，然后运行 ​​Bron--Kerbosch找到最大的派系。这是该算法的合法 Javascript 实现:https://github.com/SeregPie/almete.BronKerbosch