给定二维平面上的点集合，我想找到彼此在 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试图相互比较点并建立紧密的对，然后关闭三胞胎，等等，直到最后，但这似乎也有点低效。我将继续尝试使用某种哈希算法或字典来避免这些循环。
最佳答案
只有 800 个点，您可以通过比较每一对来构建图形，然后运行 Bron--Kerbosch找到最大的派系。这是该算法的合法 Javascript 实现:https://github.com/SeregPie/almete.BronKerbosch
关于algorithm - 空间聚类算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/55047792/