algorithm - 是否有一种算法可以确定连续区域中的元素数量？

Question

我有一组放置在二维欧几里德空间中的点。如果两点之间的距离小于预定的截止半径，则它们被认为是邻居。我想计算连续区域中元素的数量(例如，假设 1 和 2 是邻居。如果 2 和 3 以及 3 和 4 也是邻居，那么我们有 4 个彼此相邻的元素).

我一整天都在谷歌搜索，遇到了很多关键字，比如 kd-tree，k 表示聚类，图遍历，泛洪填充和连通分量分析，但我现在无法全部学习观点。我只需要一些方向来将我的努力集中在正确的方向上。

Answer 1

你的问题看起来像一个 connected component分析!

首先是将您的数据表示为图形，为此有大量的库。让我们以python为例:你可以使用Networkx或 Graph-tool .它很简单，因为一个点可以表示为一个节点。关于边缘，您基本上有几种解决方案。

您可以进行蛮力比较，将所有点相互比较。它将在 O(n * (n-1)/2) 中运行，如果数据集很小，则可以。如果数据集很大，您可以使用不同的近似算法(KD 树、球树)，在 Flann 中实现。或 scikit-learn .请注意，scikit-learn 还为您提供了蛮力比较。

此处的目标是在距离低于阈值时在两个节点(点)之间创建边(链接)。

在图中添加节点和边后，您可以运行连通分量算法，该算法给出图中的所有连通分量。连通分量基本上是由边连接的一组连续节点。

请注意，一旦您的问题用图表表示，将近 70 年的图论就会派上用场。您可以使用 subgraph isomorphism 检查某些区域是否与其他区域具有相同的形状.您可以使用 centrality measures 检查每个组件中每个点的重要性。 .您还可以将连续区域划分为子区域，而无需使用 graph partitioning 对边缘进行阈值处理。 .

您可以在我的 blog 上看到一个连续图被分割成多个分区的实例。 .

为了论证:这里是属于同一个图中的几个连接组件的示例(具有自边)。