提取满足一定条件的点

Question

我在一个平面上有一个点阵列。它们形成一些形状。我需要从这个数组中提取仅仅形成这种形状的直线的点。

在这一刻我有一个算法，但它不工作很好。我先拿两点，做一条直线，然后检查以下几点是否有一定的容差。但是存在一个问题：形成直线的点并不是真正的直线，而是有一些偏差。这种偏差非常大。如果在我的算法中，我的偏差大到足以从直线部分得到点，那么稍微弯曲的部分上的其他点也会被提取出来。

我在寻找一些关于如何执行这样的任务的想法。

这里是图片：

圈子中的人是我要提取的部分。红点是我可以用我的方法提取的部分。如果我增加容忍度，那么我也会错过这些直线段。

Answer 1

首先，如果您已经有一些候选子集的点，并且想要检查它们是否位于一条直线上。使用linear regression的形式来确定最佳拟合线，然后检查它是否合适，并接受或拒绝假设此特定片段基于此线性为线性。

这样做的最标准方法之一是使用Least Squares方法。

识别子集是一个不同的问题，最好的解决方案将取决于您拥有的数据类型和目标。我建议列举所有细分是一个很好的起点，如果数据量不是非常大的话 - 我应该在不超过立方时间的情况下做到这一点。

当然有一些近似值可以应用，例如，在序列中选择一个点并通过在任一侧上迭代地添加点来构建子集，只要该段在容限阈值内保持线性即可，而如果该段足够长则接受或拒绝该点。

我在这里假设曲线可以通过其中一个坐标进行参数化。如果不是这种情况，例如如果曲线闭合，则可能需要额外的步骤将曲线分成可参数化的段。

编辑：如何检查段是直的 有许多选项。

首先，我希望，对于一个直线的平均偏差将保持大致相同，你添加新的点，那么你可以简单地找到给出的数据上，合理的阈值。

第二个选项是进一步将子集分成固定数量的部分（例如2），为每个部分找到最佳拟合线，然后比较它们。如果是直线，则应预测大致相同的线条，但对于曲线而言，则会有所不同。

第三选项是执行非线性曲线拟合，例如，拟合二次曲线并检查二次项的系数 - 如果直线是直线，则应接近于零。

在每种情况下，当然，有段大小，并从该段的点的偏差之间的折衷。在极端情况下，可能会有一个巨大的偏离的巨大的线性分段或者是一个2分段的偏差为0的整个分支。必须为给定数据集选择偏差的实际阈值，切线曲线之间的差异或二次项的大小（取决于您偏好的选项）以满足您的需求。看看情节，我会说应该挑选阈值，以便允许长度为10左右的段。