I have an ordered list of (2d-)points that are forming a (not axis aligned) rectangle and I'd like to recover that rectangle. Approximations like a minimal enclosing rectangle can't be used so that I'm looking for an algorithm that minimizes the least-squares norm or the hausdorff distance.
The rectangle can be a square or rather narrow. The set contains several hundred points and the points cover at least three sides.
My current idea looks like that:
Initial estimation of center, rotation and lenghts from doing a PCA on the point set. (Rotation estimation will be especially bad for squares).
Then the points will be assigned to the closest side and the mean (rmse?) error recorded. This can be used as an optimization value for a following iterative LM-Optimization.