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

Question

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

• 这组点是有序的并描述了一个轮廓
• 有时轮廓有一些噪音（见第二张图）
• 搜索到的角点不必是给定点集之外的点（见左下角第三张图）
• 搜索到的角点描述一个凸四边形，不一定是矩形

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

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

然后我想合并以下两条线，如果它们或多或少具有相同的度数，但我不知道如何处理这里的噪音或预测角落。

有谁知道处理这个问题或类似问题的算法？

Answer 1

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

1. 选择 4 对随机点。为每条线拟合一条线，因此您有 4 条线穿过点云。
2. 重复直到解决方案似乎已经收敛：
   1. 对于每个点，计算到 4 条线中每条线的距离。
   2. 将该点分配给与其最近的线相对应的存储桶。
   3. 将 4 条新线拟合到 4 个桶中的每一个中的点（您可以使用线性回归或 SVD）

为了改进第一步，您可以采用对角度进行直方图的想法，并将每个点最初分配给与最近峰值相对应的存储桶。然后将线拟合到四个桶，并开始迭代。

您也可以将此视为优化问题：选择 4 个点，使差异区域（四边形内部的白色区域和四边形外部的黑色区域）尽可能小。通用优化算法可能有效，但要使其快速，您需要一个合理的算法来计算面积。