algorithm - 从一组点中找到四边形的角点

我尝试从一组点中获取四边形的角点。

点集是有序的，并描述了一个轮廓

有时轮廓有些杂音(请参见第二张图片)

搜索的角点不必一定是给定点集中的点(请参见左下方的第三张图片)

搜索的角点描述了凸四边形，不一定是矩形

第二张图片有些极端，但是我的观点集的“质量”介于第一张图片和第二张图片之间。

首先，我想到了从1-360°和长度上制作直方图的方法，以下两点说明了这一点。四个最高峰将描述每条线的长度。但是由于失去顺序点，所以只知道度数和长度或一条线，却不知道一条线属于哪个位置。

然后，我想到了合并以下两条线，如果它们具有或多或少相同的程度，但是我不知道如何处理此处的噪音或预测拐角。

有谁知道可以解决此问题或类似问题的算法？

最佳答案

您可以将其视为聚类问题，其中聚类的“中心”实际上是直线。要计算聚类，可以使用k-means算法:

随机选择4对点。每条线都适合，因此您有4条线穿过点云。

重复直到解决方案似乎收敛为止:

对于每个点，计算到4条线中每条线的距离。

将点分配给与其最接近的线相对应的存储桶。

在4个桶中的每个点上插入4条新行(可以使用线性回归或SVD)

为了改进第一步，您可以考虑对各个角度进行直方图绘制，然后将每个点最初分配给与最接近的峰相对应的存储桶。然后将线装配到四个桶中，并开始进行迭代。

您也可以将其视为优化问题:选取4个点，以使差异的面积(四边形内部的白色区域和四边形外部的黑色区域)最小。通用优化算法可能会起作用，但是要使其快速运行，您需要一种合理的算法来计算面积。

关于algorithm - 从一组点中找到四边形的角点，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/15351616/