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

Question

我尝试从一组点获得四边形的角点.

• 订购点集并描述大纲
• 有时轮廓有一些噪音(见第2张图)
• 搜索到的角点不必是给定点集之外的点(参见左下角的第3张图)
• 搜索的角点描述了凸四边形,不一定是矩形

第二张照片有点极端,但我的一组点的"质量"位于第一张照片和第二张照片之间.

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

然后我考虑合并两个以下的行,如果它们具有或多或少相同的程度,但我不知道如何处理这里的噪音或预测角落.

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

Answer 1

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

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

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

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