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

Question

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

• 点集是有序的并描述了一个轮廓
• 有时轮廓会有一些噪音(见第二张图)
• 搜索到的角点不必是给定点集中的点(见左下图3)
• 搜索到的角点描述的是凸四边形，不一定是矩形

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

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

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

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

Answer 1

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

1. 随机选择 4 对点。为每条线拟合一条线，因此您有 4 条线穿过点云。
2. 重复直到解收敛:
   1. 对于每个点，计算到 4 条线中每条线的距离。
   2. 将点分配给与其最近的线相对应的桶。
   3. 将 4 条新线拟合到 4 个桶中的每个点(您可以使用线性回归或 SVD)

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

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