我有一个有序的（2d-）点列表，这些点正在形成一个（不是轴对齐的）矩形，我想恢复那个矩形。不能使用最小封闭矩形之类的近似值，因此我正在寻找一种最小化最小二乘范数或 hausdorff 距离的算法。
矩形可以是正方形或相当窄的。该集合包含数百个点，这些点至少覆盖三个边。
我目前的想法是这样的：
在点集上进行 PCA 对中心、旋转和长度的初始估计。（旋转估计对于正方形尤其不利）。
然后将这些点分配到最近的一侧并记录平均（rmse？）误差。这可以用作后续迭代 LM-Optimization 的优化值。
一些想法，需要通过计算试验来完善：
的估计开始，或者按照 OP 中的建议通过 PCA，或者使用边界框或圆的中心（相当便宜的计算，我认为我们只需要估计误差为的中心相对于矩形的尺寸小）。
扫描数据点以计算相对于估计中心的角度和距离。
该派生数据可以拟合为周期性函数与。直观地说，“局部”最大值出现在矩形的角上，如果所有四个角都在数据中得到很好的表示，则它们将相等（因此在理想情况下将是全局最大值）。
为了帮助解决数据中矩形的任何“缺失”边，我们通过估计的中心反映所有点，从而实现更完整的周长覆盖。似乎我们不需要实际计算这些反射，因为对角度与距离派生数据的影响只是在模型上施加了一个而不是的周期。
使用在最大值之一开始和结束的半间隔，将两段三角模型拟合（通过最小二乘法）到角度与距离数据。（另一个中间的最大值将两个段分开。）也就是说，具有笛卡尔方程的矩形的边缘将具有以下形式的角度与距离关系：
分析两个半区间数据点的系统偏差拟合误差。也就是说，如果一个段的一个半区间中的数据点主要具有正误差，而同一段的另一半区间中的数据点主要具有负误差，这表明我们的估计中心需要向原始中心移动现在给出正误差的点（从估计中心的实际半径减去拟合模型的预测半径）。
冲洗。泡沫。重复。