最佳拟合矩形的算法

Question

我正在寻找一种算法来将任意矩形最佳拟合到一组无序点.具体来说,我正在寻找一个矩形,其中点与任何一个矩形边的距离之和最小.我发现了很多最合适的直线,圆和椭圆算法,但没有一个矩形.理想情况下,我喜欢C,C++或Java中的某些东西,但对语言并不是那么挑剔.

输入数据通常由位于矩形上或靠近矩形的大多数点组成,具有一些异常值.数据分布不均匀,不太可能包括所有四个角.

Answer 1

以下是一些可能对您有帮助的想法。

我们可以估计一个点是在边缘上还是在角上，如下所示：

1. 收集该点的 n 个近邻
2. 计算点的质心
3. 计算点的协方差矩阵如下：
   1. 从...开始Covariance = ((0, 0), (0, 0))
   2. 对于每个点计算d = point - centroid
   3. Covariance += outer_product(d, d)
4. 计算协方差的特征值。（例如使用 SVD）
5. 分类点：
   • 如果一个特征值很大而另一个特征值很小，我们可能处于边缘
   • 否则我们就会陷入困境

提取所有角点并进行分割。选择条目最多的四个段。这些线段的质心是矩形角的候选点。

计算相对两侧的归一化方向向量并计算其平均值。计算另外两个相对边的平均值。这些是平行四边形的方向向量。如果您想要一个矩形，请计算其中一个方向的垂直向量，并计算另一个方向向量的平均值。那么矩形的方向是平均向量和垂直向量。

为了计算角点，您可以将候选对象投影到其方向上并移动它们，使它们形成矩形的角点。