从一组点构建图形的算法

Question

我需要一些输入来解决以下问题:

给定一组无序的 (X,Y) 点，我需要减少/简化这些点并最终得到一个连接的图形表示。

下图是一个实际数据集的例子和对应的期望输出(本人在MSPaint中手绘，画的很烂，但基本思路应该很清楚了)。

一些其他的东西:

• 输入大小将在 1000-20000 点之间
• 该算法将由用户运行，用户可以直观地看到输入/输出，调整输入参数等。因此，自动找到解决方案不是必需的，但用户应该能够在相当有限的范围内实现一个重试次数(和参数调整)。这也意味着生成的图上节点之间的距离可以是一个参数，不需要从数据中导出。
• 算法的时间/空间复杂度并不重要，但实际上应该可以在标准台式机上几秒钟内完成一次运行。

我认为这归结为两个截然不同的问题:

1) 运行过滤 channel ，减少点数(包括一些用于去除杂散点的噪声过滤)

2) 之后出现某种连接点图问题。在示例数据的底部/中心部分可以看到一个非常有问题的区域。连接图形的错误部分非常容易。

谁能指出我解决这个问题的正确方向？干杯。

Answer 1

• K-nearest neighbors (或者更准确地说，sigma 邻域)可能是一个很好的起点。如果您在严格的欧几里德空间中工作，您可以通过指定一些 L2 距离阈值来实现 90% 的目标，超过该阈值点将不连接。
• 下一步可能是某种 spectral graph analysis除了距离度量之外，您还可以使用某种光谱算法来定义点之间的边缘。这将为用户提供更多关于图形连接性的旋钮。

这两种方法都应该能够处理异常值，例如“嘈杂”点根本不会连接到其他任何东西。也就是说，您可能可以将它们组合起来以获得最佳性能(因为当没有 1 点聚类时，谱聚类表现得更好):运行基本的 KNN 来识别和删除异常值，然后进行谱分析以更稳健地建立边缘.