点聚类算法

Question

我需要帮助解决一个几何问题。 考虑一个点集。 我们称点的数量为N。

我们用d表示欧几里得距离，dmax表示一个值。

仅当距离d（p1，p2）< dmax时，两个点p1和p2才会相连。

问题是创建一个算法，返回连接组件的尺寸列表。

例如，在下图中，算法应返回

[3, 2, 4, 1]

我用红色绘制了连接线，但最初我们只有点（这里是黑色）。 如有必要，程序应计算所有连接。 下面的图

我有两个算法，一个是迭代的，另一个是递归的。 我使用了 DBScan。 但它不够快。 复杂度为O（N ^ 2）

如果可能的话，我希望它更快，具有O（N）或O（N * log（N））的时间复杂度。

我读过深度优先搜索算法，但我不确定...

感谢您的帮助

- Wil123

---

你可以尝试使用 k-d 树来查找每个点的最近点。这样做可以消除计算远离的点之间距离的需求。 - fdermishin

这是一种不错的优化方式。但是我更新了问题，加入了一个要求：我不想在我的电脑上下载任何模块（抱歉我忘记提到了:\）。 - Wil123

Answer 1

使用SciPy（或其他库）查找输入点的Delaunay三角剖分（其中包含最小生成树，包括足够的边使其余答案可行）。删除长度≥dmax的三角剖分边缘。找到其余边缘的连接组件。

这是O(n log n)的算法，内部循环在Qhull中（一个编译扩展程序）。

（k-d树或其他局部结构提供了另一条解决方案的路径，但如果有许多距离dmax内的点对，则最坏情况可能是ω(n log n)。）

- David Eisenstat

---

我会研究一下并尝试。我会回来告诉你结果。不过需要一些时间才能完全理解这些概念 :) - Wil123

如果这个能够在scipy中运行，我会尝试自己编写Delaunay函数，而不是从scipy中导入它 :))) - Wil123

@Wil123 Delaunay三角剖分包含了最小生成树中的每一条边。最小生成树具有这样的性质，对于每一条被省略的边，由该边和最小生成树中的边形成的环没有比被省略的边更长的边。因此，如果存在一条路径，使得每一条边的长度都小于dmax，则存在一条满足该属性的路径，只使用最小生成树中的边。使用深度优先搜索来查找连通组件。 - David Eisenstat

谢谢您的回答。我会更深入地研究这个问题。我感觉离一个超级快速的算法非常接近了：））） - Wil123